avl tree - ll 旋转问题

Question

我已经尝试调试我的代码一个多小时了，但我不明白问题出在哪里。我有这个 class 作为顶点：

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

我有这棵树（尝试将 21 插入树之前和之后）：

这是 ll 旋转函数：

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

您是否在纸上描绘了您的 ll_rotate 动作？ v->left 在函数开头指向的任何内容都将丢失，因为您永远不会将 tmp 重新分配给 v 的原始父节点的正确子节点。

Answer 2

您没有更新 v 的父项的 left 或 right 指针。可能还有其他一些问题。这是我的工作实现中的一些代码。变量名称不同，但您可以将其与您的变量名称进行比较，看看您缺少哪些操作。最后调用的 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);
}

avl tree - ll 旋转问题

avl tree - ll rotate problam

c++

avl-tree