Golang 程序将新节点插入红黑树
go programmingserver side programmingprogramming更新于 2025/5/15 19:37:17
在本文中，我们将编写一个 Go 语言程序将节点插入红黑树。一棵红黑树。它是一个自平衡二叉搜索树，具有以下属性 -
每个节点要么是红色，要么是黑色
根节点始终为黑色
所有叶子都被视为黑色
如果一个节点是红色的，则它的两个子节点都将是黑色的
从节点到其后代叶子的每条路径都包含相同数量的黑色节点
算法
创建一个具有四个字段的"Node"结构:"key"类型为 int、"colour"类型为 string、"left"子节点、"right"子节点和"parent"类型为 Node。
创建一个 RedBlackTree 结构，其中"root"字段指向树的根节点。
要将值插入红黑树，请使用 Insert 技术。创建一个具有指定键和颜色"红色"的新节点。
插入新节点后，使用 fixViolation 技术解决红黑树中的任何潜在问题。
使用 leftRotate 和 rightRotate 等辅助方法对树节点进行左右旋转。
创建一个主要函数。创建一个新的红黑树对象。使用插入技术，将节点添加到树中。
执行中序遍历并使用 fmt 包的 Println 函数报告结果。
示例
在此示例中，我们将编写一个 Go 语言程序，使用插入方法将节点插入红黑树，然后打印中序遍历以证明插入算法的正确性。
package main
import "fmt"
type Node struct {
key int
color string
left *Node
right *Node
parent *Node
}
type RedBlackTree struct {
root *Node
}
func NewRedBlackTree() *RedBlackTree {
return &RedBlackTree{}
}
func (t *RedBlackTree) Insert(key int) {
node := &Node{
key: key,
color: "red",
}
if t.root == nil {
t.root = node
} else {
t.insertNode(t.root, node)
}
t.fixViolation(node)
}
func (t *RedBlackTree) insertNode(root, node *Node) {
if node.key < root.key {
if root.left == nil {
root.left = node
node.parent = root
} else {
t.insertNode(root.left, node)
}
} else {
if root.right == nil {
root.right = node
node.parent = root
} else {
t.insertNode(root.right, node)
}
}
}
func (t *RedBlackTree) fixViolation(node *Node) {
for node != t.root && 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.right_rotate(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.right_rotate(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) right_rotate(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) Inorder_traversal(node *Node) {
if node != nil {
t.Inorder_traversal(node.left)
fmt.Printf("%d ", node.key)
t.Inorder_traversal(node.right)
}
}
func main() {
tree := NewRedBlackTree()
tree.Insert(7)
tree.Insert(3)
tree.Insert(18)
tree.Insert(10)
tree.Insert(22)
tree.Insert(8)
tree.Insert(11)
tree.Insert(26)
tree.Insert(2)
tree.Insert(6)
tree.Insert(13)
fmt.Println("红黑树中序遍历:")
tree.Inorder_traversal(tree.root)
}
输出
红黑树中序遍历: 2 3 6 7 8 10 11 13 18 22 26
总结
本文我们讨论了如何在go语言中向红黑树插入新节点。这里我们通过Insert方法执行了一个向红黑树插入新节点的程序，然后打印中序遍历。这个方法简单直接，可以根据手头问题的需求随时使用。
