1

我正在创建一个自排序二进制搜索树的任务,每次尝试将重复元素插入树时都会重新组织它。我遇到了一些需要帮助解决的错误。

首先,树的根永远不会改变(我假设问题出在 RotateLeft 或 RotateRight 方法中)当第一个副本进入时,根永远不会更改为现在更高优先级的节点。

我得到的第二个错误是 BAD ACCESS ERROR(我已经注意到它在下面的代码中的位置),我猜它也是来自这些 Rotate 方法之一。

#ifndef SelfOrganizingTree_SOBTree_h
#define SelfOrganizingTree_SOBTree_h

#include "BinaryNode.h"
#include "bst.h"


template <class T>
class BinaryNode;

template <class T>
class SOBTree: public BinarySearchTree<T> {
public:
    SOBTree();
    void insert( const T& x );
    void remove( const T& x );
    bool isEmpty() const;
    void printTree() const;
    int reportComparisonCount();
    double reportCPUTime();


private:
    void insert( const T & x, BinaryNode<T> * & t , BinaryNode<T> * & rootNode);
    void RotateRight(BinaryNode<T> * & root );
    void RotateLeft(BinaryNode<T> * & root );
    void printTree(BinaryNode<T> *t) const;
    BinaryNode<T> *root;
    void balance (BinaryNode<T> * & root);

};

template <class T >
SOBTree<T> ::  SOBTree()
{
    root = NULL; 
}

/**
 * Insert x into the tree
 */
template <class T >
void SOBTree<T > ::  insert( const T & x )
{
    insert( x, root , root);
}

/**
 * Internal method to insert into a subtree.
 * x is the item to insert.
 * t is the node that roots the subtree.
 * Set the new root of the subtree.
 */
template <class T>
void SOBTree<T> ::  insert( const T & x, BinaryNode<T> * & t , BinaryNode<T> * & rootNode)
{
   // BinaryNode<T> *current = t;
    if( t == NULL ){
        t = new BinaryNode<T>( x, NULL, NULL, rootNode );
        //cout << t->element << endl;
        t->priority++;
    }
    else if( x < t->element ){
        //cout << "left" << endl;
        insert( x, t->left , t);
    }
    else if( t->element < x ){
        //cout << "right" << endl;
        insert( x, t->right , t);
    }
    else{
        //cout << "match found" << endl;
        t->priority++;  // Duplicate; rotate right or left if priority is higher than the root
        balance(t);
    }
}

template <class T>
void SOBTree<T>::balance (BinaryNode<T> * & rootN){

    cout << "root: " << root->element << endl;
    if (rootN->parent && rootN->priority > rootN->parent->priority) { //THIS IS WHERE THE BAD ACCESS ERROR IS BEING THROWN
        if (rootN->parent->left == rootN) {

            RotateLeft(rootN->parent);
            balance(rootN->parent);

        }else if (rootN->parent->right == rootN){

            RotateRight(rootN->parent); 
            balance(rootN->parent);

        }
    }

}


template <class T>
void
SOBTree<T>::RotateLeft(BinaryNode<T> * & rootN) {
    /*
     Let P be Q's left child.
     Set P to be the new root.
     Set Q's left child to be P's right child.
     Set P's right child to be Q.
     */

    BinaryNode<T> * oldRoot = rootN;

    // perform rotation
    rootN = rootN->left;
    oldRoot->left = rootN->right;
    rootN->right= oldRoot;

}


template <class T>
void
SOBTree<T>::RotateRight(BinaryNode<T> * & rootN) {
    /*
     Let Q be P's right child.
     Set Q to be the new root.
     Set P's right child to be Q's left child.
     Set Q's left child to be P.
     */

   BinaryNode<T> * oldRoot = rootN;

    // perform rotation
    rootN = rootN->right;
    oldRoot->right = rootN->left;
    rootN->left = oldRoot;

}

template <class T>
bool SOBTree<T> ::  isEmpty( ) const
{
    return root == NULL;
}

/**
 * Print the tree contents in sorted order.
 */
template <class T>
void SOBTree<T> ::  printTree(  ) const
{
    if( isEmpty( ) )
        cout << "Empty tree" << endl;
    else
        printTree( root );
}

template <class T>
void SOBTree<T> ::  printTree( BinaryNode<T> *t ) const
{
    if( t != NULL )
    {

        printTree( t->left );
        cout << t->element << endl;
        printTree( t->right );
    }else
        return;
}



#endif

这是 BinaryNode 结构的代码:

template <class Type>
class BinarySearchTree;     //forward declaration so BinaryNode knows about BinarySearchTree

template <class Type>
class BinaryNode{
public:
    Type element;
    BinaryNode<Type>* left;
    BinaryNode<Type>* right;
    BinaryNode<Type>* parent;
    int priority;

    BinaryNode( Type theElement, BinaryNode *lt, BinaryNode* rt, BinaryNode *par = NULL, int pri = 0) :
          element(theElement), left(lt), right(rt) ,  parent(par), priority(pri)
    { }

    friend  class BinarySearchTree<Type>;
};

有没有人看到我可以改变以提供帮助的任何东西?

4

1 回答 1

0
if (rootN->parent && rootN->priority > rootN->parent->priority) { 

要么是rootN要么rootN->parentNULL或其他无效的指针。

于 2012-03-21T20:27:25.093 回答