資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Go 語言實現 Treap 程式
本文將探討使用兩種不同方法在 Go 語言中實現 Treap 資料結構。Treap 是二叉搜尋樹和二叉堆的結合，使其成為一種高效的資料結構，用於維護有序元素集，同時確保平衡優先順序。第一種方法將利用遞迴方法構建和維護 Treap，而第二種方法將實現迭代方法。下面的示例展示了隨機二叉搜尋樹的建立和遍歷，
解釋
Treap 是兩種其他結構（二叉搜尋樹和二叉堆）的巧妙組合。這種組合為我們提供了一種按順序組織大量專案的方法，同時確保事物保持平衡和高效。我們在下面的圖中表示了一個 Treap：
Value-Priority Pairs: (Value:Priority)
(10:8)
/ \
(5:15) (20:10)
/ \
(17:5) (25:2)
在上述結構中，每個節點包含值優先順序對。這裡的值以這樣的方式放置，即值保持二叉搜尋樹屬性，並且可以在優先順序上保持最大堆屬性。
語法
type TreapNode struct{ key, priority int; left, right *TreapNode }
語法表示用於使用遞迴方法實現 Treap 的 TreapNode 結構。TreapNode 包含三個欄位：鍵（節點的值）、優先順序（用於維護堆屬性的隨機生成的值）以及分別指向其左孩子和右孩子的左指標和右指標。這種遞迴實現確保 Treap 保持平衡並遵循二叉搜尋樹和二叉堆的屬性。
演算法
如果根節點為空，則建立一個具有給定鍵和優先順序的節點，並將其設定為 Treap 的根節點。
如果要插入的鍵小於當前節點的鍵，則遞迴地將其插入到左子樹中。
如果要插入的鍵大於當前節點的鍵，則遞迴地將其插入到右子樹中。
在插入到左子樹或右子樹之後，執行旋轉以維護 Treap 的堆屬性。如果當前節點的優先順序大於其左孩子的優先順序，則執行右旋轉。如果當前節點的優先順序大於其右孩子的優先順序，則執行左旋轉。
更新從根節點到插入節點路徑上的節點的大小或其他輔助資訊。
示例 1
在這個示例中，我們將使用 Go 語言中的遞迴插入在 Go 中實現 Treap。我們定義了一個 Node 結構來表示 Treap 中的每個節點。InsertRecursive 函式遞迴地將具有給定鍵和優先順序的節點插入到 Treap 中，同時維護 BST 和最大堆屬性。
package main
import (
"fmt"
"math/rand"
)
type Node struct {
key int
priority int
left *Node
right *Node
}
func NewNode(key, priority int) *Node {
return &Node{
key: key,
priority: priority,
}
}
func InsertRecursive(root *Node, key, priority int) *Node {
if root == nil {
return NewNode(key, priority)
}
if key < root.key {
root.left = InsertRecursive(root.left, key, priority)
if root.left.priority > root.priority {
root = rotateRight(root)
}
} else if key > root.key {
root.right = InsertRecursive(root.right, key, priority)
if root.right.priority > root.priority {
root = rotateLeft(root)
}
}
return root
}
func rotateRight(y *Node) *Node {
x := y.left
y.left = x.right
x.right = y
return x
}
func rotateLeft(x *Node) *Node {
y := x.right
x.right = y.left
y.left = x
return y
}
func InOrderTraversal(root *Node) {
if root != nil {
InOrderTraversal(root.left)
fmt.Printf("(%d, %d) ", root.key, root.priority)
InOrderTraversal(root.right)
}
}
func main() {
rand.Seed(42)
var root *Node
keys := []int{10, 5, 15, 3, 7, 12, 17}
for _, key := range keys {
priority := rand.Intn(100)
root = InsertRecursive(root, key, priority)
}
fmt.Println("In-Order Traversal:")
InOrderTraversal(root)
}
輸出
In-Order Traversal: (3, 50) (5, 87) (7, 23) (10, 5) (12, 45) (15, 68) (17, 57)
示例 2
在這個示例中，我們將使用 Go 語言中的迭代插入在 Go 中實現 Treap。Node 結構和 InsertIterative 函式與遞迴方法類似，但我們使用迭代方法（使用迴圈和堆疊）來在插入過程中維護 BST 和最大堆屬性。
package main
import (
"fmt"
"math/rand"
)
type Node struct {
key int
priority int
left *Node
right *Node
}
func NewNode(key, priority int) *Node {
return &Node{
key: key,
priority: priority,
}
}
func InsertIterative(root *Node, key, priority int) *Node {
newNode := NewNode(key, priority)
var parent *Node
curr := root
for curr != nil && curr.priority >= priority {
parent = curr
if key < curr.key {
curr = curr.left
} else {
curr = curr.right
}
}
if parent == nil {
root = newNode
} else if key < parent.key {
parent.left = newNode
} else {
parent.right = newNode
}
return root
}
func InOrderTraversal(root *Node) {
if root != nil {
InOrderTraversal(root.left)
fmt.Printf("(%d, %d) ", root.key, root.priority)
InOrderTraversal(root.right)
}
}
func main() {
rand.Seed(42)
var root *Node
keys := []int{10, 5, 15, 3, 7, 12, 17}
for _, key := range keys {
priority := rand.Intn(100)
root = InsertIterative(root, key, priority)
}
fmt.Println("In-Order Traversal:")
InOrderTraversal(root)
}
輸出
In-Order Traversal: (3, 50) (5, 87) (12, 45) (15, 68) (17, 57)
現實生活中的應用
作業系統中的動態優先順序佇列
作業系統通常需要管理具有不同優先順序的程序或任務。Treap 資料結構可用於有效地管理動態優先順序佇列。每個程序/任務都表示為 Treap 中的一個節點，其中鍵對應於優先順序，優先順序對應於堆屬性。這使得能夠快速插入、刪除和檢索具有最高優先順序的程序。隨著優先順序的動態變化，Treap 的自平衡屬性確保高效處理高優先順序任務，使其成為多工作業系統中排程演算法的合適選擇。
廣告平臺中的線上廣告投放
在線上廣告平臺中，需要根據出價金額、相關性和使用者參與度等各種因素來投放和展示廣告給使用者。可以使用 Treap 來管理廣告展示的順序。每個廣告都表示為一個節點，出價金額作為鍵，隨機生成的值作為優先順序。這確保了出價較高的廣告具有優先順序，同時在投放中提供一定程度的隨機性，從而實現公平的廣告輪播。
結論
本文展示了使用兩種不同方法（遞迴和迭代）在 Go 中實現 Treap 的示例。Treap 有效地結合了二叉搜尋樹和二叉堆的屬性，提供了一個具有平衡優先順序的有序元素集。遞迴方法提供了一種構建和維護 Treap 的直接方法，而迭代方法優化了大型資料集的效能。
96 次瀏覽
