Re: [問題] AVL TREE

[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: 210.85.132.240
推 wasiseal:謝謝^^