数据结构 3 二叉查找树、红黑树、旋转与变色 理解与使用

这里再来复习一下二叉树的概念： 1. 每个节点下子元素不可超过两个，必须是0个或者一个或则两个 2. 二叉树是一种有序树。 理解了这些，我们这节要学习的内容就是有关于二叉查找树以及有关红黑树。 ## 二叉查找树 从这个名字，可以简单理解一下，他是为了解决什么被发明出来的。当然是查找了。因为名字自带查找。哈哈 开个玩笑。其实就是为了方便查找 *特征：**左边**子元素的值一定 <= 根节点* *特征：**右边**子元素的值一定 >= 根节点*  这就是一个典型的二叉查找树，比如我们查找一个`2`的元素位置 - 从根节点出发。5比2大，向着左节点4 - 4比2大，向着左节点 - 到达2的位置。 二叉查找树使用二分法的思想，将元素的位置唯一指定出来。查找最大次数=二叉树高度。 ### 二叉查找树缺陷 这么nice的二分法查找树，也不是没有缺陷的，世界上没有任何一个完美的东西。 所以，它的缺陷就是：如果我们的元素全部都是小于根节点的，那就变成这样的一个东西了。  这样，若是查找一个关于`7` 的元素，那么直接乱套了。直接和线性的数组就没有区别了。还是需要一个个遍历。 为了解决这种缺陷，下面这个东西出现了！ ## 红黑树 红黑树，是一种自我平衡的二叉查找树，说白了就是比二叉查找树更加Plus HashMap 再JDK 8当中。若链表长度超过8，则转换为红黑树。这也是一种特别好用的数据结构。所以说。`很重要` ### 特点 1. 节点要么是红色/黑色（名字中自带的属性） 2. 根节点是黑色的。 3. 叶子节点是`黑色的空节点` 4. 每个红色节点下面都有两个黑色节点 5. 从任意节点到每个叶子节点路径都都包含相同数目的黑色节点  ### 插入一个新值 在插入一个新值的时候，可能会使红黑树违反上面的5条规则，这个时候需要进行变色和旋转，我们逐一来讲解。 假设向当前红黑树插入一个 `21` 节点。  21比22小，所以只能放到22左边的位置。这里问题也就来了： - 为啥这个节点必须是`红色`的 而不能是黑色？ > 叶子节点必须是黑色空节点，所以，红色节点下必须有两个黑色节点，所以该节点必须是红色。 当然，又往上面看的话，你就会发现：22 是红色节点，红色节点必须包含两个黑色节点？ 这又冲突了。怎么办？ ## 节点的变色  这里尝试将22 节点变为黑色。这样的话，下面的规则满足了。但是从17号元素出发。到叶子节点。左边的线路有三个黑色节点，左边只有两个。 > 从任意节点到每个叶子节点路径都都包含相同数目的黑色节点  为了规则的完整性，继续变色。将25号元素变成红色  这时候还没有结束，因为 > 每个红色节点下面都有两个黑色节点  这样才算完全符合规则规范。 ## 节点的旋转方法 ### 左旋转 这里理解起来会很吃力。我先画个图。来理解这里面涉及到的内容。  1. 父节点被自己的右边孩子取代。 2. 而原来的父节点则需要成为被取代位置的左节点。 **最简单的方式是将子节点的左节点断开，挂到父节点上，翻转一下位置即可。** 1. 断开子节点的左边节点。  2. 将断开的这个节点挂到父节点上。  3. 旋转位置  很好理解吧！ ### 右旋转 顺时针旋转  1. 断开子节点的右孩子。  2. 挂到父节点上  3. 旋转位置。  **往那边旋转，就断开自己的那边的孩子，然后挂到父级，将节点变换一下位置即可。** ## 小结 其实红黑树的内容了解这么多就可以了。也没必要必须钻牛角尖。只需要懂得红黑树这种自平衡的主体思想即可。 ## 参考 https://mp.weixin.qq.com/s/jz1ajDUygZ7sXLQFHyfjWA