平衡二叉樹(shù)是一棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)。

1、平衡二叉樹(shù)的常用實(shí)現(xiàn)方法有紅黑樹(shù)、AVL、替罪羊樹(shù)、Treap、伸展樹(shù)等。替罪羊樹(shù)是 計(jì)算機(jī)科學(xué)中，一種基于部分重建的自平衡二叉搜索樹(shù)。在替罪羊樹(shù)上，插入或刪除節(jié)點(diǎn)的平攤最壞 時(shí)間復(fù)雜度是O(log n)，搜索節(jié)點(diǎn)的最壞時(shí)間復(fù)雜度是O(log n)。在非平衡的 二叉搜索樹(shù)中，每次操作以后檢查操作路徑，找到最高的滿足max(size(son_L),size(son_R))>alpha*size(this)的結(jié)點(diǎn)，重建整個(gè)子樹(shù)。

2、紅黑樹(shù)是一種自平衡二叉查找樹(shù)，是在計(jì)算機(jī)科學(xué)中用到的一種數(shù)據(jù)結(jié)構(gòu)。紅黑樹(shù)這些節(jié)點(diǎn)中的某一個(gè)節(jié)點(diǎn)總是擔(dān)當(dāng)啟始位置的功能，它不是任何節(jié)點(diǎn)的兒子;我們稱(chēng)之為根節(jié)點(diǎn)或根。它有最多兩個(gè)"兒子"，都是它連接到的其他節(jié)點(diǎn)。所有這些兒子都可以有自己的兒子，以此類(lèi)推。這樣根節(jié)點(diǎn)就有了把它連接到在樹(shù)中任何其他節(jié)點(diǎn)的路徑。

3、AVL是最先發(fā)明的自平衡二叉查找樹(shù)算法。從AVL樹(shù)中刪除，可以通過(guò)把要?jiǎng)h除的節(jié)點(diǎn)向下旋轉(zhuǎn)成一個(gè)葉子節(jié)點(diǎn)，接著直接移除這個(gè)葉子節(jié)點(diǎn)來(lái)完成。因?yàn)樵谛D(zhuǎn)成葉子節(jié)點(diǎn)期間最多有l(wèi)og n個(gè)節(jié)點(diǎn)被旋轉(zhuǎn)，而每次AVL旋轉(zhuǎn)耗費(fèi)固定的時(shí)間，所以刪除處理在整體上耗費(fèi)O(log n) 時(shí)間。

以上就是動(dòng)力節(jié)點(diǎn)小編介紹的"讓我們簡(jiǎn)單的看下什么是平衡二叉樹(shù)"，希望對(duì)大家有幫助，如有疑問(wèn)，請(qǐng)?jiān)诰€咨詢，有專(zhuān)業(yè)老師隨時(shí)為您務(wù)。