平衡搜索二叉树对比(AVL、红黑树)

前言

0.1 二叉搜索树(BST)

• 根节点的值大于其左子树中任意一个节点的值，小于其右节点中任意一节点的值，这一规则适用于二叉查找树中的每一个节点。

0.2 二叉搜索树查找的效率是基于二叉搜索树的深度。

二叉树节点的插入是根据根节点的值，判断与当前插入值的大小，小的话向左，大的向右；如果左右各有节点，则重复左右节点的寻找。直到某个节点的左/右节点为空，插入。

举个例子：如果要插入11这个值，5 -> 7 -> 8 -> 9，找到9之后比9大，而且9的右子树值为null，所以插入9的右子树。

0.3 极端情况

极端情况下，树会变成一个链表，这样的话，查找的时间复杂度会变成O(n)。
平衡搜索二叉树就是为了解决这种情况

一、AVL树

• 1. 发明者 G. M. Adelson-Velsky和 Evgenii Landis(AVL)。
• 2. Balance Factor（平衡因子）：是它的左子树的高度减去它的右子树的高度（有时相反）。balance factor = {-1, 0, 1}。
• 3. 通过旋转操作来进行平衡（四种）

1.1 AVL的基础旋转操作

当某个节点的左右子树高度差在Balance Factor之外的时候，AVL就会进行子树的旋转操作从而达到平衡。

1.1.1 右右子树 —> 左旋

1.1.2 左左子树 —> 右旋

1.1.3 左右子树 —> 左右旋

先变成左左子树

再进行右旋

1.1.4 右左子树 —> 右左旋

先变成右右子树

再进行左旋

1.2 AVL的旋转操作

AVL如果存在子树的情况下，左/右旋转时，要把子树也带到另一个结点上

1.2.1 AVL带子树的左旋

1.2.2 AVL带子树的右旋

1.2.3 总结

二、红黑树

上述的AVL树可以保证每个结点的左右子树高度都能平衡。但是这样就需要每次插入都去判断当前结点是否是平衡的，有时候我们并不需要这种非常严格的平衡机制，只需要相对来说平衡即可。
于是我们就有了近似平衡二叉树这种数据结构，可以减少因为平衡二叉树而消耗的资源。

2.1 红黑树的定义

红黑树是一种近似平衡的二叉搜索树（Binary Search Tree），它能够确保任何一
个结点的左右子树的高度差小于两倍。

2.2 红黑树的性质

• 每个结点要么是红色，要么是黑色
• 根结点是黑色
• 每个叶结点（NIL结点，空结点）是黑色的。
• 不能有相邻接的两个红色结点
• 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。

尤其是最后两条性质，保证了红黑树的左右子树高度差不会超过两倍。

三、AVL与红黑树的对比