avl树插入元素后如何固定平衡因子？

Question

我将在实现 AVL 树的地方提供我的 C 代码。对于某些测试用例，代码在遍历 bst 时显示每个元素的平衡因子时正常工作。在其中一个测试用例中，我的平衡因子超过了 (-1,0,1)。我不确定哪里出了问题。我无法理解我是否在 NODE* leftRotate、rightRotate 和 Insert 函数中返回了错误的值。

我还想了解一下 leftRotate 和 rightRotate 函数。我们将根节点作为函数中的参数传递。如果我们在这里考虑 leftRotate 函数

NODE* leftRotate(NODE* x){
    NODE* y = x->right;
    NODE* T2 = y->left;
    y->left = x;
    x->right = T2;
    int x_height = max(height(x->left),height(x->right)+1);
    int y_height = max(height(y->left),height(y->right) + 1);
    return y;
}

当他们写作时

NODE* y = x->right;
NODE* T2 = y->left;

我们得到这样的树：

x
 \ R
  y
 / L
T2

我们得到一个 RL 案例，所以我们应该先申请 RR

x
 \R
  y
   \R
    T2

答案会是

 y
/ \
x  T2

我不确定在 leftrotate 函数中，我们只是将根元素向左旋转，而不是应用通常的 RL 技术。我只是想澄清一下，如果这就是我们应该为它应用 RL、RR 案例所做的一切。

//Avl tree 

#include<stdio.h>
#include<stdlib.h>

typedef struct node{
    int data;
    struct node *left,*right;
} NODE;

NODE* createNode(int ele){
    NODE* newnode = (NODE*)malloc(sizeof(NODE));
    newnode->data = ele;
    newnode->right = newnode->left = NULL;
    return newnode;
}

NODE* createBT(){
    int ele;
    printf("Enter the element(Don't enter any duplicates):\n");
    scanf("%d",&ele);

    if (ele == -1){
        return NULL;
    }

    NODE* newnode = createNode(ele);
    printf("Enter the left child of %d(-1 to stop),\n",ele);
    newnode->left = createBT();
    printf("Enter the right child of %d(-1 to stop),\n",ele);
    newnode->right = createBT();
    return newnode;
}

int max(int a, int b){
    if (a > b)
        return a;
    else 
        return b; 
}

int height(NODE* root){
    if (root == NULL){
        return 0;
    }
    else
        return max(height(root->left),height(root->right)) + 1;
}

int BalFactor(NODE* temp){
    if (temp == NULL){
        printf("Tree is empty\n");
    }
    return height(temp->left) - height(temp->right);
}


//note: The NODE* x is the root element
//Visualise anticlockwise rotation on the root don't think of RL case
NODE* leftRotate(NODE* x){
    NODE* y = x->right;
    NODE* T2 = y->left;
    y->left = x;
    x->right = T2;
    int x_height = max(height(x->left),height(x->right)+1);
    int y_height = max(height(y->left),height(y->right) + 1);
    return y;
}

//note:NODE* y is the root element
NODE* rightRotate(NODE* y){
    NODE* x = y->left;
    NODE* T2 = x->right;
    x->right = y;
    y->left = T2;
    int x_height = max(height(x->left),height(x->right)) + 1;
    int y_height = max(height(y->left),height(y->right)) + 1;
    return x; 
}

//Recursive insert
/*
NODE* insert(NODE* root, int ele){
    if (root == NULL){
        return createNode(ele);
    }

    else if(ele > root->data){
        root->right = insert(root->right,ele);    
    }

    else if(ele < root->data){
        root->left = insert(root->left,ele);    
    }

    else
        return root;
    
    int h = 1 + max(height(root->left),height(root->right));
    int bal = BalFactor(root); 
    
    //balance factor is greater than 1 its either LL or LR 
    //balance factor is lesss than -1  its either RR ot RL

    //LL
    if (bal > 1 && ele < root->left->data){
        return rightRotate(root);
    }
    //RR
    
    if (bal > -1 && ele > root->right->data){
        return leftRotate(root);
    }
    //LR
    if (bal > 1 && ele > root->right->data){
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }
    //RL
    if (bal < -1 && ele < root->right->data){
        return leftRotate(root);
    }
    return root;
}
*/

