下载文档原格式
红黑树详解在本文，我将比较透彻地讲解红黑树。
本文适合那些有对二叉树有一定的基础，并且熟悉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 值。
