Treap

樹堆，在數據結構中也稱Treap，是指有一個隨機附加域滿足堆的性質的二叉搜索樹，其結構相當于以隨機數據插入的二叉搜索樹。其基本操作的期望時間復雜度為O(logn)。相對于其他的平衡二叉搜索樹，Treap的特點是實現(xiàn)簡單，且能基本實現(xiàn)隨機平衡的結構。

Treap基本信息

名稱 treap 性質 自平衡二叉查找樹
用途 實現(xiàn)關聯(lián)數組

模板

支持以下操作

1. 插入x數

2. 刪除x數(若有多個相同的數，因只刪除一個)

3. 查詢x數的排名(若有多個相同的數，因輸出最小的排名)

4. 查詢排名為x的數

5. 求x的前驅(前驅定義為小于x，且最大的數)

6. 求x的后繼(后繼定義為大于x，且最小的數)

Treap造價信息

市場價 信息價 詢價
材料名稱 規(guī)格/型號 市場價
（除稅）		 工程建議價
（除稅）		 行情 品牌 單位 稅率 供應商 報價日期
暫無數據
材料名稱 規(guī)格/型號 除稅
信息價		 含稅
信息價		 行情 品牌 單位 稅率 地區(qū)/時間
暫無數據
材料名稱 規(guī)格/需求量 報價數 最新報價
（元）		 供應商 報價地區(qū) 最新報價時間
暫無數據

我們可以看到，如果一個二叉排序樹節(jié)點插入的順序是隨機的，這樣我們得到的二叉排序樹大多數情況下是平衡的，即使存在一些極端情況，但是這種情況發(fā)生的概率很小，所以我們可以這樣建立一顆二叉排序樹，而不必要像AVL那樣旋轉，可以證明隨機順序建立的二叉排序樹在期望高度是O(logn)，但是某些時候我們并不能得知所有的帶插入節(jié)點，打亂以后再插入。所以我們需要一種規(guī)則來實現(xiàn)這種想法，并且不必要所有節(jié)點。也就是說節(jié)點是順序輸入的，我們實現(xiàn)這一點可以用Treap。

Treap=Tree+Heap

Treap是一棵二叉排序樹，它的左子樹和右子樹分別是一個Treap，和一般的二叉排序樹不同的是，Treap紀錄一個額外的數據，就是優(yōu)先級。Treap在以關鍵碼構成二叉排序樹的同時，還滿足堆的性質(在這里我們假設節(jié)點的優(yōu)先級大于該節(jié)點的孩子的優(yōu)先級)。但是這里要注意的是Treap和二叉堆有一點不同，就是二叉堆必須是完全二叉樹，而Treap可以并不一定是。

Treap常見問題

Treap相關推薦
  • 相關百科
  • 相關知識
  • 相關專欄