Какова правильная реализация AVL Tree Rotation? - PullRequest
Новая
       5

Какова правильная реализация AVL Tree Rotation?

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

При вставке 50,49,48 в дерево AVL оно распечатывается. 

The root is: 50 
50 Level: 0 Height: 0

 49 Level: 1 Height: 0
50 Level: 0 Height: -1

50 Level: 0 Height: 0 -->> Rotation did not work?

Вот мои функции. Повернуть влево: 

void AVLTree::rotateLeft(AVLNode* node)
{   
    AVLNode* otherNode = node;


    otherNode = node->leftchild;
    node->leftchild = otherNode->rightchild;
    otherNode->rightchild = node;

    node->height = max( height(node->leftchild), height(node->rightchild)) +1;
    otherNode->height = max( height(otherNode->leftchild) , height(otherNode->rightchild))+1;
    node = otherNode;

}

вставка: 

AVLTree::AVLNode* AVLTree::insert(int d,AVLNode *n){
if (n == NULL)
{
    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);

    if (height(n->leftchild) - height(n->rightchild) == 2) {
        if (d < n->leftchild->data) {
            rotateLeft(n);
        } else {
            rotateLeftTwice(n);
        }
    }

} else if (d > n->data) {

    n->rightchild = insert(d,n->rightchild);

    if (height(n->rightchild) - height(n->leftchild) == 2) {
        if (d > n->rightchild->data) {
            rotateRight(n);
        } else {
            rotateRightTwice(n);
        }
    }
} else {    
    ;
}
n->height = max(height(n->leftchild), height(n->rightchild))+1;
return n;}

1 Ответ

1 голос
/ 07 марта 2011

Параметр node для вашей функции rotateLeft является локальной переменной в rotateLeft.Другими словами, когда вы присваиваете значение этой переменной в rotateLeft, переменная n в insert не изменяется.Вам необходимо передать n в rotateLeft либо через указатель, либо через ссылку, т.е. либо 

void AVLTree::rotateLeft(AVLNode** node)

, либо 

void AVLTree::rotateLeft(AVLNode*& node)

Тот же принцип применим к insert 's n параметр - если вы хотите, чтобы функция изменила значение переменной, вам нужно передать ей указатель или ссылку на эту переменную, а не на ее значение.

...