資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Go語言程式定義紅黑樹
在 Go 語言中，我們可以透過提供適當的結構和方法來建立紅黑樹。在這篇文章中，我們將編寫 Go 語言程式來定義紅黑樹。在這裡，根節點始終為黑色，其他節點可以根據其擁有的屬性為紅色或黑色。它用於各種操作，例如高效搜尋、插入和刪除。
演算法
步驟 1 − 匯入 fmt 和 “main” 作為必要的包
步驟 2 − 建立一個 RedBlackTree 結構體，其中包含一個欄位，該欄位提供對根節點的引用。
步驟 3 − 然後，建立一個 “Node” 結構體，其中包含四個欄位：值為 int 型別，顏色為 string 型別，指向左子節點和右子節點的指標為 Node 型別，以及指向父節點的指標。
步驟 4 − 實現 insert 函式以將節點插入樹中。
步驟 5 − 實現 fixInsert 方法以修復任何違反紅黑樹屬性的情況。
步驟 6 − 實現 getUncle 和 getGrandparent 方法分別返回叔節點和祖父節點
步驟 7 − 在 main 函式中，建立紅黑樹的物件，並使用該物件在樹中插入值
步驟 8 − 最後，呼叫 InorderTraversal 方法以排序順序顯示值
示例
在這個例子中，我們將編寫一個 Go 語言程式來定義紅黑樹，透過多次插入並展示其保持顏色屬性的特性，最後我們還對樹進行了“中序遍歷”。
package main
import "fmt"
type Node struct {
value int
color string
left, right *Node
parent *Node
}
type RedBlackTree struct {
root *Node
}
func NewRedBlackTree() *RedBlackTree {
return &RedBlackTree{}
}
func (t *RedBlackTree) Insert(value int) {
if t.root == nil {
t.root = &Node{value: value, color: "black"}
} else {
t.root.insert(value)
}
}
func (n *Node) insert(value int) {
if value < n.value {
if n.left == nil {
n.left = &Node{value: value, color: "red", parent: n}
n.left.fixInsert()
} else {
n.left.insert(value)
}
} else if value > n.value {
if n.right == nil {
n.right = &Node{value: value, color: "red", parent: n}
n.right.fixInsert()
} else {
n.right.insert(value)
}
}
}
func (n *Node) fixInsert() {
if n.parent == nil {
n.color = "black"
return
}
if n.parent.color == "black" {
return
}
uncle := n.getUncle()
grandparent := n.getGrandparent()
if uncle != nil && uncle.color == "red" {
n.parent.color = "black"
uncle.color = "black"
grandparent.color = "red"
grandparent.fixInsert()
return
}
if n == n.parent.right && n.parent == grandparent.left {
grandparent.rotateLeft()
n = n.left
} else if n == n.parent.left && n.parent == grandparent.right {
grandparent.rotateRight()
n = n.right
}
n.parent.color = "black"
grandparent.color = "red"
if n == n.parent.left {
grandparent.rotateRight()
} else {
grandparent.rotateLeft()
}
}
func (n *Node) getUncle() *Node {
if n.parent == nil || n.parent.parent == nil {
return nil
}
grandparent := n.parent.parent
if n.parent == grandparent.left {
return grandparent.right
}
return grandparent.left
}
func (n *Node) getGrandparent() *Node {
if n.parent != nil {
return n.parent.parent
}
return nil
}
func (n *Node) rotateLeft() {
child := n.right
n.right = child.left
if child.left != nil {
child.left.parent = n
}
child.parent = n.parent
if n.parent == nil {
n.parent = child
} else if n == n.parent.left {
n.parent.left = child
} else {
n.parent.right = child
}
child.left = n
n.parent = child
}
func (n *Node) rotateRight() {
child := n.left
n.left = child.right
if child.right != nil {
child.right.parent = n
}
child.parent = n.parent
if n.parent == nil {
n.parent = child
} else if n == n.parent.left {
n.parent.left = child
} else {
n.parent.right = child
}
child.right = n
n.parent = child
}
func (t *RedBlackTree) InorderTraversal() {
if t.root != nil {
t.root.inorderTraversal()
}
fmt.Println()
}
func (n *Node) inorderTraversal() {
if n != nil {
n.left.inorderTraversal()
fmt.Printf("%d ", n.value)
n.right.inorderTraversal()
}
}
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("The inorder traversal of this tree is:")
tree.InorderTraversal()
}
輸出
The inorder traversal of this tree is: 6 7 8 10 11 13
結論
在這篇文章中，我們檢查瞭如何藉助一個使用插入的示例在 Go 語言中定義紅黑樹。在這裡，我們探討了紅黑樹的結構和操作。我們還使用中序遍歷遍歷了樹。紅黑樹是一種自平衡二叉搜尋樹，它具有與其關聯的紅色和黑色顏色屬性。
更新於: 2023年7月5日
315 次瀏覽
廣告