資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告