二叉平衡树
回顾:二叉排序树的查找
二叉排序树的不平衡会影响查找效率,所有我们要尽量让二叉树的形态均衡.
AVL树(平衡二叉树)
-
必须是二叉排序树
-
左子树和右子树的高度之差的绝对值小于等于1
-
左子树和右子树也是平衡二叉排序树
平衡因子
该结点左子树与右子树的高度差.
平衡因子=结点左子树的高度-结点右子树的高度
判断平衡二叉树
对于一个右n个结点的AVL树,其高度保持再O(logn)数量级,ASLA也保持在O(logn)量级.
平衡调整办法1
有可能导致失衡,即出现平衡因子大于1的结点
如果在一颗AVLA树中插入一个新结点后造成失衡,则必须重新调整树的结构,让其恢复平衡
平衡调整的四种类型
A:失衡结点 不止一个失衡结点时,为最小失衡子树的结点
B:A结点的孩子,C结点的双亲.
C:插入新节点的子树.
调整原则:
- 降低高度
- 保持二叉排序树性质
