Авл дерево - буду вращать проблам

Question

Я пытаюсь отладить свой код более часа, и я не могу понять, в чем проблема. У меня есть этот класс как 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;
}

Answer 1

Вы не обновляете указатель 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);
}

Answer 2

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