数据结构 — AVL tree（平衡二叉树）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include<stdio.h>
#include<iostream>
using namespace std;

#define FALSE 0
#define TRUE 1

typedef struct {
    int key;
} element;

typedef struct tree_node {
    struct tree_node *left_child;
    element data;
    short bf;
    struct tree_node *right_child;
} tree_node, *tree_pointer;

int unbalanced = FALSE;
tree_pointer root = NULL;

void left_rotation(tree_pointer *parent, int *unbalanced);
void right_rotation(tree_pointer *parent, int *unbalanced);
void avl_insert(tree_pointer *parent, element x, int *unbalanced);
/*
 *1.如果要插入的元素的父节点为空则为其分配内存并处理
 *2.如果小于父节点的数据域则插入父节点的左孩子，并旋转
 *3.如果大于父节点的数据域则插入父节点的右孩子，并旋转
 */
void avl_insert(tree_pointer *parent, element x, int *unbalanced) {
    if(!*parent) {
        *unbalanced = TRUE;
        *parent = new tree_node();
        (*parent)->left_child = (*parent)->right_child = NULL;
        (*parent)->bf = 0;
        (*parent)->data = x;
    }
    else if(x.key < (*parent)->data.key) {
        avl_insert(&(*parent)->left_child, x, unbalanced);
        if(*unbalanced) {
            /*
             * unbalanced表示是插完之后就不平衡了 和 判断还用不用处理平衡因子
             */
            switch((*parent)->bf) {
                case -1:
                    (*parent)->bf = 0;
                    *unbalanced = FALSE;
                    break;
                case 0:
                    (*parent)->bf = 1;
                    break;
                case 1:
                    left_rotation(parent,unbalanced);
            }
        }
    }
    else if(x.key > (*parent)->data.key) {
        avl_insert(&(*parent)->right_child, x, unbalanced);
        if(*unbalanced) {
            switch((*parent)->bf) {
                case 1:
                    (*parent)->bf = 0;
                    *unbalanced = FALSE;
                    break;
                case 0:
                    (*parent)->bf = 1;
                    break;
                case -1:
                    right_rotation(parent, unbalanced);
            }
        }
    }
    else {
        *unbalanced = FALSE;
        printf("该元素已经存在！n");
    }
}

void left_rotation(tree_pointer *parent, int *unbalanced) {
   tree_pointer grand_child, child;
    child = (*parent)->left_child;
    if(child->bf == 1) {
        //LL
        (*parent)->left_child = child->right_child;
        child->right_child = *parent;
        (*parent)->bf = 0;
        (*parent) = child;
    } else {
        //LR
        grand_child = child->right_child;
        child->right_child = grand_child->left_child;
        grand_child->left_child = child;
        (*parent)->left_child = grand_child->right_child;
        grand_child->right_child = (*parent);
        switch(grand_child->bf) {
            case 1:
                (*parent)->bf = -1;
                child->bf = 0;
            case 0:
                (*parent)->bf = child->bf = 0;
            case -1:
                (*parent)->bf = 0;
                child->bf = 1;
        }
        (*parent) = grand_child;
    }
    (*parent)->bf = 0;
    *unbalanced = FALSE;
}

void right_rotation(tree_pointer *parent, int *unbalanced) {
    tree_pointer grand_child, child;
    child = (*parent)->right_child;
    if(child->bf == -1) {
        //RR
        (*parent)->right_child = child->left_child;
        child->left_child = (*parent);
        (*parent) = child;
    } else {
        //RL
        grand_child = child->left_child;

        child->left_child = grand_child->right_child;
        grand_child->right_child = child;
        (*parent)->right_child = grand_child->left_child;
        grand_child->left_child = (*parent);
        switch(grand_child->bf) {
            case 1:
                (*parent)->bf = 0;
                child->bf = -1;
            case 0:
                (*parent)->bf = child->bf = 0;
            case -1:
                (*parent)->bf = 1;
                child->bf = 0;
        }
        (*parent) = grand_child;
    }
    (*parent)->bf = 0;
    *unbalanced = FALSE;
}
void raverse(tree_pointer root) {
    if(root) {
        printf("%d ",root->data.key);
        raverse(root->left_child);
        raverse(root->right_child);
    }
}
int main() {
    int arr[11] = {15,6,18,3,7,17,20,2,4,13,9};
    element arr_x[11];
    for(int i = 0; i<11; i++) {
    
        arr_x[i].key = arr[i];
     //   cout<<arr_x[i].key<<endl;
        avl_insert(&root, arr_x[i], &unbalanced);
    }
    
    raverse(root);
    printf("n");
    return 0;
}