下载文档原格式
红黑树详解在本文，我将比较透彻地讲解红黑树。
本文适合那些有对二叉树有一定的基础，并且熟悉C语言的读者。
本文最主要的参考资料是《Introduction to Algorithms 3rd Edition》。
1.1 二叉查找树1.1.1 基本概念二叉查找树是在数据结构中比较重要的数据结构之一，从外部看它满足集合性质，具有查找，插入和删除的基本功能，同时还可以求最大值和最小值。
由于二叉查找树独特的性质，它特别适合用来存储动态集合。
定义：对于二叉树上的所有结点x，如果y是x的左子树，那么y.key ≤ x.key。
如果y 是x的右子树，那么y.key ≥ x.key，这样的二叉树就称为二叉查找树(Binary Search Tree)。
我们关心的二叉查找树的逻辑结构，下面的两棵二叉树：图1 二叉查找树。
(a)这一棵高度为3的二叉树，因为10比15小，所以10在15的左子树上；同理在以10为根的左子树里，7比10小所以7在左子树上，12在10为根的子树的右子树上；20在以15为根的右子树上。
(b)这是一棵高度是4的二叉查找树，它的所有key与图(a)是一样的。
在图(a)中，查找最坏的情况是7和12，它们需要经过3次比较才能找到，而图(b)最坏情况是20，需要经过4次比较才能找到。
要想二叉树的查找的花费时间小，我们尽可能让二叉树不出现类以于单链形态的二叉树，让树的高度尽量的低。
对于高度为h的二叉查找树，从树根对叶子最坏的情况是比较h 次。
也就是说，对于高度为h的二叉查找树的最坏查找情况的运行时间是O(h)。
二叉树的查找效率取决于树的高度。
1.1.2 操作二叉树做为动态集，它有查找、插入、删除、最大值、最小值、前驱和后继这些基本操作。
为了后序的方便，我们定义了结点和树，另外我们还用0表示空子树。
查找在二叉查找树中根据给定的key找到该结点。
由于二叉树的性质，我们就知道，如果目标key比当前结点的key要小，那么目标结点必定在当前结点的左子树上。
c语言红黑树遍历序算法红黑树是一种自平衡的二叉查找树，它具有良好的平衡性能，能够保持在较低的高度范围内。
在C语言中，我们可以使用递归或者非递归的方式来实现红黑树的遍历。
下面我将分别介绍中序遍历、前序遍历和后序遍历的算法。
1. 中序遍历算法：中序遍历的顺序是先遍历左子树，然后访问根节点，最后遍历右子树。
在C语言中，我们可以使用递归实现中序遍历：c.void inOrderTraversal(struct Node root) {。
if (root != NULL) {。
inOrderTraversal(root->left);printf("%d ", root->data);inOrderTraversal(root->right);}。
}。
2. 前序遍历算法：前序遍历的顺序是先访问根节点，然后遍历左子树，最后遍历右子树。
同样可以使用递归实现前序遍历：c.void preOrderTraversal(struct Node root) {。
if (root != NULL) {。
printf("%d ", root->data);preOrderTraversal(root->left);preOrderTraversal(root->right);}。
}。
3. 后序遍历算法：后序遍历的顺序是先遍历左子树，然后遍历右子树，最后访问根节点。
同样可以使用递归实现后序遍历：c.void postOrderTraversal(struct Node root) {。
if (root != NULL) {。
postOrderTraversal(root->left);postOrderTraversal(root->right);printf("%d ", root->data);}。
}。
另外，以上是使用递归实现的遍历算法，也可以使用非递归的方式来实现，利用栈来辅助实现遍历。
算法导论-8.红⿊树详解红⿊树是⼀种相当复杂的数据结构，⼀种能够保持平衡的⼆叉查找树。
如果条件极端，随机⽣成的⼆叉树可能就是⼀个单链表，深度为 $n$，⽽红⿊树的⾼度，即使在最坏情况下也是 $\Theta(n)$ ，红⿊树通过满⾜以下5条性质来保证这⼀点：1. 节点是红⾊或者⿊⾊的。
2. 根节点的⿊⾊的。
3. NIL节点时⿊⾊的。
4. 每个红⾊节点的左⼦节点和右⼦节点必定是⿊⾊的。
5. 任意叶⼦节点的⿊深度相等。
注：这⾥以及下⽂的叶⼦节点是指真正的有意义的“叶⼦节点”⽽不是NIL节点。
如：这是⼀颗红⿊树，注意所有NIL节点其实都是⼀个节点。
我仔细研究了红⿊树，并⾃⼰实现了它，这是⼀个多⽉来看《算法导论》给我带来成就感最⼤的⼀次。
我改进了之前⼆叉查找树的代码，使⽤⼆叉树-⼆叉查找树-红⿊树和⼆叉树节点-红⿊树节点的继承关系链；并且，为了增强算法复杂部分代码的可读性，我对部分功能函数实现了⼀些看上去有点累赘的重载。
这篇博⽂可能不会分析这些⽐较简单的重载，但是完整的代码可以下载（⽅便起见，我将实现和定义全部写在⼀个头⽂件中）。
这篇博⽂参考了《算法导论》第12、13章和维基百科的“红⿊树”词条，所⽤的⽰意图也来⾃于维基百科中，这⾥先作说明。
此外，这⼀篇仅分析红⿊树的实现，不设计章节后⾯的习题。
⼆叉树⼆叉树是最简单的，我提供了⼀些基本的功能。
我尽量使变量名和函数名不⾔⾃明，所以不会作过多解释。
先看⼆叉树节点：template <typename T> class xBinaryTreeNode{public:xBinaryTreeNode();xBinaryTreeNode(T val);T data;xBinaryTreeNode<T>* leftChild;xBinaryTreeNode<T>* rightChild;xBinaryTreeNode<T>* father;};template <typename T> xBinaryTreeNode<T>::xBinaryTreeNode(){leftChild = rightChild = father = NULL;}template <typename T> xBinaryTreeNode<T>::xBinaryTreeNode(T val){data = val;leftChild = rightChild = father = NULL;}然后看⼆叉树的声明：template <typename T> class xBinaryTree{public:xBinaryTree();xBinaryTreeNode<T>* getHead();bool isEmpty();bool doesExit(xBinaryTreeNode<T>* node);bool isRoot(xBinaryTreeNode<T>* node);bool hasLeftChild(xBinaryTreeNode<T>* node);bool hasRightChild(xBinaryTreeNode<T>* node);xBinaryTreeNode<T>** getSelfFromFather(xBinaryTreeNode<T>* node);xBinaryTreeNode<T>** getBrother(xBinaryTreeNode<T>* node);protected:xBinaryTreeNode<T>* nilNode;};有⼏点需要说明：nilNode是⼀个存在的“空节点”，是根节点（或称头结点）的⽗节点，也是所有叶⼦节点实际上的⼦节点。
红黑树系列，六篇文章于今日已经完成：1、教你透彻了解红黑树2、红黑树算法的实现与剖析3、红黑树的c源码实现与剖析4、一步一图一代码，R-B Tree5、红黑树插入和删除结点的全程演示6、红黑树的c++完整实现源码------------------------------一、红黑树的介绍先来看下算法导论对R-B Tree的介绍：红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red 或Black。
通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
前面说了，红黑树，是一种二叉查找树，既然是二叉查找树，那么它必满足二叉查找树的一般性质。
下面，在具体介绍红黑树之前，咱们先来了解下二叉查找树的一般性质：1.在一棵二叉查找树上，执行查找、插入、删除等操作，的时间复杂度为O（lgn）。
因为，一棵由n个结点，随机构造的二叉查找树的高度为lgn，所以顺理成章，一般操作的执行时间为O（lgn）。
//至于n个结点的二叉树高度为lgn的证明，可参考算法导论第12章二叉查找树第12.4节。
2.但若是一棵具有n个结点的线性链，则此些操作最坏情况运行时间为O（n）。
而红黑树，能保证在最坏情况下，基本的动态几何操作的时间均为O（lgn）。
ok，我们知道，红黑树上每个结点内含五个域，color，key，left，right，p。
如果相应的指针域没有，则设为NIL。
一般的，红黑树，满足以下性质，即只有满足以下全部性质的树，我们才称之为红黑树：1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。
（注：上述第3、5点性质中所说的NULL结点，包括wikipedia.算法导论上所认为的叶子结点即为树尾端的NIL指针，或者说NULL结点。
红黑树实现原理及应用技巧介绍红黑树作为一种自平衡的二叉查找树，具有高效的插入、删除和搜索操作。
它的实现原理以及应用技巧在算法和数据结构领域中具有重要的意义。
本文将介绍红黑树的实现原理，同时探讨一些应用中的技巧和注意事项。
一、红黑树的基本概念红黑树是一种二叉查找树，在普通的二叉查找树基础上增加了一组额外的规则，使得树保持平衡。
红黑树具有以下特点：1. 每个节点要么是红色，要么是黑色。
2. 根节点是黑色的。
3. 如果一个节点是红色的，则它的子节点必须是黑色的。
4. 从根节点到叶子节点或者空子节点的每条路径，必须包含相同数目的黑色节点。
5. 空子节点被视为黑色。
二、红黑树的实现原理红黑树的实现原理主要包括节点的插入、删除和搜索操作。
1. 插入操作在红黑树中插入一个节点时，首先按照二叉查找树的规则找到插入位置，将节点插入为叶子节点，并将其颜色设置为红色。
接下来，根据红黑树的规则进行调整，确保树仍然满足平衡性：- 如果插入节点的父节点是黑色，树保持平衡，插入操作完成。
- 如果插入节点的父节点是红色，需要进行颜色和结构的调整。
具体调整方式包括：- 如果插入节点的叔节点（父节点的兄弟节点）是红色，将父节点和叔节点的颜色改为黑色，祖父节点的颜色改为红色，然后将祖父节点设置为当前节点，重新进行调整；如果插入节点没有叔节点，或者叔节点是黑色，进行下一步操作。
- 如果插入节点的父节点是祖父节点的左子节点，插入节点是父节点的左子节点，进行右旋操作；如果插入节点是父节点的右子节点，先进行左旋操作，然后再进行右旋操作。
- 如果插入节点的父节点是祖父节点的右子节点，插入节点是父节点的右子节点，进行左旋操作；如果插入节点是父节点的左子节点，先进行右旋操作，然后再进行左旋操作。
最终，将根节点设为黑色，保证红黑树始终满足规则。
2. 删除操作在红黑树中删除一个节点时，也需要进行相应的调整，以保持树的平衡。
删除操作分为两种情况：被删除节点有零个或一个子节点，以及被删除节点有两个子节点。
红黑树算法原理与实现红黑树是一种自平衡二叉查找树，它能够保证查找、插入和删除操作最坏情况下的时间复杂度都为O(log n)，是一种十分高效的数据结构。
本文将对红黑树算法的原理和实现进行介绍，帮助读者深入了解红黑树的运作流程和应用场景。
一、红黑树的定义和性质红黑树和其他的自平衡二叉查找树（如AVL树）一样，能够自动调整树的结构以保证平衡，并且能够保持树中每个节点的黑高相等。
下面是红黑树的具体定义：（1）每个节点要么是红色，要么是黑色。
（2）根节点是黑色。
（3）每个叶子节点（NIL节点，空节点）都是黑色的。
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）任意一个节点到每个叶子节点所经过的黑色节点数都相同。
这些性质确保了红黑树的平衡，在插入和删除节点时能够自动平衡而不需要人工干预，从而保证了树的性能。
二、红黑树的基本操作红黑树的插入和删除操作是它最为关键和难点的部分，下面我们将针对这两个操作进行介绍。
（1）插入操作插入节点时，首先按照二叉查找树的方式将新节点插入到树中。
接下来需要进行的操作是将节点的颜色进行调整，保证该节点符合红黑树的五大性质。
如果插入的节点不满足性质（4），需要执行进行一系列颜色调整和旋转操作，使得节点重新满足红黑树性质。
一般情况下，情况分为两种：（a）情况1：插入的节点为根节点此时只需要将节点的颜色设置为黑色即可。
（b）情况2：插入的节点的父节点为红色此时需要进行一系列的旋转和颜色调整操作。
可以分为以下三种情况：①插入节点的叔叔节点是红色的，此时需要进行颜色调整和旋转。
②插入节点的叔叔节点是黑色的，并且插入节点为父节点的右子节点，此时需要进行左旋操作。
③插入节点的叔叔节点是黑色的，并且插入节点为父节点的左子节点，此时需要进行颜色调整、右旋操作。
（2）删除操作删除节点时，首先按照二叉查找树的方式删除节点。
接着需要对树进行自平衡操作，使之重新满足红黑树性质。
与插入操作相比，删除操作需要考虑更多的情况。
hashmap为什么8转成红⿊树_⾯试1：HashMap 的数据结构？A：哈希表结构（链表散列：数组+链表）实现，结合数组和链表的优点。
当链表长度超过 8 时，链表转换为红⿊树。
transient Node<K,V>[] table;2：HashMap 的⼯作原理？HashMap 底层是 hash 数组和单向链表实现，数组中的每个元素都是链表，由 Node 内部类（实现 Map.Entry<k,v style="margin: 0px; padding: 0px; max-width: 100%; box-sizing: border-box !important; word-wrap: break-word !important;">接⼝）实现，HashMap 通过 put & get ⽅法存储和获取。
</k,v>存储对象时，将 K/V 键值传给 put() ⽅法：①、调⽤ hash(K) ⽅法计算 K 的 hash 值，然后结合数组长度，计算得数组下标；②、调整数组⼤⼩（当容器中的元素个数⼤于 capacity * loadfactor 时，容器会进⾏扩容resize 为 2n）；③、i.如果 K 的 hash 值在 HashMap 中不存在，则执⾏插⼊，若存在，则发⽣碰撞；ii.如果 K 的 hash 值在 HashMap 中存在，且它们两者 equals 返回 true，则更新键值对；iii. 如果 K 的 hash 值在 HashMap 中存在，且它们两者 equals 返回 false，则插⼊链表的尾部（尾插法）或者红⿊树中（树的添加⽅式）。
（JDK 1.7 之前使⽤头插法、JDK 1.8 使⽤尾插法）（注意：当碰撞导致链表⼤于 TREEIFY_THRESHOLD = 8 时，就把链表转换成红⿊树）获取对象时，将 K 传给 get() ⽅法：①、调⽤ hash(K) ⽅法（计算 K 的 hash 值）从⽽获取该键值所在链表的数组下标；②、顺序遍历链表，equals()⽅法查找相同 Node 链表中 K 值对应的 V 值。
红黑树的介绍和实现(一)[原创]DataStructure 2010-10-0821:42:00一、红黑树（Red-Black Tree）是二叉搜索树（Binary Search Tree）的一种。
二叉搜索树在最坏的情况下可能会变成一个链表（当所有节点按从小到大的顺序依次插入后）。
这种低效产生的原因是树没有维持一定的平衡性，要提高搜索效率，就要想办法来维持树左边的平衡，也就是要尽时降低树的高度，可行的做法就是用一些策略在每次修改树的内容之后都调整树的结构，使之满足一定的平衡条件。
其中一种满足一定平衡条件而且目前应用广泛的是红黑树。
它可以在每一次插入或删除节点之后都会花O（log N）的时间来对树的结构作修改，以保持树的平衡。
而红黑树的查找方法与二叉搜索树完全一样，也能够在O(log N)时间上完成。
而红黑树的插入和删除节点的的方法只是在原二叉搜索树搜索和删除算法之后经过一定的过程来维持红黑树的性质不变。
红黑树的每个节点上的属性除了有一个key、3个指针：parent、left、right以外，还多了一个属性：color。
它只能是两种颜色：红或黑,当然也可以再加一些以key 来索引的数据。
而红黑树除了具有二叉搜索树的所有性质之外，还具有以下5点性质：1. 每个节点是黑色的或是红色的。
2. 根节点是黑色的。
3. 空节点是黑色的（红黑树中，根节点的parent以及所有叶节点left、right都不指向NULL，而是指向一个定义好的空节点,这样可以保持算法的一致性，简化算法）。
4. 红色节点的父、左子、右子节点都是黑色。
5. 在任何一棵子树中，每一条从根节点向下走到空节点的路径上包含的黑色节点数量都相同。
如下图就是一棵红黑树：小记：1.在一棵红黑树中null节点是很多的，如果每个null节点都用一个真的节点的话那就太浪费空间了，我们可以对所有的null节点都使用同一个节点，这样可以简化算法又能节约空间。
红⿊树（R-BTree）R-B Tree简介R-B Tree，全称是Red-Black Tree，⼜称为“红⿊树”，它⼀种特殊的⼆叉查找树。
红⿊树的每个节点上都有存储位表⽰节点的颜⾊，可以是红(Red)或⿊(Black)。
红⿊树的特性:（1）每个节点或者是⿊⾊，或者是红⾊。
（2）根节点是⿊⾊。
（3）每个叶⼦节点（NIL）是⿊⾊。
[注意：这⾥叶⼦节点，是指为空(NIL或NULL)的叶⼦节点！]（4）如果⼀个节点是红⾊的，则它的⼦节点必须是⿊⾊的。
（5）从⼀个节点到该节点的⼦孙节点的所有路径上包含相同数⽬的⿊节点。
注意：(01) 特性(3)中的叶⼦节点，是只为空(NIL或null)的节点。
(02) 特性(5)，确保没有⼀条路径会⽐其他路径长出俩倍。
因⽽，红⿊树是相对是接近平衡的⼆叉树。
红⿊树⽰意图如下：红⿊树的应⽤红⿊树的应⽤⽐较⼴泛，主要是⽤它来存储有序的数据，它的时间复杂度是O(lgn)，效率⾮常之⾼。
例如，Java集合中的和，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红⿊树去实现的。
红⿊树的时间复杂度和相关证明红⿊树的时间复杂度为: O(lgn)下⾯通过“数学归纳法”对红⿊树的时间复杂度进⾏证明。
定理：⼀棵含有n个节点的红⿊树的⾼度⾄多为2log(n+1).证明："⼀棵含有n个节点的红⿊树的⾼度⾄多为2log(n+1)" 的逆否命题是 "⾼度为h的红⿊树，它的包含的内节点个数⾄少为 2h/2-1个"。
我们只需要证明逆否命题，即可证明原命题为真；即只需证明"⾼度为h的红⿊树，它的包含的内节点个数⾄少为 2h/2-1个"。
从某个节点x出发（不包括该节点）到达⼀个叶节点的任意⼀条路径上，⿊⾊节点的个数称为该节点的⿊⾼度(x's black height)，记为bh(x)。
关于bh(x)有两点需要说明：第1点：根据红⿊树的"特性(5) ，即从⼀个节点到该节点的⼦孙节点的所有路径上包含相同数⽬的⿊节点"可知，从节点x出发到达的所有的叶节点具有相同数⽬的⿊节点。
教你透彻了解红黑树作者July 2010年12月29日------------------本文参考：Google、算法导论、STL源码剖析、计算机程序设计艺术。
本人声明：个人原创，转载请注明出处。
一、红黑树的介绍先来看下算法导论对R-B Tree的介绍：红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red 或Black。
通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
前面说了，红黑树，是一种二叉查找树，既然是二叉查找树，那么它必满足二叉查找树的一般性质。
下面，再具体介绍红黑树之前，咱们先来了解下二叉查找树的一般性质：1.在一棵二叉查找树上，执行查找、插入、删除等操作，的时间复杂度为O（lgn）。
因为，一棵由n个结点，随机构造的二叉查找树的高度为O（lgn），所以顺理成章，一般操作的执行时间为O（lgn）。
（至于n个结点的二叉树高度为O（lgn）的证明，可参考算法导论第12章二叉查找树。
）2.但若是一棵具有n个结点的线性链，则此些操作最坏情况运行时间为O（n）。
而红黑树，能保证在最坏情况下，基本的动态几何操作的时间均为O（lgn）。
ok，我们知道，红黑树上每个结点内含五个域，color，key，left，right。
如果相应的指针域没有，则设为NIL。
一般的，红黑树，满足一下性质，即只有满足一下性质的树，我们才称之为红黑树：1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
下图所示，即是一颗红黑树：此图忽略了叶子和根部的父结点。
总之，可以这样表示，就对了。
:D。
..........红黑树插入、删除操作的具体实现ok，接下来，咱们来具体了解红黑树的插入操作。
前言：之所以要写这篇文章，第一个目的是为了各位朋友在查看我写的源代码之前有一个可以理解理论的文章因为红黑树还是有点难的，如果不想搞懂理论，而直接看代码，那绝对是云里雾里，不知所云。
第二个目的是我觉得网上虽然后不少我文章也在讲，但是我就是理解不上有点困难，在我参考了很多文章之后，认真阅读才慢慢摸透了其中的原理，所以我想用自己的方式来表达，希望有助于各位的朋友理解。
你可以在这里获得配套源代码红黑树由来：他是在1972年由Rudolf Bayer发明的，他称之为“对称二叉B树”，它现代的名字是Leo J. Guibas和 Robert Sedgewick 于1978年写的一篇论文中获得的。
它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。
红黑树性质：1. 每个结点或红或黑。
2. 根结点为黑色。
3. 每个叶结点(实际上就是NULL指针)都是黑色的。
4. 如果一个结点是红色的,那么它的周边3个节点都是黑色的。
5. 对于每个结点,从该结点到其所有子孙叶结点的路径中所包含的黑色结点个数都一样。
讨论的前提：1，我们只讨论往树的左边和从树的左边删除的情况，与之对称的情况一样。
2，假设我们要删除一个元素的方法都是采取删除后继节点，而非前驱节点。
3，NL或全黑表示黑空节点，也可以不用画出。
4，“=>”这个符号我们用来表示“变成”的意思。
一．插入当红黑树中没有节点的时候，新节点直接涂黑就可以了。
当树中已有节点，我们就将新节点涂红，并且底下挂两个黑空节点。
1.1 新节点的父亲为黑色这种情况最简单，只接插入将新节点可以了，不会出现红色警戒。
1.2 新节点的父亲为红色这种情况出现红色警戒，并且通过红色的父亲，我们可以推出一定有一个黑色的父，并且父亲不可能为树根(树根必须为黑)。
这种情况需要修复。
1.2.1 新节点的叔叔是红色。
什么是红黑树
红黑树（Red Black Tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
它是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B 树（symmetric binary B-trees）。
后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。
红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的：它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。
它的统计性能要好于平衡二叉树(有些书籍根据作者姓名，Adelson-Velskii和Landis，将其称为AVL-树)，因此，红黑树在很多地方都有应用。
在C++ STL中，很多部分(包括set, multiset,map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持)。
其他平衡树还有：AVL，SBT，伸展树，TREAP 等等。
红⿊树详解前⾔红⿊树的起源，⾃然是⼆叉查找树了，这种树结构从根节点开始，左⼦节点⼩于它，右⼦节点⼤于它。
每个节点都符合这个特性，所以易于查找，是⼀种很好的数据结构。
但是它有⼀个问题，就是容易偏向某⼀侧，这样就像⼀个链表结构了，失去了树结构的优点，查找时间会变坏。
所以我们都希望树结构都是矮矮胖胖的，像这样：⽽不是像这样：在这种需求下，平衡树（AVL）的概念就应运⽽⽣了。
红⿊树就是⼀种平衡树，它可以保证⼆叉树基本符合矮矮胖胖的结构，但是理解红⿊树之前，必须先了解另⼀种树，叫2-3树，红⿊树背后的逻辑就是它。
好吧来看2-3树吧。
2-3树是⼆叉查找树的变种，树中的2和3代表两种节点，以下表⽰为2-节点和3-节点。
2-节点即普通节点：包含⼀个元素，两条⼦链接。
3-节点则是扩充版，包含2个元素和三条链接：两个元素A、B，左边的链接指向⼩于A的节点，中间的链接指向介于A、B值之间的节点，右边的链接指向⼤于B的节点 2-节点： 3-节点：在这两种节点的配合下，2-3树可以保证在插⼊值过程中，任意叶⼦节点到根节点的距离都是相同的。
完全实现了矮胖矮胖的⽬标。
怎么配合的呢，下⾯来看2-3树的构造过程。
所谓构造，就是从零开始⼀个节点⼀个节点的插⼊。
在⼆叉查找树中，插⼊过程从根节点开始⽐较，⼩于节点值往右继续与左⼦节点⽐，⼤于则继续与右⼦节点⽐，直到某节点左或右⼦节点为空，把值插⼊进去。
这样⽆法避免偏向问题。
在2-3树中，插⼊的过程是这样的。
如果将值插⼊⼀个2-节点，则将2-节点扩充为⼀个3-节点。
如果将值插⼊⼀个3-节点，分为以下⼏种情况。
(1).3-节点没有⽗节点，即整棵树就只有它⼀个三节点。
此时，将3-节点扩充为⼀个4-节点，即包含三个元素的节点，然后将其分解，变成⼀棵⼆叉树。
此时⼆叉树依然保持平衡。
(2).3-节点有⼀个2-节点的⽗节点，此时的操作是，3-节点扩充为4-节点，然后分解4-节点，然后将分解后的新树的⽗节点融⼊到2-节点的⽗节点中去。
java算法实现红⿊树完整代码⽰例红⿊树定义红⿊树（英语：Red–black tree）是⼀种⾃平衡⼆叉查找树，是在计算机科学中⽤到的⼀种数据结构，典型的⽤途是实现关联数组。
红⿊树的另⼀种定义是含有红⿊链接并满⾜下列条件的⼆叉查找树：红链接均为左链接；没有任何⼀个结点同时和两条红链接相连；该树是完美⿊⾊平衡的，即任意空链接到根结点的路径上的⿊链接数量相同。
满⾜这样定义的红⿊树和相应的2-3树是⼀⼀对应的。
旋转旋转⼜分为左旋和右旋。
通常左旋操作⽤于将⼀个向右倾斜的红⾊链接旋转为向左链接。
对⽐操作前后，可以看出，该操作实际上是将红线链接的两个节点中的⼀个较⼤的节点移动到根节点上。
左旋操作如下图：右旋旋操作如下图：即：复杂度红⿊树的平均⾼度⼤约为lgN。
下图是红⿊树在各种情况下的时间复杂度，可以看出红⿊树是2-3查找树的⼀种实现，他能保证最坏情况下仍然具有对数的时间复杂度。
Java代码import java.util.NoSuchElementException;import java.util.Scanner;public class RedBlackBST<key extends="" key="">, Value> {private static final boolean RED = true;private static final boolean BLACK = false;private Node root; //root of the BSTprivate class Node {private Key key; //keyprivate Value val; //associated dataprivate Node left, right; //links to left and right subtreesprivate boolean color; //color of parent linkprivate int size; //subtree countpublic Node(Key key, Value val, boolean color, int size) {this.key = key;this.val = val;this.color = color;this.size = size;}}//is node x red?private boolean isRed(Node x) {if(x == null) {return false;}return x.color == RED;}//number of node in subtree rooted at x; 0 if x is nullprivate int size(Node x) {if(x == null) {return 0;}return x.size;}/*** return the number of key-value pairs in this symbol table* @return the number of key-value pairs in this symbol table*/public int size() {return size(root);}/*** is this symbol table empty?* @return true if this symbol table is empty and false otherwise*/public boolean isEmpty() {return root == null;}/*** return the value associated with the given key* @param key the key* @return the value associated with the given key if the key is in the symbol table, and null if it is not. */public Value get(Key key) {if(key == null) {throw new NullPointerException("argument to get() is null");}return get(root, key);}//value associated with the given key in subtree rooted at x; null if no such keyprivate Value get(Node x, Key key) {while(x != null) {int cmp = pareTo(x.key);if(cmp < 0) {x = x.left;}else if(cmp > 0) {x = x.right;}else {return x.val;}}return null;}/*** does this symbol table contain the given key?* @param key the key* @return true if this symbol table contains key and false otherwise*/public boolean contains(Key key) {return get(key) != null;}/**************************************************************************** Red-black tree insertion.***************************************************************************//*** Inserts the specified key-value pair into the symbol table, overwriting the old* value with the new value if the symbol table already contains the specified key.* Deletes the specified key (and its associated value) from this symbol table* if the specified value is null.** @param key the key* @param val the value* @throws NullPointerException if key is null*/public void put(Key key, Value val) {if (key == null) {throw new NullPointerException("first argument to put() is null");}if (val == null) {delete(key);return;}root = put(root, key, val);root.color = BLACK;}// insert the key-value pair in the subtree rooted at hprivate Node put(Node h, Key key, Value val) {if(h == null) {return new Node(key, val, RED, 1);}int cmp = pareTo(h.key);if(cmp < 0) {h.left = put(h.left, key, val);}else if(cmp > 0) {h.right = put(h.right, key, val);}else {h.val = val;}if(isRed(h.right) && !isRed(h.left)) {h = rotateLeft(h);}if(isRed(h.left) && isRed(h.left.left)) {h = rotateRight(h);}if(isRed(h.left) && isRed(h.right)) {flipColors(h);}h.size = size(h.left) + size(h.right) + 1;return h;}/**************************************************************************** Red-black tree deletion.***************************************************************************//*** Removes the smallest key and associated value from the symbol table. * @throws NoSuchElementException if the symbol table is empty*/public void deleteMin() {if (isEmpty()) {throw new NoSuchElementException("BST underflow");}// if both children of root are black, set root to redif (!isRed(root.left) && !isRed(root.right))root.color = RED;root = deleteMin(root);if (!isEmpty()) root.color = BLACK;// assert check();}// delete the key-value pair with the minimum key rooted at h// delete the key-value pair with the minimum key rooted at hprivate Node deleteMin(Node h) {if (h.left == null){return null;}if (!isRed(h.left) && !isRed(h.left.left)) {h = moveRedLeft(h);}h.left = deleteMin(h.left);return balance(h);}/*** Removes the largest key and associated value from the symbol table. * @throws NoSuchElementException if the symbol table is empty*/public void deleteMax() {if (isEmpty()) {throw new NoSuchElementException("BST underflow");}// if both children of root are black, set root to redif (!isRed(root.left) && !isRed(root.right))root.color = RED;root = deleteMax(root);if (!isEmpty()) root.color = BLACK;// assert check();}// delete the key-value pair with the maximum key rooted at h// delete the key-value pair with the maximum key rooted at hprivate Node deleteMax(Node h) {if (isRed(h.left))h = rotateRight(h);if (h.right == null)return null;if (!isRed(h.right) && !isRed(h.right.left))h = moveRedRight(h);h.right = deleteMax(h.right);return balance(h);}/*** remove the specified key and its associated value from this symbol table * (if the key is in this symbol table).** @param key the key* @throws NullPointerException if key is null*/public void delete(Key key) {if (key == null) {throw new NullPointerException("argument to delete() is null");}if (!contains(key)) {return;}//if both children of root are black, set root to redif(!isRed(root.left) && !isRed(root.right)) {root.color = RED;}root = delete(root, key);if(!isEmpty()) {root.color = BLACK;}}// delete the key-value pair with the given key rooted at h// delete the key-value pair with the given key rooted at hprivate Node delete(Node h, Key key) {if(pareTo(h.key) < 0) {if(!isRed(h.left) && !isRed(h.left.left)) {h = moveRedLeft(h);}h.left = delete(h.left, key);}else {if(isRed(h.left)) {h = rotateRight(h);}if (pareTo(h.key) == 0 && (h.right == null)) {return null;}if (!isRed(h.right) && !isRed(h.right.left)) {h = moveRedRight(h);}if (pareTo(h.key) == 0) {Node x = min(h.right);h.key = x.key;h.val = x.val;h.right = deleteMin(h.right);}else {h.right = delete(h.right, key);}}return balance(h);}/**************************************************************************** Red-black tree helper functions.***************************************************************************/// make a left-leaning link lean to the right// make a left-leaning link lean to the rightprivate Node rotateRight(Node h) {// assert (h != null) && isRed(h.left);Node x = h.left;h.left = x.right;x.right = h;x.color = x.right.color;x.right.color = RED;x.size = h.size;h.size = size(h.left) + size(h.right) + 1;return x;}// make a right-leaning link lean to the left// make a right-leaning link lean to the leftprivate Node rotateLeft(Node h) {// assert (h != null) && isRed(h.right);Node x = h.right;h.right = x.left;x.left = h;x.color = x.left.color;x.left.color = RED;x.size = h.size;h.size = size(h.left) + size(h.right) + 1;return x;}// flip the colors of a node and its two children// flip the colors of a node and its two childrenprivate void flipColors(Node h) {// h must have opposite color of its two children// assert (h != null) && (h.left != null) && (h.right != null);// assert (!isRed(h) && isRed(h.left) && isRed(h.right))// || (isRed(h) && !isRed(h.left) && !isRed(h.right));h.color = !h.color;h.left.color = !h.left.color;h.right.color = !h.right.color;}// Assuming that h is red and both h.left and h.left.left// are black, make h.left or one of its children red.// Assuming that h is red and both h.left and h.left.left// are black, make h.left or one of its children red.private Node moveRedLeft(Node h) {// assert (h != null);// assert isRed(h) && !isRed(h.left) && !isRed(h.left.left);flipColors(h);if (isRed(h.right.left)) {h.right = rotateRight(h.right);h = rotateLeft(h);flipColors(h);}return h;}// Assuming that h is red and both h.right and h.right.left// are black, make h.right or one of its children red.// Assuming that h is red and both h.right and h.right.left// are black, make h.right or one of its children red.private Node moveRedRight(Node h) {// assert (h != null);// assert isRed(h) && !isRed(h.right) && !isRed(h.right.left);flipColors(h);if (isRed(h.left.left)) {h = rotateRight(h);flipColors(h);}return h;}// restore red-black tree invariant// restore red-black tree invariantprivate Node balance(Node h) {// assert (h != null);if (isRed(h.right)) {h = rotateLeft(h);}if (isRed(h.left) && isRed(h.left.left)) {h = rotateRight(h);}if (isRed(h.left) && isRed(h.right)) {flipColors(h);}h.size = size(h.left) + size(h.right) + 1;return h;}/*************************************************************************** * Utility functions.***************************************************************************//*** Returns the height of the BST (for debugging).* @return the height of the BST (a 1-node tree has height 0)*/public int height() {return height(root);}private int height(Node x) {if (x == null) {return -1;}return 1 + Math.max(height(x.left), height(x.right));}/**************************************************************************** Ordered symbol table methods.***************************************************************************//*** Returns the smallest key in the symbol table.* @return the smallest key in the symbol table* @throws NoSuchElementException if the symbol table is empty*/public Key min() {if (isEmpty()) {throw new NoSuchElementException("called min() with empty symbol table"); }return min(root).key;}// the smallest key in subtree rooted at x; null if no such keyprivate Node min(Node x) {// assert x != null;if (x.left == null) {return x;}else {return min(x.left);}}/*** Returns the largest key in the symbol table.* @return the largest key in the symbol table* @throws NoSuchElementException if the symbol table is empty*/public Key max() {if (isEmpty()) {throw new NoSuchElementException("called max() with empty symbol table"); }return max(root).key;}// the largest key in the subtree rooted at x; null if no such keyprivate Node max(Node x) {// assert x != null;if (x.right == null) {return x;}else {return max(x.right);}}/*** Returns the largest key in the symbol table less than or equal to key.* @param key the key* @return the largest key in the symbol table less than or equal to key* @throws NoSuchElementException if there is no such key* @throws NullPointerException if key is null*/public Key floor(Key key) {if (key == null) {throw new NullPointerException("argument to floor() is null");}if (isEmpty()) {throw new NoSuchElementException("called floor() with empty symbol table"); }Node x = floor(root, key);if (x == null) {return null;}else {return x.key;}}// the largest key in the subtree rooted at x less than or equal to the given keyprivate Node floor(Node x, Key key) {if (x == null) {return null;}int cmp = pareTo(x.key);if (cmp == 0) {return x;}if (cmp < 0) {return floor(x.left, key);}Node t = floor(x.right, key);if (t != null) {return t;}else {return x;}}/*** Returns the smallest key in the symbol table greater than or equal to key.* @param key the key* @return the smallest key in the symbol table greater than or equal to key* @throws NoSuchElementException if there is no such key* @throws NullPointerException if key is null*/public Key ceiling(Key key) {if (key == null) {throw new NullPointerException("argument to ceiling() is null");}if (isEmpty()) {throw new NoSuchElementException("called ceiling() with empty symbol table"); }Node x = ceiling(root, key);if (x == null) {return null;}else {return x.key;}}// the smallest key in the subtree rooted at x greater than or equal to the given key private Node ceiling(Node x, Key key) {if (x == null) {return null;}int cmp = pareTo(x.key);if (cmp == 0) {return x;}if (cmp > 0) {return ceiling(x.right, key);}Node t = ceiling(x.left, key);if (t != null) {return t;}else {return x;}}/*** Return the kth smallest key in the symbol table.* @param k the order statistic* @return the kth smallest key in the symbol table* @throws IllegalArgumentException unless k is between 0 and* <em>N</em> − 1*/public Key select(int k) {if (k < 0 || k >= size()) {throw new IllegalArgumentException();Node x = select(root, k);return x.key;}// the key of rank k in the subtree rooted at xprivate Node select(Node x, int k) {// assert x != null;// assert k >= 0 && k < size(x);int t = size(x.left);if (t > k) {return select(x.left, k);}else if (t < k) {return select(x.right, k-t-1);}else {return x;}}/*** Return the number of keys in the symbol table strictly less than key. * @param key the key* @return the number of keys in the symbol table strictly less than key * @throws NullPointerException if key is null*/public int rank(Key key) {if (key == null) {throw new NullPointerException("argument to rank() is null");}return rank(key, root);}// number of keys less than key in the subtree rooted at xprivate int rank(Key key, Node x) {if (x == null) {return 0;}int cmp = pareTo(x.key);if (cmp < 0) {return rank(key, x.left);}else if (cmp > 0) {return 1 + size(x.left) + rank(key, x.right);}else {return size(x.left);}}/**************************************************************************** Range count and range search.***************************************************************************//*** Returns all keys in the symbol table as an Iterable.* To iterate over all of the keys in the symbol table named st,* use the foreach notation: for (Key key : st.keys()).* @return all keys in the symbol table as an Iterable*/public Iterable<key> keys() {if (isEmpty()) {return new Queue<key>();}return keys(min(), max());}/*** Returns all keys in the symbol table in the given range,* as an Iterable.* @return all keys in the symbol table between lo* (inclusive) and hi (exclusive) as an Iterable* @throws NullPointerException if either lo or hi* is null*/public Iterable<key> keys(Key lo, Key hi) {if (lo == null) {throw new NullPointerException("first argument to keys() is null");}if (hi == null) {throw new NullPointerException("second argument to keys() is null");Queue<key> queue = new Queue<key>();// if (isEmpty() || pareTo(hi) > 0) return queue;keys(root, queue, lo, hi);return queue;}// add the keys between lo and hi in the subtree rooted at x// to the queueprivate void keys(Node x, Queue<key> queue, Key lo, Key hi) {if (x == null) {return;}int cmplo = pareTo(x.key);int cmphi = pareTo(x.key);if (cmplo < 0) {keys(x.left, queue, lo, hi);}if (cmplo <= 0 && cmphi >= 0) {queue.enqueue(x.key);}if (cmphi > 0) {keys(x.right, queue, lo, hi);}}/*** Returns the number of keys in the symbol table in the given range.* @return the number of keys in the symbol table between lo* (inclusive) and hi (exclusive)* @throws NullPointerException if either lo or hi* is null*/public int size(Key lo, Key hi) {if (lo == null) {throw new NullPointerException("first argument to size() is null");}if (hi == null) {throw new NullPointerException("second argument to size() is null");}if (pareTo(hi) > 0) {return 0;}if (contains(hi)) {return rank(hi) - rank(lo) + 1;}else {return rank(hi) - rank(lo);}}/**************************************************************************** Check integrity of red-black tree data structure.***************************************************************************/private boolean check() {if (!isBST()) System.out.println("Not in symmetric order");if (!isSizeConsistent()) System.out.println("Subtree counts not consistent");if (!isRankConsistent()) System.out.println("Ranks not consistent");if (!is23()) System.out.println("Not a 2-3 tree");if (!isBalanced()) System.out.println("Not balanced");return isBST() && isSizeConsistent() && isRankConsistent() && is23() && isBalanced(); }// does this binary tree satisfy symmetric order?// Note: this test also ensures that data structure is a binary tree since order is strictprivate boolean isBST() {return isBST(root, null, null);}// is the tree rooted at x a BST with all keys strictly between min and max// (if min or max is null, treat as empty constraint)// Credit: Bob Dondero's elegant solutionprivate boolean isBST(Node x, Key min, Key max) {if (x == null) {return true;}if (min != null && pareTo(min) <= 0) {return false;}if (max != null && pareTo(max) >= 0) {return false;return isBST(x.left, min, x.key) && isBST(x.right, x.key, max);}// are the size fields correct?private boolean isSizeConsistent() {return isSizeConsistent(root);}private boolean isSizeConsistent(Node x) {if (x == null) {return true;}if (x.size != size(x.left) + size(x.right) + 1) {return false;}return isSizeConsistent(x.left) && isSizeConsistent(x.right);}// check that ranks are consistentprivate boolean isRankConsistent() {for (int i = 0; i < size(); i++) {if (i != rank(select(i))) {return false;}}for (Key key : keys()) {if (pareTo(select(rank(key))) != 0) {return false;}}return true;}// Does the tree have no red right links, and at most one (left)// red links in a row on any path?private boolean is23() {return is23(root);}private boolean is23(Node x) {if (x == null) {return true;}if (isRed(x.right)) {return false;}if (x != root && isRed(x) && isRed(x.left)){return false;}return is23(x.left) && is23(x.right);}// do all paths from root to leaf have same number of black edges?private boolean isBalanced() {int black = 0; // number of black links on path from root to minNode x = root;while (x != null) {if (!isRed(x)) black++;x = x.left;}return isBalanced(root, black);}// does every path from the root to a leaf have the given number of black links? private boolean isBalanced(Node x, int black) {if (x == null) {return black == 0;}if (!isRed(x)) {black--;}return isBalanced(x.left, black) && isBalanced(x.right, black);}/*** Unit tests the RedBlackBST data type.*/public static void main(String[] args) {RedBlackBST<string, integer=""> st = new RedBlackBST<string, integer="">(); String data = "a b c d e f g h m n o p";Scanner sc = new Scanner(data);int i = 0;while (sc.hasNext()) {String key = sc.next();st.put(key, i);i++;}sc.close();for (String s : st.keys())System.out.println(s + " " + st.get(s));System.out.println();boolean result = st.check();System.out.println("check: " + result);}}输出：<code>a 0b 1c 2d 3e 4f 5g 6h 7m 8n 9o 10p 11check: true</code>总结以上就是本⽂关于java算法实现红⿊树完整代码⽰例的全部内容，希望对⼤家有所帮助。
