【数据结构】AVL树(未完)

平衡因子 δ(T)

为了度量一颗二叉树的平衡,可以比较左右分支的高度差,如果差很大,则说明树不平衡。
定义一棵树的高度差如下:

δ(T)=|R||L|

其中, |T| 代表树 T 的高度,L 和 R 分别代表左右分支。
δ(T)=0 ,说明树是平衡的。通常 δ(T) 的绝对值越小,说明树越平衡。

AVL树的定义

如果一棵二叉搜索树的所有子树都满足如下条件,称之为AVL树。

δ(T)1

AVL树中所有 子树平衡因子的绝对值都不大于1,只可能是-1、0、1这三个值。

插入

向AVL树中插入一个新key,根节点的平衡因子的变化区间为[-1,1],树的高度最多增加1。
算法描述:
定义插入算法的结果为一对值 (T,ΔH) ,其中 T 为插入后的新树, ΔH 为树高度的增加值。令函数 first(pari) 取得一对值中的第一个元素,在二叉搜索树的插入算法上进行改动,定义AVL树的插入操作:

insert(T,k)=first(ins(T,k))
相关文章
相关标签/搜索