学习笔记之平衡二叉树

发表于 更新于 分类于

平衡二叉树（AVL树）

平衡二叉树（self-balancing binary search tree or height-balanced binary search tree）, 是一种二叉排序树，其中每一个节点的左子树和右子树高度差至多为1.

左子树深度 - 右子树深度 = 平衡因子（BF, Balance Factor）

距离插入点最近，且平衡银子绝对值大于1的节点为跟的子树 - 最小不平衡子树

对比 红黑树1

右旋操作

二叉树P, 左孩子L : 将L的右子树变成P的左子树，P改为L的右子树, L 替换P变成根节点

rootBF >= 2

如图所示：

yx

左旋操作

二叉树P, 右孩子R:将R的左孩子变成P的右子树， P改为R的做左子树，R替换P变成根节点

rootBF <= -2

左右旋操作

右左情况： rootBF <= -2 , rightChildBF =1

右左旋操作

左右情况： rootBF >= 2, leftChildBF = 1

参考

https://zhuanlan.zhihu.com/p/94130997

  1. 查看 Post not found: 学习笔记之红黑树 红黑树↩︎