AVL树/红黑树实现及map与set的封装
本帖最后由 Shaw0xyz 于 2024-6-23 15:47 编辑1. 引言
在计算机科学中，平衡二叉搜索树（BST）是一种保持树的高度接近最小以确保操作高效的数据结构。常见的平衡二叉搜索树有AVL树和红黑树。本文将详细介绍AVL树和红黑树的实现，并讨论如何将它们封装成map和set数据结构。
1.1 AVL树
AVL树是一种自平衡二叉搜索树，每个节点维护一个平衡因子，即其左右子树的高度差。AVL树通过旋转操作保持平衡，以确保插入、删除和查找操作的时间复杂度为O(log n)。
1.1.1 AVL树的基本操作
AVL树的基本操作包括插入、删除和查找。在插入和删除节点后，AVL树需要进行平衡操作。
(1) 插入操作
插入节点后，如果树失去平衡，需要通过单旋转或双旋转恢复平衡。
示例代码：
type AVLNode struct {
key int
height int
left *AVLNode
right*AVLNode
}
func height(node *AVLNode) int {
if node == nil {
return 0
}
return node.height
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func rightRotate(y *AVLNode) *AVLNode {
x := y.left
T2 := x.right
x.right = y
y.left = T2
y.height = max(height(y.left), height(y.right)) + 1
x.height = max(height(x.left), height(x.right)) + 1
return x
}
func leftRotate(x *AVLNode) *AVLNode {
y := x.right
T2 := y.left
y.left = x
x.right = T2
x.height = max(height(x.left), height(x.right)) + 1
y.height = max(height(y.left), height(y.right)) + 1
return y
}
func getBalance(node *AVLNode) int {
if node == nil {
return 0
}
return height(node.left) - height(node.right)
}
func insert(node *AVLNode, key int) *AVLNode {
if node == nil {
return &AVLNode{key: key, height: 1}
}
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 = 1 + max(height(node.left), height(node.right))
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
}
(2) 删除操作
删除节点后，同样需要进行旋转操作以保持平衡。
1.1.2 AVL树的查找操作
查找操作与普通二叉搜索树相同，通过比较节点值递归或迭代进行查找。
示例代码：
func search(node *AVLNode, key int) *AVLNode {
if node == nil || node.key == key {
return node
}
if key < node.key {
return search(node.left, key)
}
return search(node.right, key)
}
1.2 红黑树
红黑树是一种自平衡二叉搜索树，确保在插入和删除操作后保持近似平衡。红黑树通过颜色属性和旋转操作来保持平衡，插入和删除的时间复杂度为O(log n)。
1.2.1 红黑树的基本操作
红黑树的基本操作包括插入、删除和查找。
(1) 插入操作
插入节点后，通过重新着色和旋转操作恢复红黑树的性质。
(2) 删除操作
删除节点后，通过重新着色和旋转操作保持平衡。
1.2.2 红黑树的查找操作
查找操作与普通二叉搜索树相同，通过比较节点值递归或迭代进行查找。
1.3 map和set的封装
通过AVL树或红黑树实现map和set数据结构，可以确保键的有序性和操作的高效性。
1.3.1 map的实现
map是一种键值对数据结构，可以通过AVL树或红黑树实现。每个节点存储一个键值对，支持插入、删除和查找操作。
示例代码：
type MapNode struct {
key int
valueinterface{}
height int
left *MapNode
right*MapNode
}
func insertMapNode(node *MapNode, key int, value interface{}) *MapNode {
if node == nil {
return &MapNode{key: key, value: value, height: 1}
}
if key < node.key {
node.left = insertMapNode(node.left, key, value)
} else if key > node.key {
node.right = insertMapNode(node.right, key, value)
} else {
node.value = value
return node
}
node.height = 1 + max(height(node.left), height(node.right))
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
}
1.3.2 set的实现
set是一种无重复元素的数据结构，可以通过AVL树或红黑树实现。每个节点存储一个元素，支持插入、删除和查找操作。
示例代码：
type SetNode struct {
key int
height int
left *SetNode
right*SetNode
}
func insertSetNode(node *SetNode, key int) *SetNode {
if node == nil {
return &SetNode{key: key, height: 1}
}
if key < node.key {
node.left = insertSetNode(node.left, key)
} else if key > node.key {
node.right = insertSetNode(node.right, key)
} else {
return node
}
node.height = 1 + max(height(node.left), height(node.right))
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
}
2. 结论
通过本文的介绍，我们了解了AVL树和红黑树的基本原理及实现方法，并讨论了如何将它们封装成map和set数据结构。掌握这些高级数据结构和算法对于提高程序性能和解决复杂问题至关重要。希望这篇文章能对你理解和使用平衡二叉搜索树有所帮助。
/ 荔枝学姐de课后专栏 /
Hi！这里是荔枝学姐~
欢迎来到我的课后专栏
自然语言学渣 NLP摆烂姐
热衷于技术写作 IT边角料
AIGC & Coding & Linux ...
~互撩~ TG: @Shaw_0xyz
页:
[1]