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