資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Go語言程式：實現紅黑樹的左旋轉
紅黑樹是一種自平衡二叉搜尋樹。旋轉是自平衡樹的基本操作之一。在向樹中插入和刪除節點時，執行旋轉操作以保持樹的特性。在這篇文章中，我們將編寫一個程式來使用指標以及節點值在紅黑樹中執行左旋轉。
紅黑樹的特性
每個節點要麼是紅色，要麼是黑色
根節點總是黑色
每個葉子節點都被認為是黑色
如果一個節點是紅色的，則它的兩個子節點都是黑色的
演算法
步驟 1 − 匯入 main 和 fmt 包。
步驟 2 − 檢查輸入節點和右子節點是否存在。如果不存在，則退出函式。
步驟 3 − 將節點的右子節點賦值給 pivot 變數。
步驟 4 − 現在將節點的右子節點更新為 pivot 的左子節點。
步驟 5 − 如果 pivot 的左子節點已存在，則將 pivot 的左子節點的父節點更新為該節點。
步驟 6 − 現在將 pivot 的父節點更新為節點的父節點。如果節點是根節點，則更新根節點引用。
示例 1：使用指標和節點交換
左旋轉是紅黑樹的基本方法，用於在保持元素順序的同時保持平衡。在這種方法中，我們將透過操作指標和交換節點引用來執行左旋轉。
package main
import (
"fmt"
)
type Node struct {
key int
color bool
left *Node
right *Node
parent *Node
}
var root *Node
func leftRotate(node *Node) {
if node == nil || node.right == nil {
return
}
pivot := node.right
node.right = pivot.left
if pivot.left != nil {
pivot.left.parent = node
}
pivot.parent = node.parent
if node.parent == nil {
// If the node was the root, update the root reference
root = pivot
} else if node == node.parent.left {
node.parent.left = pivot
} else {
node.parent.right = pivot
}
pivot.left = node
node.parent = pivot
}
func main() {
// Sample usage of leftRotate function
root = &Node{
key: 15,
color: false,
left: nil,
right: nil,
}
node1 := &Node{
key: 25,
color: true,
left: nil,
right: nil,
}
node2 := &Node{
key: 35,
color: true,
left: nil,
right: nil,
}
root.right = node1
node1.parent = root
node1.right = node2
node2.parent = node1
fmt.Println("Before left rotation:")
fmt.Println("Rootkey:", root.key)
fmt.Println("right child key of Root :", root.right.key)
fmt.Println(" right child key of right child key of root:", root.right.right.key)
leftRotate(root)
fmt.Println("\nAfter left rotation:")
fmt.Println("Rootkey:", root.key)
fmt.Println("left child key of Root's :", root.left.key)
}
輸出
Before left rotation: Rootkey: 15 right child key of Root : 25 right child key of right child key of root: 35 After left rotation: Rootkey: 25 left child key of Root's : 15
示例 2：使用節點值
左旋轉是紅黑樹的基本方法，用於在保持元素順序的同時保持平衡。在這種方法中，我們將透過複製節點的值而不是直接操作指標來執行左旋轉。
package main
import (
"fmt"
)
type Node struct {
key int
color bool
left *Node
right *Node
parent *Node
}
var root *Node
func leftRotate(node *Node) {
if node == nil || node.right == nil {
return
}
pivot := &Node{
key: node.right.key,
color: node.right.color,
left: node.left,
right: node.right.left,
parent: node,
}
if pivot.left != nil {
pivot.left.parent = pivot
}
node.right = pivot
if pivot.right != nil {
pivot.right.parent = pivot
}
if node.parent == nil {
root = pivot
} else if node == node.parent.left {
node.parent.left = pivot
} else {
node.parent.right = pivot
}
pivot.parent = node.parent
node.parent = pivot
}
func main() {
root = &Node{
key: 15,
color: false,
left: nil,
right: nil,
}
node1 := &Node{
key: 25,
color: true,
left: nil,
right: nil,
}
node2 := &Node{
key: 35,
color: true,
left: nil,
right: nil,
}
root.right = node1
node1.parent = root
node1.right = node2
node2.parent = node1
fmt.Println("Before left rotation:")
fmt.Println("Root key:", root.key)
fmt.Println("Right child key of Root:", root.right.key)
fmt.Println("Right child key of right child key of Root:", root.right.right.key)
leftRotate(root)
fmt.Println("\nAfter left rotation:")
fmt.Println("Root key:", root.key)
}
輸出
Before left rotation: Rootkey: 15 right child key of Root : 25 right child key of right child key of root: 35 After left rotation: Rootkey: 25 left child key of Root's : 15
結論
在這篇文章中，我們檢查瞭如何在 Go 語言中對紅黑樹執行左旋轉。我們探討了如何使用指標和節點交換以及使用節點值來執行此操作。在自平衡樹（如紅黑樹）上執行這些操作對於保持其平衡至關重要。
更新於：2023年7月6日
76 次檢視
廣告