作者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
1F：推 wasiseal:谢谢^^ 59.115.229.183 07/02