红黑树

什么是红黑树？

最近研究JDK源码的时候，发现TreeMap和TreeSet底层数据结构是红黑树，当然，TreeSet其实本质上就是Value为一个固定值的TreeMap。在JDK1.8以后，HashMap也用到了红黑树。 那红黑树到底是怎样的一种数据结构呢？相信大家都不是非常了解，我也去翻了好多的相关文章，发现一篇很有趣的漫画，可以帮助大家很快了解红黑树大概是怎样的一种数据结构，有哪些特点。 只是大概的介绍一下红黑树，详细的实现大家还是请参考相关的算法书籍。 以下内容转自： 漫画算法：什么是红黑树？ 1.左子树上所有结点的值均小于或等于它的根结点的值。 2.右子树上所有结点的值均大于或等于它的根结点的值。 3.左、右子树也分别为二叉排序树。 下图中这棵树，就是一颗典型的二叉查找树： 1.查看根节点9： 3.由于10 < 13，因此查看左孩子11： 假设初始的二叉查找树只有三个节点，根节点值为9，左孩子值为8，右孩子值为12： 2.根节点是黑色。 3.每个叶子节点都是黑色的空节点（NIL节点）。 4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点) 5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。 下图中这棵树，就是一颗典型的红黑树： 什么情况下会破坏红黑树的规则，什么情况下不会破坏规则呢？我们举两个简单的栗子： 1.向原红黑树插入值为14的新节点： 为了重新符合红黑树的规则，尝试把红色节点变为黑色，或者把黑色节点变为红色。 下图所表示的是红黑树的一部分，需要注意节点25并非根节点。因为节点21和节点22连续出现了红色，不符合规则4，所以把节点22从红色变成黑色： 但这样并不算完，因为凭空多出的黑色节点打破了规则5，所以发生连锁反应，需要继续把节点25从黑色变成红色： 逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子。说起来很怪异，大家看下图： 图中，身为右孩子的Y取代了X的位置，而X变成了自己的左孩子。此为左旋转。 顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子。大家看下图： 图中，身为左孩子的Y取代了X的位置，而X变成了自己的右孩子。此为右旋转。 首先，我们需要做的是变色，把节点25及其下方的节点变色： 这时候我们需要把节点13看做X，节点8看做Y，像刚才的示意图那样进行右旋转： 如果想要详细了解红黑树算法，可以参考这篇文章： Java数据结构和算法（十一）——红黑树

什么是红黑树

红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。红黑树是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。树的旋转当我们在对红黑树进行插入和删除等操作时，对树做了修改，那么可能会违背红黑树的性质。为了保持红黑树的性质，我们可以对相关结点做一系列的调整，通过对树进行旋转（例如左旋和右旋操作），即修改树中某些结点的颜色及指针结构，以达到对红黑树进行插入、删除结点等操作时，红黑树依然能保持它特有的性质（五点性质）。