AVL树 | 笔记整理!
AVL树 | 笔记整理!
AVL树
结构体
1
2
3
4
5
6
| type AVLNode struct {
key int
left *AVLNode
right *AVLNode
height int
}
|
定义 AVL 树节点的结构体。每个节点包含一个键值、左子节点、右子节点和当前节点的高度。
辅助函数
newNode 函数用于创建一个新的 AVL 树节点，并初始化键值、左右子节点以及高度。
1
2
3
| func newNode(key int) *AVLNode {
return &AVLNode{key: key, left: nil, right: nil, height: 1}
}
|
getHeight 函数用于获取指定节点的高度。如果节点为空，则返回 0。
1
2
3
4
5
6
| func getHeight(node *AVLNode) int {
if node == nil {
return 0
}
return node.height
}
|
getBalance 函数用于计算指定节点的平衡因子，即左子树的高度减去右子树的高度。如果节点为空，则返回 0。
1
2
3
4
5
6
| func getBalance(node *AVLNode) int {
if node == nil {
return 0
}
return getHeight(node.left) - getHeight(node.right)
}
|
updateHeight 函数用于更新节点的高度。它计算节点的新高度，并将其更新为左右子树中较大的高度加 1。
1
2
3
| func updateHeight(node *AVLNode) {
node.height = 1 + max(getHeight(node.left), getHeight(node.right))
}
|
max 函数用于返回两个整数中较大的值。
1
2
3
4
5
6
| func max(a, b int) int {
if a > b {
return a
}
return b
}
|
findMinValue 函数用于找到以指定节点为根的子树中的最小值节点。它通过不断遍历左子节点，直到找到最左边的叶子节点。
1
2
3
4
5
6
7
| func findMinValue(node *AVLNode) *AVLNode {
cur := node
for cur.left != nil {
cur = cur.left
}
return cur
}
|
printAVLTree 函数用于打印 AVL 树的结构。它采用递归方式，先打印右子树，然后打印当前节点，最后打印左子树。通过增加制表符来表示树的层级。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| func printAVLTree(node *AVLNode, level int) {
if node == nil {
return
}
printAVLTree(node.right, level+1)
for i := 0; i < level; i++ {
fmt.Print("\t")
}
fmt.Printf("%d\n", node.key)
printAVLTree(node.left, level+1)
}
|
旋转操作
基础旋转
leftRotate 函数实现左旋操作。它将当前节点的右子节点旋转为当前节点的父节点，并更新节点的高度。
1
2
3
4
5
6
7
8
| func leftRotate(node *AVLNode) *AVLNode {
child := node.right
node.right = child.left
child.left = node
updateHeight(node)
updateHeight(child)
return child
}
|
rightRotate 函数实现右旋操作。它将当前节点的左子节点旋转为当前节点的父节点，并更新节点的高度。
1
2
3
4
5
6
7
8
| func rightRotate(node *AVLNode) *AVLNode {
child := node.left
node.left = child.right
child.right = node
updateHeight(node)
updateHeight(child)
return child
}
|
处理旋转
rotate 函数用于处理 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
| func rotate(node *AVLNode) *AVLNode {
bf := getBalance(node)
if bf > 1 {
if childBf := getBalance(node.left); childBf >= 0 {
return rightRotate(node)
} else {
node.left = leftRotate(node.left)
return rightRotate(node)
}
}
if bf < -1 {
if childBf := getBalance(node.right); childBf <= 0 {
return leftRotate(node)
} else {
node.right = rightRotate(node.right)
return leftRotate(node)
}
}
return node
}
|
插入
insert 函数用于向 AVL 树中插入一个新节点。它按照二叉搜索树的规则找到合适的位置，并更新节点的高度，然后执行旋转操作以保持树的平衡。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
func insert(root *AVLNode, key int) *AVLNode {
if root == nil {
return newNode(key)
}
if key < root.key {
root.left = insert(root.left, key)
} else if key > root.key {
root.right = insert(root.right, key)
} else {
return root
}
updateHeight(root)
return rotate(root)
}
|
删除
remove 函数用于从 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
|
func remove(root *AVLNode, key int) *AVLNode {
if root == nil {
return root
}
if key < root.key {
root.left = remove(root.left, key)
} else if key > root.key {
root.right = remove(root.right, key)
} else {
if root.left == nil || root.right == nil {
child := root.left
if root.right != nil {
child = root.right
}
if child == nil {
return nil
} else {
root = child
}
} else {
cur := findMinValue(root.right)
root.right = remove(root.right, cur.key)
root.key = cur.key
}
}
updateHeight(root)
return rotate(root)
}
|
测试代码
一个简单的测试代码，它演示了如何使用 AVL 树的插入和删除操作，并打印树的结构。首先，将一些节点插入树中，然后删除一些节点，并输出删除后的树结构。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| func main() {
var root *AVLNode
root = insert(root, 10)
root = insert(root, 20)
root = insert(root, 30)
root = insert(root, 40)
root = insert(root, 50)
root = insert(root, 25)
fmt.Println("插入节点后的树结构：")
printAVLTree(root, 0)
root = remove(root, 30)
root = remove(root, 40)
fmt.Println("删除节点后的树结构：")
printAVLTree(root, 0)
}
|