隨機二叉樹(Treap) Java實現
摘要: Treap=Tree+Heap。Treap本身是一棵二叉搜索樹，它的左子樹和右子樹也分別是一個Treap，和一般的二叉搜索樹不同的是，Treap記錄一個額外的數據，就是優先級。Treap在以關鍵碼構成二叉搜索樹的同時，還按優先級來滿足堆的性質(在這里我們假設節點的優先級大于該節點的孩子的優先級)。但是這里要注意的是Treap和二叉堆有一點不同，就是二叉堆必須是完全二叉樹，而Treap可以并不一定是。
閱讀全文
posted @
2012-05-16 14:37 x.matthew 閱讀(4295) |
評論 (0) 編輯