AVL Tree

AVL 平衡二叉树

AVL 平衡二叉树在 BST 的基础上要求左右两子树的高度差不超过 1

插入新的元素可能影响树的平衡性,为了使插入元素后的树继续满足 AVL 性质,要对树进行一些调整。

插入新的元素后,有四种情况,分别为 LL, LR,RR,RL

调整的方法是对最小不满足AVL性质的子树进行旋转操作。

左旋和右旋

1
2
3
4
5
6
7
8
9
10
11
12
T1, T2 and T3 are subtrees of the tree 
rooted with y (on the left side) or x (on
the right side)
y x
/ \ Right Rotation / \
x T3 - - - - - - - > T1 y
/ \ < - - - - - - - / \
T1 T2 Left Rotation T2 T3
Keys in both of the above trees follow the
following order
keys(T1) < key(x) < keys(T2) < key(y) < keys(T3)
So BST property is not violated anywhere.

左旋和右旋操作后,子树仍然满足 BST 的性质,但是某些情况下可以降低子树的高度。

插入新的元素后,找到最小不满足 AVL 性质的子树,有以下四种情况(左侧)

主要关注 Z, Y, X

  1. Left Left Case (LL)
1
2
3
4
5
6
7
8
T1, T2, T3 and T4 are subtrees.
z y
/ \ / \
y T4 Right Rotate (z) x z
/ \ - - - - - - - - -> / \ / \
x T3 T1 T2 T3 T4
/ \
T1 T2

具体例子

  1. Left Right Case (LR)
1
2
3
4
5
6
7
     z                               z                           x
/ \ / \ / \
y T4 Left Rotate (y) x T4 Right Rotate(z) y z
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
T1 x y T3 T1 T2 T3 T4
/ \ / \
T2 T3 T1 T2

具体例子

  1. Right Right Case (RR)
1
2
3
4
5
6
7
  z                                y
/ \ / \
T1 y Left Rotate(z) z x
/ \ - - - - - - - -> / \ / \
T2 x T1 T2 T3 T4
/ \
T3 T4
  1. Right Left Case
1
2
3
4
5
6
7
   z                            z                            x
/ \ / \ / \
T1 y Right Rotate (y) T1 x Left Rotate(z) z y
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
x T4 T2 y T1 T2 T3 T4
/ \ / \
T2 T3 T3 T4

实现

leetcode 题

https://leetcode-cn.com/problems/balance-a-binary-search-tree/

非递归版本….xjb 手写能过 leetcode

插入过程:

遍历找插入位置 -> 插入 -> 更新高度 -> 发现左右子树高度差大于 2 -> 判断旋转类型 -> 旋转

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
void insert(int key) {
printf("%d\n", key);
AVLTreeNode * new_node = _alloca_node();
new_node->key = key;
new_node->height = 1;
if ( root == nullptr) {
root = new_node;
return;
}

// 找到一个合适的插入位置
AVLTreeNode * insert_node = root;
while ( (key <= insert_node->key && insert_node->left) || (key > insert_node->key && insert_node->right) ) {
insert_node = key<=insert_node->key?insert_node->left:insert_node->right;
}

// 插入到找到的位置.
new_node->parent = insert_node;
if ( key <= insert_node->key )
insert_node->left = new_node;
else
insert_node->right = new_node;

// 更新高度
AVLTreeNode * travel = new_node->parent;
AVLTreeNode * lastBugTree = nullptr;
int balance;
while (travel) {
int height_r, height_l;
height_l = travel->left ? travel->left->height : 0;
height_r = travel->right ? travel->right->height : 0;
travel->height = max(height_l, height_r) + 1;
balance = height_l - height_r;
if(abs(balance) > 1) {
lastBugTree = travel;
break;
}
travel = travel->parent;
}

// 旋转
AVLTreeNode * new_root;
if (lastBugTree) {
AVLTreeNode * lastBugParent;
lastBugParent = lastBugTree->parent;
if(balance > 1 && new_node->key < lastBugTree->left->key) {
printf("Type1\n");
new_root = right_rotate(lastBugTree);
}else if(balance > 1 && new_node->key > lastBugTree->left->key){
printf("Type2\n");
new_root = left_right_rotate(lastBugTree);
}else if(balance < 0 && new_node->key > lastBugTree->right->key) {
printf("type3\n");
new_root = left_rotate(lastBugTree);
} else if(balance < 0 && new_node->key < lastBugTree->right->key) {
printf("Type4\n");
new_root = right_left_rotate(lastBugTree);
}

if (!lastBugParent) {
root = new_root;
}else {
if (lastBugParent->key > lastBugTree->key)
lastBugParent->left = new_root;
else
lastBugParent->right = new_root;
};
}
}

旋转相关的代码

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
AVLTreeNode * right_rotate(AVLTreeNode * z) {
AVLTreeNode * y = z->left;
AVLTreeNode * x = y->left;

y->parent = z->parent;
z->left = y->right;
if (z->left) z->left->parent = z;
y->right = z;
z->parent = y;
// 更新高度
z->height = get_height(z) + 1;
y->height = get_height(y) + 1;
return y;
}

AVLTreeNode * left_rotate(AVLTreeNode * z) {
AVLTreeNode * y = z->right;
AVLTreeNode * x = y->right;

z->right = y->left;

if (z->right)
z->right->parent = z;
y->parent = z->parent;
z->parent = y;
y->left = z;
// 更新高度
z->height = get_height(z) + 1;
y->height = get_height(y) + 1;
return y;
}

AVLTreeNode * left_right_rotate(AVLTreeNode * z) {
AVLTreeNode * y = z->left;
AVLTreeNode * x = y->right;
z->left = left_rotate(y);
return right_rotate(z);
}


AVLTreeNode * right_left_rotate(AVLTreeNode * z) {
AVLTreeNode * y = z->right;
AVLTreeNode * x = y->left;
z->right = right_rotate(y);
return left_rotate(z);
}

参考

[1] AVL 数据可视化 https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
[2] AVL Tree | Set 1 (Insertion) https://www.geeksforgeeks.org/avl-tree-set-1-insertion/
[3] Data Structure and Algorithms - AVL Trees https://www.tutorialspoint.com/data_structures_algorithms/avl_tree_algorithm.htm

[4] leetcode 1382. 将二叉搜索树变平衡 https://leetcode-cn.com/problems/balance-a-binary-search-tree/


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!