平衡樹的定義

Question

我只是想知道如果有人能夠爲我闡明平衡樹的定義。我有這樣的說法：「每棵子樹的樹是平衡的，兩棵子樹的高度相差至多一個。」

如果這是一個愚蠢的問題，但是這個定義是否適用於每一個節點一直到樹的葉子，或者只是到根的左邊和右邊的子樹，我猜想另外一個問題的方法是詢問樹的內部節點是否可能不平衡而整棵樹保持平衡？

Answer 1

有這兩件事之間沒有什麼區別。想想吧。

讓我們來簡單的定義，「一個正數，即使是零或數減二是即使「。這是否說8即使6是偶數？或者這是否說8即使6,4,2和0都是偶數？

沒有區別。如果說8即使6是偶數，也就是說6即使4是偶數。因此它也說4即使2是偶數。因此它說2即使是0也是。所以如果說8即使6是偶數，它（間接）也說8即使6,4,2和0是偶數。

這裏是一樣的東西。任何間接子樹都可以通過一系列直接子樹找到。因此，即使它僅直接應用於直接子樹，它仍然間接應用於所有子樹（並因此也適用於所有節點）。

Answer 2

約束通常遞歸地應用於每個子樹。也就是說，該樹是唯一的均衡，如果：

1. 左，右子樹的高度最多由一個不同，
2. 左子樹是平衡的，
3. 右子樹是平衡

根據這一點，接下來的樹是平衡：

 A 
/ \ 
    B  C 
/ /\ 
D  E F 
    / 
    G 

下一個是不平衡，因爲C的子樹2在其高度不同：

 A 
/ \ 
    B  C <-- difference = 2 
/ /
D  E 
    / 
    G 

這就是說，第一點的具體約束取決於樹的類型。上面列出的是AVL trees的典型值。例如，

Red-black trees施加更柔和的約束。

Answer 3

有幾種方法可以定義「平衡」。主要目標是保持所有節點的深度爲O(log(n))。

在我看來，你所談論的平衡條件是針對AVL樹。
這裏是AVL樹的平衡狀態的正式定義：

對於AVL的任一節點，它的左子樹的高度，距離其右子樹的高度相差最多 1。

下一個問題，什麼是 「高度」？

在二進制樹中的節點的「高度」是從該節點到葉的最長路徑的長度。

有一個奇怪，但常見的情況：

人們定義一個空樹的高度是(-1)。

例如，根的左孩子是null：

   A (Height = 2) 
     / \ 
(height =-1)  B (Height = 1) <-- Unbalanced because 1-(-1)=2 >1 
        \ 
        C (Height = 0) 

兩個例子來確定：

是，平衡樹例子：

 A (h=3) 
    / \ 
B(h=1)  C (h=2)   
/  / \ 
D (h=0) E(h=0) F (h=1) 
      /
       G (h=0) 

沒有， 不是平衡樹示例：

 A (h=3) 
    / \ 
B(h=0)  C (h=2)  <-- Unbalanced: 2-0 =2 > 1 
     / \ 
     E(h=1) F (h=0) 
     / \ 
     H (h=0) G (h=0)  

Answer 4

平衡樹是高度爲log（樹中元素的數量）的高度的樹。

height = O(log(n)) 
O, as in asymptotic notation i.e. height should have same or lower asymptotic 
growth rate than log(n) 
n: number of elements in the tree 

給出的定義「一棵樹是每個子樹的均衡是均衡和兩個子樹的高度最多由一個不同的」後面AVL樹。

由於AVL樹是平衡的，但並非所有平衡樹都是AVL樹，所以平衡樹不具有此定義，並且內部節點可能在其中不平衡。但是，AVL樹要求所有內部節點均衡。

Answer 5

平衡樹的目標是以最小遍歷（最小高度）到達葉。 樹的度數是分支的數量減1。 平衡樹可能不是二進制。