作者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)
1F:→ wasiseal:谢谢啦~~这里真棒阿!! 59.115.229.183 07/02