完整的二叉搜索樹和AVL樹的區別？

Question

完整的二叉搜索樹和AVL樹有區別嗎？舉個例子。

在google上搜索，但找到this。沒有太大的幫助

Answer 1

每個完整的二叉樹是一個AVl樹，但不一定是相反的方式。

一個完整的二叉樹是除了可能最後一個以外的每個層都被完全填充的一棵樹.AVL樹是每個節點的子樹是高度相差至多一個的AVL樹的樹。最大偏斜的AVL樹是斐波那契樹，它們通常不是完整的樹。下面是一棵樹的例子，它是一棵AVL樹，而不是一棵完整的二叉樹：

  . 
     / \ 
    .   . 
    /\  /\ 
    . .  . . 
    / //\ 
    .  . . . 
       /
       .