平衡二叉樹是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。

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

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

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

以上就是動力節(jié)點小編介紹的"讓我們簡單的看下什么是平衡二叉樹"，希望對大家有幫助，如有疑問，請在線咨詢，有專業(yè)老師隨時為您務(wù)。