二叉树到二叉查找树，是为了查找数据的效率接近logN。
二叉查找树到平衡二叉查找树，是为了防止二叉查找树沦为链表。
平衡二叉查找树到红黑树，是为了降级增删改的调整代价。
红黑树调整有左旋，右旋的概念。
参考以下几篇微信内容：
【漫画】以后在有面试官问你AVL树，你就把这篇文章扔给他
背景
西天取经的路上，一样上演着编程的乐趣.....
image
image
image
image
image
1、若它的左子树不为空，则左子树上所有的节点值都小于它的根节点值。
2、若它的右子树不为空，则右子树上所有的节点值均大于它的根节点值。
3、它的左右子树也分别可以充当为二叉查找树。
例如：
image
image
image
例如，我现在想要查找数值为14的节点。由于二叉查找树的特性，我们可以很快着找到它，其过程如下：
1、和根节点9比较
image
2、由于 14 > 9，所以14只可能存在于9的右子树中，因此查看右孩子13
image
3、由于 14 > 13，所以继续查看13的右孩子15
image
4、由于 14 < 15，所以14只可能存在于15的左孩子中，因此查找15的左孩子14
image
5、这时候发现14正是自己查找的值，于是查找结束。
这种查找二叉树的查找正是二分查找的思想，可以很快着找到目的节点，查找所需的最大次数等同于二叉查找树的高度。
在插入的时候也是一样，通过一层一层的比较，最后找到适合自己的位置。
image
image
image
初始的二叉查找树只有三个节点：
image
然后我们按照顺序陆续插入节点 4，3，2，1，0。插入之后的结构如下：
image
image
image
image
image
image
image
这是一种比查找二叉树还特别的树哦，这种树就可以帮助我们解决二叉查找树刚才的那种所有节点都倾向一边的缺点的。具有如下特性：
-
具有二叉查找树的全部特性。
-
每个节点的左子树和右子树的高度差至多等于1。
例如：图一就是一颗AVL树了，而图二则不是(节点右边标的是这个节点的高度)。
image
image
对于图二，因为节点9的左孩子高度为2，而右孩子高度为0。他们之间的差值超过1了。
这种树就可以保证不会出现大量节点偏向于一边的情况了。
image
听起来这种树还不错，可以对于图1，如果我们要插入一个节点3，按照查找二叉树的特性，我们只能把3作为节点4的左子树插进去，可是插进去之后，又会破坏了AVL树的特性，那我们那该怎么弄？
image
右旋
我们在进行节点插入的时候，可能会出现节点都倾向于左边的情况，例如：
image
我们把这种倾向于左边的情况称之为 左-左型。这个时候，我们就可以对节点9进行右旋操作，使它恢复平衡。
image
即：顺时针旋转两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子
再举个例子：
image
节点4和9高度相差大于1。由于是左孩子的高度较高，此时是左-左型，进行右旋。
image
这里要注意，节点4的右孩子成为了节点6的左孩子了
我找了个动图，尽量这个动图和上面例子的节点不一样。
image
左旋
左旋和右旋一样，就是用来解决当大部分节点都偏向右边的时候，通过左旋来还原。例如：
image
我们把这种倾向于右边的情况称之为** 右-右型**。
我也找了一张动图。
image
例子讲解
image
image
初始状态如下：
image
然后我们主键插入如下数值：1,4,5,6,7,10,9,8
插入 1
image
左-左型，需要右旋调整。
image
插入4
image
继续插入 5
image
右-右型，需要左旋转调整。
image
继续插入6
image
右-右型，需要进行左旋
image
继续插入7
image
右-右型，需要进行左旋
image
继续插入10
image
继续插入9
image
出现了这种情况怎么办呢?对于这种 **右-左型 **的情况，单单一次左旋或右旋是不行的，下面我们先说说如何处理这种情况。
image
这种我们就把它称之为 右-左 型吧。处理的方法是先对节点10进行右旋把它变成右-右型。
image
然后在进行左旋。
image
所以对于这种 右-左型的，我们需要进行一次右旋再左旋。
同理，也存在 左-右型的，例如：
image
对于左-右型的情况和刚才的 右-左型相反，我们需要对它进行一次左旋，再右旋。
image
回到刚才那道题
image
对它进行右旋再左旋。
image
到此，我们的插入就结束了。
image
image
总结一下
在插入的过程中，会出现一下四种情况破坏AVL树的特性，我们可以采取如下相应的旋转。
1、左-左型：做右旋。
2、右-右型：做左旋转。
3、左-右型：先做左旋，后做右旋。
4、右-左型：先做右旋，再做左旋。
不知道大家发现规律没，这个规则还是挺好记。
image
image
image
image
网友评论