資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Go語言程式：向紅黑樹插入新節點
本文將編寫一個 Go 語言程式，用於向紅黑樹中插入節點。紅黑樹是一種自平衡二叉搜尋樹，具有以下特性：
每個節點要麼是紅色，要麼是黑色。
根節點總是黑色。
所有葉子節點都被視為黑色。
如果一個節點是紅色的，則它的兩個子節點都必須是黑色的。
從任意節點到其所有後代葉節點的每條路徑都包含相同數量的黑色節點。
演算法
建立一個名為“Node”的結構體，包含四個欄位：“key”（整型），“colour”（字串型），“left”（左子節點），“right”（右子節點）和“parent”（父節點，型別為 Node）。
建立一個名為“RedBlackTree”的結構體，包含一個“root”欄位，指向樹的根節點。
使用 Insert 方法向紅黑樹插入值。建立一個新的節點，指定其鍵值，並將顏色設定為“red”。
插入新節點後，使用 fixViolation 方法修復紅黑樹中可能出現的任何違規情況。
使用輔助方法 leftRotate 和 rightRotate 對樹節點進行左旋和右旋操作。
編寫主函式。建立一個新的 RedBlackTree 物件。使用 Insert 方法向樹中新增節點。
執行中序遍歷，並使用 fmt 包的 Println 函式輸出結果。
示例
在這個例子中，我們將編寫一個 Go 語言程式，使用 insert 方法向紅黑樹插入一個節點，然後列印中序遍歷結果來驗證插入演算法的正確性。
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("Inorder traversal of the Red-Black Tree:")
tree.Inorder_traversal(tree.root)
}
輸出
Inorder traversal of the Red-Black Tree: 2 3 6 7 8 10 11 13 18 22 26
結論
本文討論瞭如何在 Go 語言中向紅黑樹插入新節點。示例程式演示了使用 Insert 方法向紅黑樹插入新節點，然後列印中序遍歷結果的方法。這種方法簡單直接，可以根據問題的需要隨時使用。
更新於：2023年7月5日
瀏覽量：128
廣告