Я работаю над реализацией дерева поиска AVL.Пока что я закончил часть кода и начал тестировать ее на наличие ошибок.Я обнаружил, что мои методы ротации узлов прослушиваются и, ради бога, я не могу понять, в чем проблема.
Алгоритм работает как на бумаге, но при выполнении на машине он хорошо ... пропускает узлы дерева.
Этот метод используется для поворота узла влево: http://pastebin.com/mPHj29Af
bool avl_search_tree::avl_tree_node::rotate_left()
{
if (_right_child != NULL) {
avl_tree_node *new_root = _right_child;
if (_parent != NULL) {
if (_parent->_left_child == this) {
_parent->_left_child = new_root;
} else {
_parent->_right_child = new_root;
}
}
new_root->_parent = _parent;
_parent = new_root;
_right_child = new_root->_left_child;
new_root->_left_child = this;
if (_right_child != NULL) {
_right_child->_parent = this;
}
//update heights
update_height();
new_root->update_height();
return true;
}
return false;
}
В моем методе вставки я прокомментировал часть балансировки AVL, и вместо этого я просто пытаюсь повернуть недавно вставленный узел влево.Результат для вставки целых чисел в порядке возрастания: мое дерево содержит только начальный корень (первый узел вставлен), а все остальные узлы просочились.
Любая помощь в выявлении проблемы очень важна, так как я начинаю идтиmad.
Для справки: если я не использую никаких вращений, дерево не будет пропускать узлы, и оно работает как обычное несбалансированное двоичное дерево поиска (для вставки и поиска).
Редактировать: Из-за комментария AJG85 я добавлю наблюдения:
Я добавил printf 'check' в метод деструктора avl_search_tree :: avl_tree_node, который будет печатать значение ключа (в моем случае 32-битные целые числа) перед очисткойи к методу вставки дерева avl_search_tree, который будет печатать только что вставленный ключ.
Затем в точке входа программы я выделяю в куче дерево avl_search_tree, добавляю ключи в порядке возрастания и затем удаляю его.
С включенной балансировкой AVL я получаю следующий вывод в терминале:
bool avl_search_tree::insert(const int&) : 1
bool avl_search_tree::insert(const int&) : 2
bool avl_search_tree::insert(const int&) : 3
bool avl_search_tree::insert(const int&) : 4
bool avl_search_tree::insert(const int&) : 5
bool avl_search_tree::insert(const int&) : 6
bool avl_search_tree::insert(const int&) : 7
bool avl_search_tree::insert(const int&) : 8
avl_search_tree::avl_tree_node::~avl_tree_node() : 1
Это означает, что все вставки были успешными, но был удален только корень.
С помощьюAVL Balancing прокомментировал, что он работает как обычное двоичное дерево поиска.Вывод терминала:
bool avl_search_tree::insert(const int&) : 1
bool avl_search_tree::insert(const int&) : 2
bool avl_search_tree::insert(const int&) : 3
bool avl_search_tree::insert(const int&) : 4
bool avl_search_tree::insert(const int&) : 5
bool avl_search_tree::insert(const int&) : 6
bool avl_search_tree::insert(const int&) : 7
bool avl_search_tree::insert(const int&) : 8
avl_search_tree::avl_tree_node::~avl_tree_node() : 1
avl_search_tree::avl_tree_node::~avl_tree_node() : 2
avl_search_tree::avl_tree_node::~avl_tree_node() : 3
avl_search_tree::avl_tree_node::~avl_tree_node() : 4
avl_search_tree::avl_tree_node::~avl_tree_node() : 5
avl_search_tree::avl_tree_node::~avl_tree_node() : 6
avl_search_tree::avl_tree_node::~avl_tree_node() : 7
avl_search_tree::avl_tree_node::~avl_tree_node() : 8
Что означает, что все правильно очищено.
Теперь ... как я пришел к выводу, что методы ротации - это проблемы?Под прокомментированной подпрограммой балансировки AVL я добавил строку, которая поворачивает каждый вновь вставленный узел влево.Результат?Так же, как если бы подпрограмма балансировки AVL была включена.
А что касается метода update_height (), он никак не изменяет структуру дерева.
Надеюсь, это прояснит это.
Edit 2:
Чтобы прояснить еще кое-что, его способ реализации деструктора avl_tree_node:
avl_search_tree::avl_tree_node::~avl_tree_node()
{
printf("%s : %d\n", __PRETTY_FUNCTION__, *_key);
if (_left_child != NULL) {
delete _left_child;
}
if (_right_child != NULL) {
delete _right_child;
}
if (_key != NULL) {
delete _key;
}
}
_left_child и _right_child являются указателями на объекты avl_tree_node, расположенные накуча.
Редактировать 3:
Благодаря второму комментарию AGJ85 я нашел проблему.В моих методах поворота я забыл, что мне нужно обновлять указатель корня дерева на новый корень всякий раз, когда корень смещается.
В основном корень дерева всегда указывал на первый вставленный узел и без обновления указателя, когданеобходимо, чтобы мои методы rotate вытекли из корня нового дерева, которое было настроено правильно.:)
Спасибо AGJ85!