C++ AVLTree Rotation

Question

Я пытаюсь сделать LeftRotation с моим AVLTree. Я вложу 3, 5, а затем 10, чтобы он стал вырожденным деревом. Когда я пройдусь, он даст мне 3, 5, 10, но когда я сделаю поворот, я просто получу 5, 10 вместо ожидаемого 5, 3, 10.

Это как-то связано с установкой a как bleft отрасль. Я пройду через него, а корень моего дерева будет 5, слева будет 3, а справа будет 10, но когда я иду на траверс, он показывает левую сторону как null.

Вот мой код вращения:

void AVLTree::RotateLeft(Node *root) 
{ 
    Node a = *root; 
    Node b = *root->GetRight(); 
    *root = b; 
    a.SetRight(b.GetLeft()); 
    b.SetLeft(&a); //This is where the problem occurs 
} 

И мой Traversal код:

void AVLTree::Traverse(Node *node) 
{ 
    cout << node->GetValue() << ", "; 
    if (node->GetLeft() != nullptr) 
     Traverse(node->GetLeft()); 
    if (node->GetRight() != nullptr) 
     Traverse(node->GetRight()); 
} 

Спасибо заранее!

Редактировать: все все 0 - nullptr, спасибо за исправление!

Answer 1

Проблема с тем, как root перемещается, чтобы указать на новое местоположение. Если есть сомнения в этом, рассмотрите следующие два утверждения. Обратите внимание, что соглашение об именовании переменных из исходного кода выше используется для согласованности.

*root = b; // (1) 
root = &b; // (2) 

В (1), содержимое корневого указателя модифицированы, чтобы содержать значение, сохраненное в переменной b. Адрес root не был изменен каким-либо образом. Адрес root имеет значение до (1) Выполнение остается неизменным после завершения (1).

В (2), root теперь указывает на адрес переменной b. Поскольку адрес, на который указывает root, был изменен, содержимое указателя root теперь равно значению в переменной b.

Я настоятельно рекомендую пройти через функцию void AVLTree::RotateLeft(Node *root) по строчке и проверить все адреса и содержимое всех переменных, чтобы увидеть это из первых рук. Я выполнил симуляцию вышеупомянутых действий над образцами целочисленных данных, и указатели перемещались, как ожидалось, с помощью (2).

Перед тем, как произойдет поворот данных образца, ожидается, что небалансное дерево должно быть расположено так, чтобы узел 3 указывал на root. Затем root->right указывает на 5, а root->right->right указывает на 10. root->right->left должен быть nullptr, а root->left также должен быть nullptr.

Если это не так, то либо алгоритм вставки АВЛ осуществляется неправильно или требования к конструкции отличаются, чем ожидалось (например AVL tree на Википедии, Data Structures and Algorithm Analysis in C++ (3rd Edition) [Hardcover] по Марк Аллен Weiss, AVL Tree Tutorial on Eternally Confuzzled по Julienne Walker).

Что касается движения балансировки дерева, где конечный результат root указывает на 5, то root->left указывает на 3 и root->right указывает на 10, правый указатель переданному в root указатель будет установлен в точку слева указатель локального указателя pB, левый указатель pB будет указывать на переданный в root указатель, а root будет указывать на локальную переменную pB (первоначально в этом случае указатель root->right).

Используя данные примера выше, тело функции изменено. Обратите внимание, что это не согласуется с тем, как GetRight() и GetLeft() возвращают копию узла в исходном сообщении выше. Модифицированный орган функции ниже соответствует single AVL rotation with right child, реализованному Марк Аллен Вайс, упомянутый выше. Поскольку исходное сообщение не имеет переменной высоты, код ниже также не является.

// 
// The `root` variable is passed as a pointer by reference 
// 
void AVLTree::RotateLeft(Node* & root) 
{ 
    // 
    // This works as long as the GetRight() method returns a pointer, not a Node copy 
    // 
    Node *pB = root->GetRight(); 

    // 
    // In the example values for three nodes, the root->right will become nullptr 
    // 
    root->SetRight(pB->GetLeft()); 

    // 
    // In the example values, the pB->left will point to the node with value of 3 
    // 
    pB->SetLeft(root); 

    // 
    // Move root to point to where pB does (root->right) 
    // 
    root = pB; 
}