avl tree - проблема с вращением

Я пытался отлаживать свой код более часа и не могу понять, в чем проблема. У меня есть этот класс как Vertex:

class avl_node {
public:
    T data;
    int value;
    int high;
    avl_node *left, *right;
    avl_node *parent;

и у меня есть это дерево (до и после попытки вставить 21 в дерево): Я теряю информацию

Это функция вращения:

Status ll_rotation(avl_node<T> *v) {
    avl_node<T>* tmp = v->left;
    v->left = tmp->right;
    if (tmp->right){
        tmp->right->parent = v;
    }
    tmp->right = v;
    tmp->parent = v->parent;
    v->parent = tmp;
    if (this->root == v) {
        this->root = tmp;
    }
    return OK;
}

c++ avl-tree
person Guy Sadoun    schedule 07.05.2018    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Вы не обновляете указатель left или right родителя v. Могут быть и другие проблемы. Вот некоторый код из моей рабочей реализации. Имена переменных разные, но вы можете сравнить их со своими и посмотреть, каких операций вам не хватает. Функция update_height, которая вызывается в конце, проходит вверх по дереву, обновляя высоту каждого узла по мере продвижения.

template<typename K, typename V>
void AVLTree<K,V>::right_rotate(AVLNode<K,V> *node)
{
    auto hold = node->left;
    if (node == root)
    {
        root = hold;
    }
    else if (node == node->parent->left)
    {
        node->parent->left = hold;
    }
    else
    {
        node->parent->right = hold;
    }

    hold->parent = node->parent;
    node->left = node->left->right;
    if (node->left)
    {
        node->left->parent = node;
    }
    hold->right = node;
    node->parent = hold;
    update_height(node);
}
person Mike Borkland    schedule 07.05.2018
comment
Подумайте о том, чтобы принять этот ответ, если он действительно ответил на ваш вопрос. - person Mike Borkland; 08.05.2018

arrow_upward
0
arrow_downward

Вы проследили свои ll_rotate действия на бумаге? Все, на что указывает v->left в начале функции, теряется, поскольку вы никогда не переназначаете tmp соответствующему дочернему узлу исходного родителя v.

person 1201ProgramAlarm    schedule 07.05.2018
comment
да, я сделал, шаг за шагом. Отладчик Clion говорит, что это идеально в конце функции, когда я выхожу, я теряю информацию - person Guy Sadoun; 07.05.2018