数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Go语言程序：在红黑树中搜索节点
在红黑树中搜索节点是指查找具有特定键或值的节点。红黑树的搜索类似于标准二叉搜索树的搜索。在本文中，我们将编写 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 语言中可以使用红黑树的一些应用场景。
更新于: 2023年7月5日
96 次查看
广告