版權(quán)歸原作者所有,如有侵權(quán),請(qǐng)聯(lián)系我們

[科普中國(guó)]-平衡二叉查找樹

科學(xué)百科
原創(chuàng)
科學(xué)百科為用戶提供權(quán)威科普內(nèi)容,打造知識(shí)科普陣地
收藏

平衡二叉搜索樹(英語:Balanced Binary Tree)是一種結(jié)構(gòu)平衡的二叉搜索樹,即葉節(jié)點(diǎn)高度差的絕對(duì)值不超過1,并且左右兩個(gè)子樹都是一棵平衡二叉樹。

簡(jiǎn)介平衡二叉搜索樹(英語:Balanced Binary Tree)是一種結(jié)構(gòu)平衡的二叉搜索樹,即葉節(jié)點(diǎn)高度差的絕對(duì)值不超過1,并且左右兩個(gè)子樹都是一棵平衡二叉樹。它能在O()內(nèi)完成插入、查找和刪除操作,最早被發(fā)明的平衡二叉搜索樹為AVL樹。

常見的平衡二叉搜索樹有:

AVL樹

紅黑樹

Treap

節(jié)點(diǎn)大小平衡樹1

AVL樹在計(jì)算機(jī)科學(xué)中,AVL樹是最早被發(fā)明的自平衡二叉查找樹。在AVL樹中,任一節(jié)點(diǎn)對(duì)應(yīng)的兩棵子樹的最大高度差為1,因此它也被稱為高度平衡樹。查找、插入和刪除在平均和最壞情況下的時(shí)間復(fù)雜度都是。增加和刪除元素的操作則可能需要借由一次或多次樹旋轉(zhuǎn),以實(shí)現(xiàn)樹的重新平衡。AVL樹得名于它的發(fā)明者G. M. Adelson-Velsky和Evgenii Landis,他們?cè)?962年的論文《An algorithm for the organization of information》中公開了這一數(shù)據(jù)結(jié)構(gòu)。

節(jié)點(diǎn)的平衡因子是它的左子樹的高度減去它的右子樹的高度(有時(shí)相反)。帶有平衡因子1、0或 -1的節(jié)點(diǎn)被認(rèn)為是平衡的。帶有平衡因子 -2或2的節(jié)點(diǎn)被認(rèn)為是不平衡的,并需要重新平衡這個(gè)樹。平衡因子可以直接存儲(chǔ)在每個(gè)節(jié)點(diǎn)中,或從可能存儲(chǔ)在節(jié)點(diǎn)中的子樹高度計(jì)算出來。1

紅黑樹紅黑樹(英語:Red–black tree)是一種自平衡二叉查找樹,是在計(jì)算機(jī)科學(xué)中用到的一種數(shù)據(jù)結(jié)構(gòu),典型的用途是實(shí)現(xiàn)關(guān)聯(lián)數(shù)組。它是在1972年由魯?shù)婪颉へ悹柊l(fā)明的,他稱之為"對(duì)稱二叉B樹",它現(xiàn)代的名字是在Leo J. Guibas和Robert Sedgewick于1978年寫的一篇論文中獲得的。1

本詞條內(nèi)容貢獻(xiàn)者為:

李嘉騫 - 博士 - 同濟(jì)大學(xué)