CS61B 课程笔记（Lecture
22 Balanced BSTs)
平衡二叉搜索树（BSTs）
1. BST 性能
最优和最差情况
- 最佳情况：
- 当树是完全平衡的，所有节点都均匀分布，树的高度为 \(\Theta(\log N)\)。
- 在这种情况下，插入、查找和删除操作的时间复杂度均为 \(O(\log N)\)。
- 最差情况：
- 当树的插入顺序导致其退化为链表（例如，按升序插入1到N），树的高度为
\(\Theta(N)\)。
- 此时，查找和插入操作的时间复杂度变为 \(O(N)\)。
2. 高度与深度
- 高度：
- 树的高度是指从根节点到最深叶节点的最长路径长度。
- 高度是描述树结构的一个整体属性，影响所有操作的时间复杂度。
- 深度：
- 深度是指某一节点到根节点的边数。
- 深度是节点的特有属性，根节点的深度为0，其子节点深度依次加一。
- 平均深度：
- 平均深度是树中所有节点深度的平均值。
- 在完全平衡的树中，平均深度约为 \(\log
N\)，而在不平衡树中可能更大。
3. BST 操作的影响
4. 随机化 BST
- 随机插入顺序：
- 如果节点的插入顺序是随机的，树的高度和平均深度通常会保持在 \(\Theta(\log N)\)。
- 这种随机性减少了树结构的不平衡性，确保在插入和查找操作中较好的性能。
- 自平衡机制：
- 在一些实现中（如AVL树和红黑树），使用自平衡机制确保树的高度保持在对数级别。
- 这种机制包括在插入或删除后进行旋转操作，调整树的结构以保持平衡。
AVL树
下面是AVL树的具体实现，包括基本的插入、删除和旋转操作。AVL树是一种自平衡的二叉搜索树，它在每次插入或删除后通过旋转操作保持平衡。AVL树的每个节点都存储一个平衡因子，该因子是其左子树和右子树高度的差值。
AVL树的基本结构
1
2
3
4
5
6
7
8
9
10
11
| class AVLNode {
int key;
int height;
AVLNode left;
AVLNode right;
AVLNode(int key) {
this.key = key;
this.height = 1;
}
}
|
AVL树类
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
| class AVLTree {
private AVLNode root;
private int height(AVLNode node) {
return node == null ? 0 : node.height;
}
private int getBalance(AVLNode node) {
return node == null ? 0 : height(node.left) - height(node.right);
}
private AVLNode rightRotate(AVLNode y) {
AVLNode x = y.left;
AVLNode T2 = x.right;
x.right = y;
y.left = T2;
y.height = Math.max(height(y.left), height(y.right)) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
return x;
}
private AVLNode leftRotate(AVLNode x) {
AVLNode y = x.right;
AVLNode T2 = y.left;
y.left = x;
x.right = T2;
x.height = Math.max(height(x.left), height(x.right)) + 1;
y.height = Math.max(height(y.left), height(y.right)) + 1;
return y;
}
public AVLNode insert(AVLNode node, int key) {
if (node == null) {
return new AVLNode(key);
}
if (key < node.key) {
node.left = insert(node.left, key);
} else if (key > node.key) {
node.right = insert(node.right, key);
} else {
return node;
}
node.height = Math.max(height(node.left), height(node.right)) + 1;
int balance = getBalance(node);
if (balance > 1 && key < node.left.key) {
return rightRotate(node);
}
if (balance < -1 && key > node.right.key) {
return leftRotate(node);
}
if (balance > 1 && key > node.left.key) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
if (balance < -1 && key < node.right.key) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}
public void inorder() {
inorderHelper(root);
}
private void inorderHelper(AVLNode node) {
if (node != null) {
inorderHelper(node.left);
System.out.print(node.key + " ");
inorderHelper(node.right);
}
}
public AVLNode getRoot() {
return root;
}
}
|
使用示例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public class Main {
public static void main(String[] args) {
AVLTree tree = new AVLTree();
tree.root = tree.insert(tree.root, 10);
tree.root = tree.insert(tree.root, 20);
tree.root = tree.insert(tree.root, 30);
tree.root = tree.insert(tree.root, 40);
tree.root = tree.insert(tree.root, 50);
tree.root = tree.insert(tree.root, 25);
System.out.println("中序遍历结果:");
tree.inorder();
}
}
|
说明
- 高度更新：每次插入后，需要更新节点的高度。
- 平衡因子计算：通过计算每个节点的平衡因子，判断树是否平衡。
- 旋转操作：根据不同的情况（左左、右右、左右、右左）进行相应的旋转，以保持AVL树的性质。
B-树
定义
B-树是一种自平衡的树数据结构，广泛用于数据库和文件系统中，以高效地存储和管理大量数据。它能够在内存和外存之间高效地读写数据。
性质
- 平衡性：所有叶子节点的深度相同，保证了树的平衡性。
- 节点结构：
- 每个节点可以包含多个键（项）和指向子节点的指针。
- 非叶节点的子节点数等于节点中项数加一。
- 每个节点的项数必须在一个预定义的范围内（例如，\(m/2,
m\)，其中m为每个节点的最大项数）。
- 有序性：每个节点内的项按升序排列，子节点指针的分布也遵循有序关系。
1. B-树的插入操作
- 插入过程：
- 从根节点开始，沿着树找到合适的叶子节点以插入新项。
- 如果该叶子节点的项数小于最大容量，直接插入。
- 如果叶子节点已满，需要分裂该节点：
- 找到中间值，将其上移到父节点。
- 创建一个新节点，将大于中间值的项移入新节点，并保持有序性。
- 如果父节点也满，则递归进行分裂，直到根节点。
- 分裂示例：
假设在一个具有最大项数3的B-树中，插入项\(7、2、5、1、6、3、8\)。当插入6后，节点满，分裂时：
- 中间值5上移到父节点。
- 原节点变为[\(1,
2\)]，新节点为[\(6, 7\)]。
2. B-树的性能
- 高度：最坏情况下，B-树的高度为 \(\Theta(\log_N
M)\)，其中N为每个节点的最大项数，M为树中项的总数。
- 操作复杂度：
contains 和 add 操作的时间复杂度为 \(O(\log_N M)\)。- 因为B-树节点通常存储在内存块中，能够减少磁盘I/O操作，提高查询效率。
具体实现示例（Java）
以下是B-树的简单实现，包括插入操作：
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
| import java.util.ArrayList;
import java.util.Collections;
class BTreeNode {
int[] keys;
int t;
BTreeNode[] children;
int n;
boolean leaf;
BTreeNode(int t, boolean leaf) {
this.t = t;
this.leaf = leaf;
this.keys = new int[2 * t - 1];
this.children = new BTreeNode[2 * t];
this.n = 0;
}
public void insertNonFull(int key) {
int i = n - 1;
if (leaf) {
while (i >= 0 && keys[i] > key) {
keys[i + 1] = keys[i];
i--;
}
keys[i + 1] = key;
n++;
} else {
while (i >= 0 && keys[i] > key) {
i--;
}
if (children[i + 1].n == 2 * t - 1) {
splitChild(i + 1, children[i + 1]);
if (keys[i + 1] < key) {
i++;
}
}
children[i + 1].insertNonFull(key);
}
}
public void splitChild(int i, BTreeNode y) {
BTreeNode z = new BTreeNode(y.t, y.leaf);
z.n = t - 1;
for (int j = 0; j < t - 1; j++) {
z.keys[j] = y.keys[j + t];
}
if (!y.leaf) {
for (int j = 0; j < t; j++) {
z.children[j] = y.children[j + t];
}
}
y.n = t - 1;
for (int j = n; j >= i + 1; j--) {
children[j + 1] = children[j];
}
children[i + 1] = z;
for (int j = n - 1; j >= i; j--) {
keys[j + 1] = keys[j];
}
keys[i] = y.keys[t - 1];
n++;
}
}
class BTree {
BTreeNode root;
int t;
BTree(int t) {
this.root = null;
this.t = t;
}
public void insert(int key) {
if (root == null) {
root = new BTreeNode(t, true);
root.keys[0] = key;
root.n = 1;
} else {
if (root.n == 2 * t - 1) {
BTreeNode s = new BTreeNode(t, false);
s.children[0] = root;
s.splitChild(0, root);
int i = 0;
if (s.keys[0] < key) {
i++;
}
s.children[i].insertNonFull(key);
root = s;
} else {
root.insertNonFull(key);
}
}
}
public void inorder() {
if (root != null) {
inorderHelper(root);
}
}
private void inorderHelper(BTreeNode node) {
for (int i = 0; i < node.n; i++) {
if (!node.leaf) {
inorderHelper(node.children[i]);
}
System.out.print(node.keys[i] + " ");
}
if (!node.leaf) {
inorderHelper(node.children[node.n]);
}
}
}
|
使用示例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public class Main {
public static void main(String[] args) {
BTree bTree = new BTree(3);
bTree.insert(10);
bTree.insert(20);
bTree.insert(5);
bTree.insert(6);
bTree.insert(12);
bTree.insert(30);
bTree.insert(7);
bTree.insert(17);
System.out.println("B-树的中序遍历结果:");
bTree.inorder();
}
}
|
说明
- 插入方法：
insert方法处理根节点分裂，并在适当位置插入新键。
- 分裂操作：
splitChild方法负责将满节点分裂，并保持B-树的性质。
- 中序遍历：中序遍历用于验证B-树的有序性。
红黑树（Red-Black Trees）
1. 红黑树性质
红黑树是一种自平衡的二叉搜索树（BST），其节点颜色（红色或黑色）帮助保持树的平衡。红黑树遵循以下性质：
- 根节点为黑色：树的根节点始终是黑色。
- 叶子节点为黑色：所有的叶子节点（NIL或空节点）都被视为黑色。
- 红色节点的子节点必须是黑色：如果一个节点是红色，则其两个子节点必须是黑色，避免出现两个红色节点相邻。
- 黑色平衡：从任何节点到其每个叶子节点的所有路径都包含相同数量的黑色节点。这保证了树的高度平衡。
2. 旋转操作
旋转操作是维护红黑树平衡的重要手段，主要有两种旋转方式：
左旋转（rotateLeft）
将节点G的右子节点P成为新根，G成为P的左子节点。
1
2
3
4
5
6
| private Node rotateLeft(Node h) {
Node x = h.right;
h.right = x.left;
x.left = h;
return x;
}
|
右旋转（rotateRight）
将节点G的左子节点P成为新根，G成为P的右子节点。
1
2
3
4
5
6
| private Node rotateRight(Node h) {
Node x = h.left;
h.left = x.right;
x.right = h;
return x;
}
|
3. 平衡树的实现
在插入过程中，红黑树通过旋转和颜色调整来保持平衡。插入的步骤如下：
- 插入新节点：遵循二叉搜索树的性质，将新节点插入到合适的位置。
- 调整颜色：根据插入节点的颜色和其父节点的颜色，调整节点颜色以满足红黑树性质。
- 旋转操作：如果在调整颜色后仍然不符合红黑树性质，进行必要的旋转操作。可能需要一次或多次旋转来恢复平衡。
红黑树的具体实现
以下是红黑树的简单实现，包括插入操作和旋转功能：
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
163
164
165
166
167
168
169
170
171
172
173
| class Node {
int key;
boolean color;
Node left, right, parent;
Node(int key) {
this.key = key;
this.color = true;
this.left = this.right = this.parent = null;
}
}
class RedBlackTree {
private Node root;
private Node TNULL;
public RedBlackTree() {
TNULL = new Node(0);
TNULL.color = false;
root = TNULL;
}
public void insert(int key) {
Node node = new Node(key);
node.parent = null;
node.left = TNULL;
node.right = TNULL;
Node y = null;
Node x = this.root;
while (x != TNULL) {
y = x;
if (node.key < x.key) {
x = x.left;
} else {
x = x.right;
}
}
node.parent = y;
if (y == null) {
root = node;
} else if (node.key < y.key) {
y.left = node;
} else {
y.right = node;
}
if (node.parent == null) {
node.color = false;
return;
}
if (node.parent.color == false) {
return;
}
fixInsert(node);
}
private void fixInsert(Node k) {
Node u;
while (k.parent.color == true) {
if (k.parent == k.parent.parent.left) {
u = k.parent.parent.right;
if (u.color == true) {
u.color = false;
k.parent.color = false;
k.parent.parent.color = true;
k = k.parent.parent;
} else {
if (k == k.parent.right) {
k = k.parent;
rotateLeft(k);
}
k.parent.color = false;
k.parent.parent.color = true;
rotateRight(k.parent.parent);
}
} else {
u = k.parent.parent.left;
if (u.color == true) {
u.color = false;
k.parent.color = false;
k.parent.parent.color = true;
k = k.parent.parent;
} else {
if (k == k.parent.left) {
k = k.parent;
rotateRight(k);
}
k.parent.color = false;
k.parent.parent.color = true;
rotateLeft(k.parent.parent);
}
}
if (k == root) {
break;
}
}
}
private Node rotateLeft(Node x) {
Node y = x.right;
x.right = y.left;
if (y.left != TNULL) {
y.left.parent = x;
}
y.parent = x.parent;
if (x.parent == null) {
this.root = y;
} else if (x == x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
y.left = x;
x.parent = y;
return y;
}
private Node rotateRight(Node x) {
Node y = x.left;
x.left = y.right;
if (y.right != TNULL) {
y.right.parent = x;
}
y.parent = x.parent;
if (x.parent == null) {
this.root = y;
} else if (x == x.parent.right) {
x.parent.right = y;
} else {
x.parent.left = y;
}
y.right = x;
x.parent = y;
return y;
}
public void inorder() {
inorderHelper(this.root);
}
private void inorderHelper(Node node) {
if (node != TNULL) {
inorderHelper(node.left);
System.out.print(node.key + " ");
inorderHelper(node.right);
}
}
}
|
使用示例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public class Main {
public static void main(String[] args) {
RedBlackTree rbt = new RedBlackTree();
rbt.insert(55);
rbt.insert(40);
rbt.insert(65);
rbt.insert(30);
rbt.insert(50);
rbt.insert(60);
rbt.insert(70);
System.out.println("红黑树的中序遍历结果:");
rbt.inorder();
}
}
|
说明
- 节点类
(
Node)：定义了红黑树节点的结构，包括键、颜色、左、右子节点和父节点指针。
- 插入方法
(
insert)：插入新节点并调用fixInsert进行
调整。
- 旋转方法：实现了左旋转和右旋转。
- 遍历方法：实现了中序遍历以展示树的结构。
通过以上实现，红黑树能够有效维护平衡并保证操作的时间复杂度为 \(O(\log n)\)。
总结
- 平衡BST和红黑树都能在插入和查找操作中提供对数时间复杂度。
- B-树适用于存储大规模数据，尤其在磁盘存取时性能优越。
- 红黑树更适合内存中的动态数据集，因为它们可以高效地保持平衡。
