Я реализую красно-черное дерево в C ++, но у меня проблемы с методами ротации. Метод вставки прекрасно работает без какой-либо балансировки, но как только я пытаюсь повернуть, мое дерево теряет информацию. Я предполагаю, что я неправильно устанавливаю указатели на узлы, но я не совсем понимаю, что здесь происходит не так.
Вот мой правильный метод поворота:
void RedBlackTree::rotateRight(RedBlackNode *localRoot) {
cout << "rotateRight - local root " << localRoot->data << endl;
RedBlackNode *temp = localRoot->left;
localRoot->left = temp->right;
temp->right = localRoot;
localRoot = temp;
}
Примером того, что происходит, я вставляю c, b и a. Дерево изначально выглядит так:
c
/
b
/
a
После поворота дерево распечатает только корневой узел, c.
Любые идеи о том, что может происходить? Спасибо!
Трудно сказать, основываясь на сегменте кода, но localRoot
является локальным указателем, изменение которого забывается в момент выхода из функции. Если вы хотите изменить его в контексте, из которого вызывается функция, вы можете передать его как RedBlackNode*&
или вы должны вернуть значение как результат.
Других решений пока нет …