AVL树
这是一种最老的平衡查找树
一棵AVL树是其每个结点的左子树和右子树的高度最多差1的二叉查找树
大致上讲,一棵AVL树的高度最多为
1.44 log(N+2)-1.328
这个算式实际上,只比 logN 稍微多一些,而相关的推导与斐波那契数密切相关,这里就点到为止。
AVL树靠两种算法保持平衡 单旋转和双旋转
插入有以下4种情况
- 对α的左儿子的左子树进行一次插入。
- 对α的左儿子的右子树进行一次插入。
- 对α的右儿子的左子树进行一次插入。
- 对α的右儿子的右子树进行一次插入。
单旋转是情况1,3
双旋转是情况2,4
代码部分
结点声明
1 | struct AvlNode{ |
计算结点高度
1 | int height(AvlNode *t) const{ |
插入
1 | void insert(const Comparable & x, AvlNode t){ |
单旋转
1 | void rotateWithLeftChild(AvlNode k2){ |
双旋转
1 | void doubleWithLeftChild(AvlNode k3){ |
- 本文作者: TangZ
- 本文链接: http://wstzj.github.io/2020/07/31/学习笔记-AVL树/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!