数据结构:平衡二叉树AVL

说明

平衡二叉树(Balanced Binary Tree 或 Height-Balanced Tree)又称为 AVL 树,其实就是一颗 平衡的二叉排序树

AVL树或者是一颗空树,或者是具有下列性质的二叉排序树:

它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过 1

什么是平衡因子?

平衡二叉树上结点的 平衡因子 BF(Balanced Factor) 定义为该结点的左子树深度减去它的右子树的深度,平衡二叉树上所有结点的平衡因子只可能是 -1,0,1。

二叉排序树(二叉查找树)

解决 二叉排序树(二叉查找树)不平衡问题 ,详见 链接

案例

平衡二叉树

上面的两个树就是典型的平衡二叉树,原因如下:

  • 首先它是一颗二叉排序树
  • 其次每一个结点的平衡因子都是 -1,0,1三个数当中的一个。

比如上面的左图,红色的数字为结点的平衡因子,对于任意一个叶子结点而言,其左右孩子都为空,左子树的深度为 0 ,右子树的深度为 0 ,所以 AVL树当中的叶子结点的平衡因子都是 0 ;其他结点的平衡因子同样通过左子树深度减去右子树深度可以求得,比如上图中 左侧 的AVL树中,结点 3 的 左子树深度为 2,右子树深度为1 ,所以结点3的平衡因子就是 1

上图中 右侧 的AVL树中,结点 3 的左子树深度为2,右子树深度为3,则平衡因子为 2 - 3 = -1

不平衡的二叉树

上图中就是不平衡的二叉排序树,非AVL树 。

上图 左侧 的树中,结点 6 的平衡因子为 2,该平衡因子是结点 6 左子树深度 3 减去右子树深度 1 所得

右侧 的树中,结点 6 的左子树深度 0 减去右子树深度 2,即为 -2

所以这两棵树都不是平衡二叉树

缺点

虽然平衡树解决了二叉查找树退化为近似链表的缺点,能够把查找时间控制在 O(logn),不过却不是最佳的

因为平衡树要求每个节点的左子树和右子树的 高度差至多等于1,这个要求实在是太严了,导致每次进行插入/删除节点的时候,几乎都会破坏平衡树的第二个规则,进而需要通过左旋和右旋来进行调整,使之再次成为一颗符合要求的平衡树

如果在插入、删除 很频繁 的场景中,平衡树需要频繁着进行调整,使性能降低,为了解决这个问题,于是提出 红黑树

参考

https://mp.weixin.qq.com/s/POX8QV9JFrRcAi-q-sJvOA
https://blog.csdn.net/ff_simon/article/details/101055134


原文出处:https://malaoshi.top/show_1IX3cKvWVkEq.html