Re: [問題] AVL TREE

[shesay (她說)]

簡單來說就是左右子樹node的大小
相差小於等於1

用下面的來當例子xD
把每個節點編號 由上到下從0開始
댊有平衡 2-1 = 1

                    D    0
                  /   \
                 L     R  1
                /
               L1          2




沒平衡 3-1 = 2
                     D    0
                   /   \
                  L     R  1
                 /
                L1          2
               /
              L2             3




※ 引述《dichia (回憶的牽絆)》之銘言：
: ※ 引述《wasiseal (11)》之銘言：
: :  請問這個TREE的特性是啥
: :  還有其定義的方式
: :  如何判別其為AVL TREE
: :  謝謝!!
:    AVL TREE，高度平衡二元樹。
:    定義：空樹是高度平衡樹，若T不是空樹且左右子樹分別為TL與TR
: 　　　　 若且唯若T是高度平衡樹，則須滿足以下兩個條件：
: 　　　　 1. TL和TR也是高度平衡樹。
: 　　　　 2. |hL-hR|<=1，其中hL和hR分別是TL和TR的高度。
:                    D
:                  /   \
:                 L     R
:             D→L的距離 = hL
:             D→R的距離 = hR
:         ＊ AVL樹可在O(logn)時間內完成插入、刪除或修改，且於插
: 　　　　　 入、刪除或修改後，所得的樹仍須保持為高度平衡二元樹

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 203.70.103.27
※ 編輯: shesay          來自: 203.70.103.27        (07/01 22:52)
→ wasiseal:謝謝啦~~這裡真棒阿!!