資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究資料結構中的錦標賽樹、獲勝樹和失敗樹
在這裡，我們將瞭解錦標賽樹、獲勝樹和失敗樹。錦標賽樹是一個完全二叉樹，它有 n 個外部節點和 n - 1 個內部節點。外部節點代表選手，內部節點代表兩名選手比賽的獲勝者。這棵樹也被稱為選擇樹。
錦標賽樹有一些特性。如下所示：
這棵樹是根節點的。因此，樹中的連結和從父節點到子節點的有向路徑，並且有一個唯一的元素沒有父節點。
父節點的值小於或等於該節點，對於任何比較運算子，只要父節點和子節點的相對值在整棵樹中保持不變，就可以使用。
節點數不是 2 的冪的樹包含空洞。空洞可以出現在樹中的任何位置。
這棵樹是二叉堆的適當泛化。
根節點將代表錦標賽的整體獲勝者。
錦標賽樹有兩種型別：
獲勝樹
失敗樹
獲勝樹
獲勝樹是一個完全二叉樹，其中每個節點都代表其兩個子節點中較小或較大的節點，稱為獲勝樹。根節點儲存樹中最小的或最大的節點。錦標賽樹的獲勝者是在所有序列中第 n 個最小或最大的鍵。很容易看出，獲勝樹可以在 O(log n) 時間內形成。
**示例** - 假設有一些鍵，3、5、6、7、20、8、2、9。
失敗樹
失敗樹是針對 n 個選手的完全二叉樹，其中存在 n 個外部節點和 n - 1 個內部節點。比賽的失敗者儲存在內部節點中。但在此整體獲勝者儲存在 tree[0] 中。失敗者是一種替代表示，它在相應的節點儲存比賽的失敗者。失敗者的一個優點是，在輸出獲勝樹後重構樹，只需要檢查從葉子到根節點路徑上的節點，而不是該路徑上節點的兄弟節點。
**示例** - 要形成失敗樹，我們必須首先建立獲勝樹。
假設有一些鍵，10、2、7、6、5、9、12、1。因此，我們將首先建立最小獲勝樹。
現在，我們將每個內部節點中比賽的失敗者儲存起來。
更新於：2020 年 8 月 11 日
6K+ 次檢視
廣告