AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它。
特点:
1.本身首先是一棵二叉搜索树。
2.带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。
也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。
对于如何理解上面两个特点，我们可以先看个图：
这是一个标准的AVL树
如果现在要插入一个99的节点，一定得作为右孩子放在88的右边，如图
这就不是一个AVL树了
目前，左子树的高度为1，右子树高度为3，已经超过1了。根据旋转的逻辑，哪边的树低，就往哪个方向旋转。所以左旋转之后，如图
左旋转之后的AVL树
旋转之后，有两个关键点需要注意
1 77变成了根节点
2 77之前的左孩子75变成了66的右孩子
为什么会有上面的变化呢？
其实这跟AVL本身的结构特性相关，为了保持平衡，AVL树在做数据插入或者更新时，需要不停的进行旋转，本着最小路径原则，只有当77为根节点，才能维持这个平衡。大家自己可以试其它的节点，看77是不是最优解。另外一个就是77之前的左孩子75为什么就变成了66的新右孩子呢？那我们再看一下二叉树的基本条件，左节点一定比右节点小，当66成为77新的左孩子之后，75按照这个原则只能脱离77去找自己新的位置，最终只能作为66的右孩子。
上面说的两种情况其实是比较简单的左孩子的左子树（LL）,右孩子的右子树（RR）情况，下面我们说详细的说一下稍微复杂一点儿的左孩子的右子树（LR)及右孩子的左子树（RL)的情况。
左孩子的右子树：
LR
F作为新加入的节点，整棵树的自平衡就不存在了，最终要以E为中心点进行旋转，首先B节点进行左旋
B节点左旋
目前还是不平衡，A节点再进行右旋
A节点右旋
右孩子的左子树：
RL
F作为新加入的节点，整棵树的自平衡就不存在了，最终要以E为中心点进行旋转，首先 C节点进行右旋
C右旋
A节点再进行左旋
A节点左旋
如果LR与RL的情况，记住以新加节点的父节点为中心点进行旋转
最后汇总一下旋转的情形：
1 根节点的左孩子的左子树插入节点(LL)==》右旋
2 根节点的右孩子的右子树插入节点(RR)==》左旋
3 根节点的左孩子的右子树插入节点(LR)==》原来根结点的左孩子的右孩子作为新的根节点
4 根节点的右孩子的左子树插入节点(RL)==》原来根结点的右孩子的左孩子作为新的根节点
后面这两个比较复杂，需要仔细体会。
参考地址https://zhuanlan.zhihu.com/p/56066942
关于上面AVL树的特性，真实的应用场景可能已经不多。为了保持高度平横，他的变动效率较低。为了解决这个问题，红黑树就应运而生了。B站上有一个号称讲的最透彻的视频，大家感兴趣的可以去看看红黑树讲解
有6个特性：
属性1:红黑树必须是二叉搜索树。
属性2:根节点必须涂成黑色。
属性3:红色节点的子节点必须涂成黑色。(不应该有两个连续的红结点)。
属性4:在树的所有路径中，应该有相同数量的黑色节点。
属性#5:每个新节点必须用红色插入。
属性6:每个叶节点(如NULL节点)必须涂成黑色。
在红黑树中，每个新节点都必须以红色插入。红黑树中的插入操作与二叉搜索树中的插入操作相似。但是它是用颜色属性插入的。每次插入操作结束后，我们都需要检查红黑树的所有属性。如果所有的属性都满足，我们就进行下一个操作否则我们执行下面的操作使它成为红黑树。
1. 重新着色
2. 旋转
3.旋转后重新上色
红黑树中的插入操作使用以下步骤执行…
步骤1 -检查树是否为空。
步骤2 -如果树是空的，那么插入新节点作为根节点，颜色为黑色，并退出操作。
步骤3 -如果树不是空的，然后插入新节点为叶子节点，颜色为红色。
步骤4 -如果newNode的父结点为黑色，则退出操作。
步骤5 -如果newNode的父节点是红色的，那么检查parentnode的兄弟节点的颜色。
步骤6 -如果它是黑色或NULL，然后做适当的旋转和重新上色。
步骤7 -如果它是红色的，然后执行重新上色。重复相同的操作，直到树变成红黑树。
下面给一个例子，图片来源http://btechsmartclass.com/data_structures/ds_images/Red_Black_Tree_Creation.png
一棵红黑树的成功长成
以上关于红黑树的说明全部来源于http://btechsmartclass.com/data_structures/red-black-trees.html
网友评论