Golang 程序用于在红黑树中搜索节点
go programmingserver side programmingprogramming更新于 2025/5/15 20:07:17
在红黑树中搜索节点就是查找具有特定键或值的节点。在红黑树中的搜索类似于在标准二叉树中的搜索。在本文中，我们将编写 Go 语言程序来在红黑树中搜索节点。它是一种具有着色属性的自平衡二叉搜索树，其中根节点始终为黑色，其他节点根据属性为红色或黑色。这棵树使用旋转来保持插入和删除过程中的平衡。
属性
每个节点要么是红色，要么是黑色
根节点始终为黑色
所有叶子都被视为黑色
如果一个节点是红色的，那么它的两个子节点都是黑色的
从节点到其后代叶子的每条路径都包含相同数量的黑色节点
语法
func NewRedBlackTree() *RedBlackTree { return &RedBlackTree{} }
创建红黑树。
func (t *RedBlackTree) Insert(data int) { // ... }
向树中插入一个包含数据的新节点。
func (t *RedBlackTree) leftRotate(node *Node) { // ... }
对树进行左旋转。
func (t *RedBlackTree) Search(key int) *Node { // ... }
搜索具有特定键值的节点。
算法
导入所需的包
创建一个类型为"Colour"的常量，将值"Red"和"Black"分别分配为 0 和 1。
定义数据结构创建一个名为"RedBlackTree"的结构，其中有一个名为"root"的字段指向根节点。
创建一个名为"NewRedBlackTree"的函数，该函数创建并返回红黑树结构的新实例。
示例 1
在下面的示例中，使用由根节点组成的结构定义了一棵红黑树。以下代码包含红黑树中的构造、插入和搜索操作，突出显示了数据结构的自平衡特性和快速搜索能力。
package main
import "fmt"
type Color int
const (
Red Color = 0
Black Color = 1
)
type Node struct {
data int
color Color
left, right *Node
parent *Node
}
type RedBlackTree struct {
root *Node
}
func NewRedBlackTree() *RedBlackTree {
return &RedBlackTree{}
}
func (t *RedBlackTree) Insert(data int) {
newNode := &Node{data: data, color: Red}
t.insertNode(newNode)
t.fixInsertion(newNode)
}
func (t *RedBlackTree) insertNode(newNode *Node) {
if t.root == nil {
t.root = newNode
return
}
current := t.root
var parent *Node
for current != nil {
parent = current
if newNode.data < current.data {
current = current.left
} else if newNode.data > current.data {
current = current.right
} else {
return
}
}
newNode.parent = parent
if newNode.data < parent.data {
parent.left = newNode
} else {
parent.right = newNode
}
}
func (t *RedBlackTree) fixInsertion(node *Node) {
for node.parent != nil && node.parent.color == Red {
if node.parent == node.parent.parent.left {
uncle := node.parent.parent.right
if uncle != nil && uncle.color == Red {
node.parent.color = Black
uncle.color = Black
node.parent.parent.color = Red
node = node.parent.parent
} else {
if node == node.parent.right {
node = node.parent
t.leftRotate(node)
}
node.parent.color = Black
node.parent.parent.color = Red
t.rightRotate(node.parent.parent)
}
} else {
uncle := node.parent.parent.left
if uncle != nil && uncle.color == Red {
node.parent.color = Black
uncle.color = Black
node.parent.parent.color = Red
node = node.parent.parent
} else {
if node == node.parent.left {
node = node.parent
t.rightRotate(node)
}
node.parent.color = Black
node.parent.parent.color = Red
t.leftRotate(node.parent.parent)
}
}
}
t.root.color = Black
}
func (t *RedBlackTree) leftRotate(node *Node) {
rightChild := node.right
node.right = rightChild.left
if rightChild.left != nil {
rightChild.left.parent = node
}
rightChild.parent = node.parent
if node.parent == nil {
t.root = rightChild
} else if node == node.parent.left {
node.parent.left = rightChild
} else {
node.parent.right = rightChild
}
rightChild.left = node
node.parent = rightChild
}
func (t *RedBlackTree) rightRotate(node *Node) {
leftChild := node.left
node.left = leftChild.right
if leftChild.right != nil {
leftChild.right.parent = node
}
leftChild.parent = node.parent
if node.parent == nil {
t.root = leftChild
} else if node == node.parent.left {
node.parent.left = leftChild
} else {
node.parent.right = leftChild
}
leftChild.right = node
node.parent = leftChild
}
func (t *RedBlackTree) Search(key int) *Node {
current := t.root
for current != nil {
if key == current.data {
return current
} else if key < current.data {
current = current.left
} else {
current = current.right
}
}
return nil
}
func main() {
tree := NewRedBlackTree()
tree.Insert(60)
tree.Insert(40)
tree.Insert(20)
tree.Insert(40)
tree.Insert(30)
search_key := 40
result := tree.Search(search_key)
if result != nil {
fmt.Printf("Node with value %d found\n", search_key)
} else {
fmt.Printf("Node with value %d not found\n", search_key)
}
}
输出
Node with value 40 found.
结论
在本文中，我们讨论了如何在红黑树中搜索节点。要搜索值，我们首先创建一棵红黑树，向其中插入一个带有数据的节点，然后搜索特定值。红黑树用于表示文件管理系统中的目录和文件，它可以用作调度程序中的优先级队列，可以对其进行修改以实现间隔树等等，这些是红黑树在 Go 语言中可以使用的少数应用。