//iterative insert function
NODE* insert(NODE* root,int ele){
    NODE* newnode = createNode(ele);
    NODE* x = root;
    NODE* y = NULL;

    while (x != NULL){
        y = x;
        if (ele < x->data)
            x = x->left;
        else
            x = x->right;
    }

    if(y == NULL)
        y = newnode;
    
    else if(ele < y->data)
        y->left = newnode;
    
    else 
        y->right = newnode;

    return y;

    int h = 1 + max(height(y->left),height(y->right));
    int bal = BalFactor(y); 
    //LL
    //balance factor is greater than 1 its either LL or LR 
    //balance factor is lesss than -1  its either RR ot RL
    if (bal > 1 && ele < y->left->data){
        return rightRotate(y);
    }
    //RR
    
    if (bal > -1 && ele > y->right->data){
        return leftRotate(y);
    }
    //LR
    if (bal > 1 && ele > y->right->data){
        y->left = leftRotate(y->left);
        return rightRotate(y);
    }
    //RL
    if (bal < -1 && ele < y->right->data){
        return leftRotate(y);
    }
    return root;
}

void inorder(NODE* root){
    if (root != NULL){
        inorder(root->left);
        printf(" %d (%d)", root->data, BalFactor(root));
        inorder(root->right);
    }
}
 
void postorder(NODE* root){
    if (root != NULL){
        postorder(root->left);
        postorder(root->right);
        printf(" %d (%d)", root->data, BalFactor(root));
    }
}

void preorder(NODE* root){
    if (root != NULL){
        printf(" %d (%d)", root->data, BalFactor(root));
        preorder(root->left);
        preorder(root->right);
    }
}


int main(){
    NODE* root  = NULL;
    root = createBT();
    int ch,ele;
    printf("\nList of operations:\n1.Insert\n2.Traversals and display balance factor\n3.Exit\n");
    while(1){
        printf("\nEnter your choice:\n");
        scanf("%d",&ch);

        if (ch == 1){
            printf("Enter the element to insert:\n");
            scanf("%d",&ele);
            insert(root,ele);
        }

        else if(ch == 2){
            printf("Inorder traversal:\n");
            inorder(root);
            
            printf("\nPreorder traversal:\n");
            preorder(root);
            
            printf("\nPostorder traversal:\n");
            postorder(root);
        }

        else if(ch == 3){
            break;
        }
        else{
            printf("Enter a valid choice\n");
        }
    }
    return 0;
}

代码输出：

Enter the element(Don't enter any duplicates):
10
Enter the left child of 10(-1 to stop),
Enter the element(Don't enter any duplicates):
9
Enter the left child of 9(-1 to stop),
Enter the element(Don't enter any duplicates):
8
Enter the left child of 8(-1 to stop),
Enter the element(Don't enter any duplicates):
7
Enter the left child of 7(-1 to stop),
Enter the element(Don't enter any duplicates):
-1
Enter the right child of 7(-1 to stop),
Enter the element(Don't enter any duplicates):
12
Enter the left child of 12(-1 to stop),
Enter the element(Don't enter any duplicates):
-1
Enter the right child of 12(-1 to stop),
Enter the element(Don't enter any duplicates):
-1
Enter the right child of 8(-1 to stop),
Enter the element(Don't enter any duplicates):
13
Enter the left child of 13(-1 to stop),
Enter the element(Don't enter any duplicates):
-1
Enter the right child of 13(-1 to stop),
Enter the element(Don't enter any duplicates):
-1
Enter the right child of 9(-1 to stop),
Enter the element(Don't enter any duplicates):
20
Enter the left child of 20(-1 to stop),
Enter the element(Don't enter any duplicates):
-1
Enter the right child of 20(-1 to stop),
Enter the element(Don't enter any duplicates):
-1
Enter the right child of 10(-1 to stop),
Enter the element(Don't enter any duplicates):
21
Enter the left child of 21(-1 to stop),
Enter the element(Don't enter any duplicates):
-1
Enter the right child of 21(-1 to stop),
Enter the element(Don't enter any duplicates):
-1

 10 (1) 9 (2) 8 (1) 7 (-1) 12 (0) 13 (0) 20 (0) 21 (-2) 30 (-1) 40 (0)
Postorder traversal:
 12 (0) 7 (-1) 13 (0) 8 (1) 20 (0) 9 (2) 40 (0) 30 (-1) 21 (-2) 10 (1)
Enter your choice:
3

Answer 1

实现 AVL 树时，请确保保留一个高度成员，以便检查高度是否为 +/- 2。然后，在插入时，如果任何节点的高度变为 > 2 或 < -2.

，您将重新平衡

确保输入正确值的唯一方法是将它们输入到程序中，然后对树进行中序、前序、后序打印。使用程序的打印输出并在纸上重建树，以确保树正确形成并且重新平衡功能正常工作。

旧金山大学的 AVL Tree Visualizer 网站 有一个很棒的可视化工具，可以让你看到 AVL 树上的旋转，你可以用它来帮助你理解旋转是如何工作的。

无论 AVL 树如何实现，旋转总是相同的。 这里是 RL 技术工作原理的详细解释。网上还有很多其他技术含量较低的解释，可能更容易理解