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