AVL Tree странное поведение - PullRequest
Новая
       1

AVL Tree странное поведение

0 голосов
/ 05 марта 2011

Следующий код меня очень озадачил.

класс 

class AVLTree {
   private:
struct AVLNode
{
    AVLNode *leftchild;
    AVLNode *rightchild;
    int data;
    int height;
};

AVLNode *root;

public:

AVLTree()
{
    root = NULL;
}

bool isEmpty() const { return root == NULL; }
void print();
void inorder(AVLNode *n, int l);
void insert(int d);
void rotateLeft(AVLNode* n);
void rotateRight(AVLNode* n);
void rotateLeftTwice(AVLNode* n);
void rotateRightTwice(AVLNode* n);
AVLTree::AVLNode* insert(int d, AVLNode* n);
int max( int a, int b);
int height( AVLNode* n); };

функция вставки. 

  AVLTree::AVLNode* AVLTree::insert(int d,AVLNode *n){
    if (n == NULL)
    {
        AVLNode *n = new AVLNode;
        n->data = d;
        n->leftchild = NULL;
        n->rightchild = NULL;
        n->height = 0;
    } else if( d < n->data) {
        n->leftchild = insert(d,n->leftchild);

    } else if (d > n->data) {
        n->rightchild = insert(d,n->rightchild);
    }
    else {      
        n->height = max(height(n->leftchild), height(n->rightchild));
        return n;
         }
        -----> This section of the code gives be "EXC_BAD_ACCESS".
    n->height = max(height(n->leftchild), height(n->rightchild));
       return n;
}

Это функция высоты. 

int AVLTree::height(AVLNode* node)
{   cout << "HEIGHT"; 
    if(node == NULL)
    {
        return -1;
    }
    else {
        return node->height;
    }
}

Кто-нибудь знает почему?

=== Обновление:

при выполнении поворота 

 void AVLTree::rotateLeft(AVLNode* n)
    {
            AVLNode *child = n->leftchild;
            n->leftchild = child->rightchild;
            child->rightchild = n;

            n->height = max(height(n->leftchild),height(n->rightchild))+1;
            child->height = max(height(child->leftchild),height(child->rightchild))+1;
            n = child;
}

Кажется, что значения не меняются должным образом.Кажется, что n = child поменяется местами, но это не отражает изменения в остальной части кода.Давая мне бесконечный цикл.

1 Ответ

2 голосов
/ 06 марта 2011

Если n был нулевым при входе в функцию, то эта строка будет пытаться разыменовать его, выдавая ошибку. Ваш код для выделения нового узла должен присваивать его самому n, а не отдельной переменной с тем же именем, которая скрывает аргумент функции.

Изменить первую строку блока if (n == NULL) с 

AVLNode *n = new AVLNode;

до 

n = new AVLNode;

Относительно обновления: * В вашей функции поворота n является локальной (автоматической) переменной, изменение которой не повлияет на что-либо вне функции. Вам нужно будет либо передать указатель по ссылке, либо вернуть новое значение указателя (как вы это делаете в insert()).

...