数据结构:平衡二叉树AVL 作者:马育民 • 2022-07-04 22:11 • 阅读:10065 # 说明 平衡二叉树(Balanced Binary Tree 或 Height-Balanced Tree)又称为 **AVL** 树,其实就是一颗 **平衡的二叉排序树** AVL树或者是一颗空树,或者是具有下列性质的二叉排序树: **它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过 1 **。 ### 什么是平衡因子? 平衡二叉树上结点的 **平衡因子** BF(Balanced Factor) 定义为该结点的左子树深度减去它的右子树的深度,平衡二叉树上所有结点的平衡因子只可能是 -1,0,1。 ### 二叉排序树(二叉查找树) 解决 二叉排序树(二叉查找树)**不平衡问题** ,详见 [链接](https://www.malaoshi.top/show_1IX3cJo0to5t.html "链接") # 案例 ### 平衡二叉树 [![](/upload/0/0/1IX3cKo73aGO.png)](/upload/0/0/1IX3cKo73aGO.png) 上面的两个树就是典型的平衡二叉树,原因如下: - 首先它是一颗二叉排序树 - 其次每一个结点的平衡因子都是 -1,0,1三个数当中的一个。 比如上面的左图,红色的数字为结点的平衡因子,对于任意一个叶子结点而言,其左右孩子都为空,左子树的深度为 0 ,右子树的深度为 0 ,所以 AVL树当中的叶子结点的平衡因子都是 0 ;其他结点的平衡因子同样通过左子树深度减去右子树深度可以求得,比如上图中 左侧 的AVL树中,结点 3 的 左子树深度为 2,右子树深度为1 ,所以结点3的平衡因子就是 1 上图中 右侧 的AVL树中,结点 3 的左子树深度为2,右子树深度为3,则平衡因子为 `2 - 3 = -1` 。 ### 不平衡的二叉树 [![](/upload/0/0/1IX3cKqAkRrY.png)](/upload/0/0/1IX3cKqAkRrY.png) 上图中就是不平衡的二叉排序树,非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 原文出处:http://malaoshi.top/show_1IX3cKvWVkEq.html