平衡二叉樹是什麼意思?

General 更新 2023年10月15日

什麼是平衡二叉樹

簡單說就是平衡二叉排序樹，也就是首先是二叉排序樹，然後還是平衡的。可以這樣理解

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

平衡二叉樹比其他二叉樹有什麼好處

首先平衡二叉樹是特殊的二叉排序樹，他的結點元素間存在著偏序關係。

其次相對於一般的二叉排序樹，平衡二叉樹的左右子樹的深度差也有不超過1層的約束。

這樣使得平衡樹是同種元素序列情況下的深度最小的二叉排序樹。這可以減少二叉樹元素查找的深度，從而提升平均查找效率。

平衡二叉樹定義

所謂平衡二叉樹是指樹中任一結點的左、右子樹高度大致相同。平衡二叉樹有很多種績著名的是由前蘇聯數學家Adelse—Velskil和Landis在1962年提出的，稱為AVL樹。平衡二叉樹(AVL樹)定義如下：平衡二叉樹或者是一棵空樹，或者是具有以下性質的二叉排序樹：(1)它的左子樹和右子樹的高度之差絕對值不超過1；(2)它的左子樹和右子樹都是平衡二叉樹。

數據結構平衡二叉樹圖9.12中的(e)和(g)啥意思

這個e和g就是在平衡二叉樹產生不平衡時，做了平衡化的旋轉得到

紅黑樹和平衡二叉樹區別

紅黑樹和之前所講的AVL樹類似，都是在進行插入和刪除操作時通過特定操作保持二叉查找樹的平衡，從而獲得較高的查找性能。自從紅黑樹出來後，AVL樹就被放到了博物館裡，據說是紅黑樹有更好的效率，更高的統計性能。

紅黑樹和AVL樹的區別在於它使用顏色來標識結點的高度，它所追求的是局部平衡而不是AVL樹中的非常嚴格的平衡。AVL樹的複雜比起紅黑樹來說簡直是小巫見大巫。紅黑樹是真正的變態級數據結構。

平衡二叉樹的平衡因子是什麼

基本上就是左子樹高了1層就加1，右子樹高就-1，然後左右一樣高就為0

為什麼要構建平衡二叉樹，的主要目的為? 5分

因為正常的二叉排序樹弄得不好查找性能近似於O(n)，使用平衡二叉樹則可以保證查找性能不超過1.5log2n

什麼是平衡二叉樹

平衡二叉樹，又稱AVL樹。它或者是一棵空樹，或者是具有下列性質的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的高度之差之差的絕對值不超過1.。

常用算法有：紅黑樹、AVL樹、Treap等。

平衡二叉樹的調整方法

平衡二叉樹是在構造二叉排序樹的過程中，每當插入一個新結點時，首先檢查是否因插入新結點而破壞了二叉排序樹的平衡性，若是，則找出其中的最小不平衡子樹，在保持二叉排序樹特性的前提下，調整最小不平衡子樹中各結點之間的鏈接關係，進行相應的旋轉，使之成為新的平衡子樹。具體步驟如下：

⑴ 每當插入一個新結點，從該結點開始向上計算各結點的平衡因子，即計算該結點的祖先結點的平衡因子，若該結點的祖先結點的平衡因子的絕對值均不超過1，則平衡二叉樹沒有失去平衡，繼續插入結點；

⑵ 若插入結點的某祖先結點的平衡因子的絕對值大於1，則找出其中最小不平衡子樹的根結點；

⑶ 判斷新插入的結點與最小不平衡子樹的根結點的關係，確定是哪種類型的調整；

⑷ 如果是LL型或RR型，只需應用扁擔原理旋轉一次，在旋轉過程中，如果出現衝突，應用旋轉優先原則調整衝突；如果是LR型或LR型，則需應用扁擔原理旋轉兩次，第一次最小不平衡子樹的根結點先不動，調整插入結點所在子樹，第二次再調整最小不平衡子樹，在旋轉過程中，如果出現衝突，應用旋轉優先原則調整衝突；

⑸ 計算調整後的平衡二叉樹中各結點的平衡因子，檢驗是否因為旋轉而破壞其他結點的平衡因子，以及調整後的平衡二叉樹中是否存在平衡因子大於1的結點。

平衡二叉樹概念

我覺得平衡二叉樹，不一定必須是二叉搜索樹。