[問題] AVL TREE

[wasiseal (11)]

 請問這個TREE的特性是啥

 還有其定義的方式

 如何判別其為AVL TREE

 謝謝!!

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 59.115.229.183

> -------------------------------------------------------------------------- <

作者: dichia (回憶的牽絆) 看板: TransCSI
標題: Re: [問題] AVL TREE
時間: Fri Jul  1 22:22:45 2005

※ 引述《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: 210.85.132.240
推 wasiseal:謝謝^^
> -------------------------------------------------------------------------- <

作者: shesay (她說) 看板: TransCSI
標題: Re: [問題] AVL TREE
時間: Fri Jul  1 22:51:02 2005


簡單來說就是左右子樹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:謝謝啦~~這裡真棒阿!!