c - AVL 树未正确平衡

Question

我的作业是编写一个自平衡二叉搜索树。我决定使用 AVL 树，因为它是我们在类里面讨论过的。然后使用给定的输入 { 3, 5, 61, 9, 32, 7, 1, 45, 26, 6} 我期待输出:

               7
         6-----|-----32
    3----|      9----|----45
1---|           |---26    |---61

也就是说，除非我严重误解并因此错误地计算了 AVL 树在平衡自身时应该做什么。我得到的输出是完全不同的:

              5
        3-----|-----61
   1----|      9----|
           7---|---32
        6--|    26--|--45

再说一次，除非我完全错了，否则那棵树是不平衡的。我用来设置树的函数定义如下:

node* insertKeyAVL(node* n, int e)
{
    int cmpVal;

    if (n == NULL){
            n = create_node();
            n->data = e;
    } else if (e < n->data) {
            if (n->left == NULL){
                    n->left = create_node();
                    n->left->data = e;
                    n->left->parent = n;
            } else {
                    n->left = insertKeyAVL(n->left, e);
            }

            cmpVal = height(n->left) - height(n->right);


    } else {
            if (n->right == NULL){
                    n->right = create_node();
                    n->right->data = e;
                    n->right->parent = n;
            } else {
                    n->right = insertKeyAVL(n->right, e);
            }

            cmpVal = height(n->right) - height(n->left);
    }

    if (cmpVal > 2){
            if (n->left){
                    if (e < n->left->data)
                            n = rotate_left(n);
                    else
                            n = rotate_right_left(n);
            } else if (n->right){
                    if (e > n->right->data)
                            n = rotate_right(n);
                    else
                            n = rotate_left_right(n);
            }
    }

    n->height = max(height(n->left), height(n->right)) + 1;

    return n;
}

我用来存储所有数据的结构定义如下:

typedef struct node
{

    struct node *parent;
    struct node*  left;
    struct node*  right;

    int data;

    int height;
} node;

函数 rotate_left_right 和 rotate_right_left 是旋转第一个后缀然后第二个后缀的方向的基本函数，它们各自的方向都依赖于 rotate_left 和 rotate_right。向左旋转定义如下:

node* rotate_left(node* n)
{
    node* tmp = n->left;
    n->left = tmp->right;
    tmp->right = n;

    tmp->parent = n->parent;
    n->parent = tmp;

    n->height = max(height(n->left), height(n->right)) + 1;
    tmp->height = max(height(tmp->left), n->height) + 1;

    return tmp;
}

rotate_right 类似，但调整为向右旋转。

我想知道这段代码哪里搞砸了，以至于它没有产生所需的输出。

Answer 1

当您在预期结果中添加 26 时，5 的 cmpval 变为 2，这是无效的，这就是代码重新执行并给出结果的原因。