[数据结构与算法]二叉查找树(BST)，平衡二叉树(AVL)，红黑树之间的区别

1. 3者的区别与联系

二叉树，二叉查找树(BST)，平衡二叉树(AVL)，红黑树之间的区别：

根据百度百科给出的定义，它们之间的关系可以用下图表示，平衡二叉树（平衡二叉查找树，AVL）和红黑树都是二叉查找树的一种，区别就是平衡二叉树严格平衡，红黑树是弱平衡。

而AVL树由于实现比较复杂，而且插入和删除性能差，在实际环境下的应用不如红黑树。

2. 二叉查找树（BST）

2.1 定义

左子树的值小于根节点的值，右子树的值全部大于根节点的值；左右子树分别都是一颗二叉查找树。（递归定义）

3.1.2 缺点

可能退化形成单链表，此时搜索效率降低为 O(n)

因为这个缺点，优化之后的平衡二叉查找树，解决了这个问题。

3.1.3 插入操作

若原二叉排序树为空，则直接插入结点；否则，若关键字k小于根结点值，则插入到左子树，若关键字k大于根结点值，则插入到右子树。

新插入的阶段一定是叶子结点。

3.1.4 删除操作

（1）被删除的结点为叶子结点，直接删除

（2）被删除的结点只有左或者只有右子树，用其子树顶替其位置

（3）若结点z有左、右两棵子树，则令z的直接后继（或直接前驱）替代z，然后从二叉排序树中删去这个直接后继（或直接前驱），这样就转换成了第一或第二种情况。

PS：这里的直接前驱和直接后继概念来自于中序遍历（左根右），因为二叉排序树的中序遍历就是一个递增的序列。

用直接后继替代（直接后继：右子树中最左下的点）

用直接前驱替代（直接前驱：左子树中最右下的结点）

f

3.2 平衡二叉树（AVL）

3.2.1 定义

全称是“平衡二叉查找树”，是结构平衡的“二叉查找树”。

结构平衡：树上任一结点的左子树和右子树的高度之差不超过1

节点的 平衡因子 = 左子树高度 - 右子树高度

执行插入和删除操作时，只要不满足上面条件，就需要通过旋转来保持平衡，由于是强平衡，所以旋转操作是十分耗时的，由此可以知道AVL树适合用于插入与删除次数较少的情况，但是查找较多的情况。

3.2.2 平均查找时间复杂度

可以证明含有n个结点的平衡二叉树的最大深度为
$$O(lo{g}_{2}n)$$
平衡二叉树的平均查找长度为
$$O(lo{g}_{2}n)$$
因此查找的平均时间复杂度为：
$$O(lo{g}_{2}n)$$

3.2.3 缺点

严格平衡，旋转十分耗时；由于要综合考虑查找和插入，删除的时间复杂度，所以还可以进一步优化。

3.2.4 插入操作

执行插入操作之后，有可能导致二叉树不是平衡的，所以需要进行旋转，来调整为平衡二叉树。

总共可以分为以下4中情况：

下面图中，都假设子树的高度为H

（1）LL 型

（2）RR 型

（3）LR 型平衡旋转（先左后右双旋转）

（4）RL 型平衡旋转（先右后左双旋转）

3.3 红黑树

一种自平衡的“二叉查找树”；

红黑树数一种“弱平衡”的二叉树，相较于要求严格平衡的AVL树来说，红黑树大致平衡的，同时引入了颜色这个性质，因此在红黑树上进行插入操作和删除操作引起结构变化时，只需要少量的颜色变换和旋转操作，就可以恢复红黑树的结构。

同时由于是大致平衡，红黑树查找的时间复杂度和AVL树是同一个数量级的，但是在插入和删除操作上有很大的优势，所以综合考虑查找，插入，删除的时间复杂度，红黑树是优于AVL的。

红黑树的定义

1. 任何一个节点都有颜色，黑色或者红色
2. 根节点是黑色的
3. 父子节点之间不能出现两个连续的红节点
4. 任何一个节点向下遍历到其子孙的叶子节点，所经过的黑节点个数必须相等
5. 空节点被认为是黑色的

关于红黑树的插入，删除图示可以参考这篇博客：
漫画：什么是红黑树？

参考资料：

红黑树-百度百科

平衡二叉查找树-百度百科

二叉搜索树-百度百科