5409人阅读
Algorithm（13）
1. 红黑树的特性
Red-Black Tree (& RBT）也是一种自平衡二叉树，其统计性能要好于 AVL树 。它是在1972年由 鲁道夫·贝尔 发明的，它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的。[]
一般的，红黑树同时满足以下五大特性：
所有节点的颜色是红色或者黑色；根节点是黑色；所有的叶子节点是黑色（叶子节点包含NULL）；每个红色的节点都有两个黑色的子节点；从任意节点出发，到其所有叶子节点的简单路径上都包含相同数目的黑色节点.
从上面的性质 4 和 5来看，红色节点和黑色节点基本上是交替的出现，所以红黑树从根到叶子的最长的可能路径不多于最短的可能路径的两倍长，这样的结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的。
2. 数据结构定义
RBT数据结构在基本二叉树数据结构之上增加一个color和parent，color用于保存节点颜色，parent指向父节点。
#define COLOR_RED 0
#define COLOR_BLACK 1
typedef int keyT
// 定义而二叉树节点数据结构
struct BinaryTreeNode {
BinaryTreeNode* // 保存父节点
BinaryTreeNode* // left child
BinaryTreeNode* // right child
// define red-black tree node
typedef BinaryTreeN
// define red-black tree
typedef BinaryTreeN
3. 插入Key
无论怎么样操作，性质1和性质3是始终能够保持的。新插入节点的时候，新节点的初始颜色为红色，这样可以不直接破坏性质5，这个时候可能性质4受到威胁，需要调整节点颜色或这左一些旋转等操作。假设新插入的节点为N，其父节点为P，祖父节点为G，叔父节点为U，下面具体分析一下插入新节点的各种情况。
情形1 、空树
当树为空的时候，直接将N节点设为黑色作为树的根节点返回。
情形2 、P为黑色节点
图中所示为N插入到P左孩子节点中，这个过程完全满足性质 1 - 5 的要求，并没有破坏 RBT 的规则，因此，此时即可停止检查，插入过程结束。
同理，若P为黑色节点，N插入后作为P的右孩子节点也不会破坏 RBT的规则。
（下面开始讨论 P 为红色 的情形，由 性质2 推导出 G 一定存在，根据性质 4，G一定是黑色）
情形3 、P为红色节点，U存在且为红色节点
这种情况下，将G变为红色，P和U变为黑色，这样维持了G为Root的子树内性质4和5，然后以G作为新的插入节点，从情形1开始迭代。
情形4 、P为红色节点，U不存在或者U为黑色
（a） 若P在G的左侧，插入点N也在P的左侧 ------ LL 型
假设G的右侧有 路径有 x个黑色节点，则c有x个黑色节点，G为root的子树路径有x+1个黑色节点。 此时， 只需要以P为中心右旋，将P变为黑色，G变为红色，G的左子树替换为c，这样就可以继续保证以P为root的子树有x+1个黑色节点，检查停止。
（b）若P在G的左侧，N在P的右侧& -----LR型
这时候先将节点P和节点N做调整，进行左旋，变化成（a）的形态，然后做一次右旋。到此，调整完毕。
（c）若P在G的右侧，N在P的右侧 ----------RR型
情形和（a）正好相反，做一次左旋即可。
（d）若P在G的右侧，N在P的左侧 ----------RL型
情形和（b）正好相反，先做做一次右旋，后进行一次左旋即可。
RBT插入算法过程代码如下：
// 向右旋转
void rb_right_rotate(rbnode* g) {
&& &rbnode * p = g-&
&& &keyType k = g-&
&& &g-&key = p-&
&& &p-&key =
&& &g-&left = p-&
&& &if (NULL != p-&left) {
&& &&& &p-&left-&parent =
&& &p-&left = p-&
&& &p-&right = g-&
&& &if (NULL != g-&right) {
&& &&& &g-&right-&parent =
&& &g-&right =
// 向左旋转
void rb_left_rotate(rbnode* g) {
&& &rbnode* p = g-&
&& &keyType k = g-&
&& &g-&key = p-&
&& &p-&key =
&& &g-&right = p-&
&& &if (NULL != p-&right) {
&& &&& &p-&right-&parent =
&& &p-&right = p-&
&& &p-&left = g-&
&& &if (NULL != g-&left) {
&& &&& &g-&left-&parent =
&& &g-&left =
// check and adjust after insertion
void rbt_insert_check(rbnode* node) {
&& &// CASE 1 :& if the node equals the root
&& &// set the color of the node black and return.
&& &if (NULL == node-&parent) {
&& &&& &node-&color = COLOR_BLACK;
&& &// CASE 2 : when the parent of the node is black
&& &// All features have been met, stop check and return
&& &if (node-&parent-&color == COLOR_BLACK) {
&& &// Otherwise, the the parent node is RED, and this means the grandfather node exists.
&& &rbnode* gf = node-&parent-&
&& &rbnode* uf = (gf-&left == node-&parent) ? gf-&right : gf-&
&& &// CASE 3 : When the uncle node exists and it's RED
&& &if (NULL != uf && uf-&color == COLOR_RED) {
&& &&& &// set parent and uncle black, set grandfather red
&& &&& &node-&parent-&color = COLOR_BLACK;
&& &&& &uf-&color = COLOR_BLACK;
&& &&& &gf-&color = COLOR_RED;
&& &&& &// then re check the tree at grandfather node from CASE 1.
&& &&& &rbt_insert_check(gf);
&& &// CASE 4 : when the uncle is NULL or its color is Black.
&& &if (node-&parent == gf-&left) { // the node in the left of its grandfather
&& &&& &// (a) LL model
&& &&& &if (node == node-&parent-&left) { // the node in the left of its parent
&& &&& &&& &rb_right_rotate(gf);
&& &&& &// (b) LR model
&& &&& &else if (node == node-&parent-&right) { //the node in the right of its parent.
&& &&& &&& &rb_left_rotate(node-&parent);
&& &&& &&& &rb_right_rotate(gf);
&& &} else if (node-&parent == gf-&right) { //the node in the right of its grandfather
&& &&& &// (c) RR model
&& &&& &if (node == node-&parent-&right) { //the node in the right of its parent.
&& &&& &&& &rb_left_rotate(gf);
&& &&& &// (d) RL model
&& &&& &else if (node == node-&parent-&left) { //the node in the left of its parent.
&& &&& &&& &rb_right_rotate(node-&parent);
&& &&& &&& &rb_left_rotate(gf);
// 插入新的关键字
int rbt_insert(rbtree* &tree, keyType key) {
&& &if (NULL == tree) { // if the tree is NULL
&& &&& &tree = (rbtree*) malloc((sizeof(rbnode)));
&& &&& &tree-&key =
&& &&& &tree-&color = COLOR_BLACK;
&& &&& &tree-&parent = tree-&left = tree-&right = NULL;
&& &&& &return 1;
&& &// find insert point
&& &rbnode *n = tree, *p = tree-&
&& &while (NULL != n) {
&& &&& &if (key == n-&key) {
&& &&& &&& &return 0;
&& &&& &p =
&& &&& &n = (key & p-&key) ? p-&right : p-&
&& &// insert the node
&& &n = (rbtree*) malloc((sizeof(rbnode)));
&& &n-&key =
&& &n-&color = COLOR_RED;
&& &n-&parent =
&& &n-&right = n-&left = NULL;
&& &((key & p-&key) ? p-&right : p-&left) =
&& &// adjust the tree
&& &rbt_insert_check(n);
&& &return 1;
从RBT中删除指定的Key时，需要重新调整树的形态使之满足红黑树的特性。下面来具体分析一下删除Key的过程。
（1）根据key找到要删除的节点Node：如果没有找到，直接返回，否则，进行下一步操作；
（2）如果Node有两个孩子节点，那么删除Node之后该如何放置其孩子节点呢？
&&&&&&&&&& 这个时候需要进行预处理，转化为删除只有一个孩子的节点的情形。
&&&&&&&&&& 找到Node的中序前驱（后继）节点，将前驱（后继）节点的值复制到Node中，Node指向前驱（后继）节点；
（3）到此步骤，Node确切的指示为待删除的节点，且Node最多只有一个孩子节点。
&&&&&&&&&& 删除Node节点，将Node的孩子节点顶替Node的位置.（注意Node为Root的情形）
（4）调整RBT树使其满足规定的5大特性。
&&&&&&&&&& 假设上一步中顶替上来的节点为 N ，其父节点为 P ，其兄弟节点为 S ，Sl 和 Sr 分别为 S 的左右孩子节点 ，假设 N 在 P 的左侧， 调整过程如下：
&&&&&&&&&&（右侧与左侧对称，这里分析一种即可）
情形1 、N节点为红色
当N节点为红色的时候，由于左侧缺少一个黑色的节点，可以将N节点的颜色修改为黑色，这样即可从新满足性质5.
调整完毕。
情形2、S节点为红色
当S节点为红色节点时，则可以将P节点向左旋转，旋转之后P为红色，S为黑色，这个时候S-Sl这条简单路径黑色节点数目合法，S-P-Sl节点数目也合法，S-P-N路径黑色节点数目少一个。
相当于，P的左侧删除了一个黑色节点，应当重新调整 P，S，Sl，Sr所指向的节点，进行后续操作。
后续可能的情形为：3，5，6
情形3、P节点为红色，S，Sl，Sr为黑色
当P为红色，S为黑色，Sl和Sr均为黑色的时候，则可以简单的交换P节点和S节点的颜色，这样即可使各条简单路径的黑色节点数目和删除节点前相等。
调整完毕。
情形4、P，S，Sl，Sr均为黑色
当P、S、Sl、Sr均为黑色节点的时候，只需要简单的将S节点标记为红色，这样以P节点为根的个简单路径黑色节点数目比删除之前少一个。
因此，P相当与N的位置，从P的父节点开始递归进行调整。
（如果此时P为树的根节点，即可停止调整）
情形5、Sl为红色节点并且Sr为黑色
这种情况下，可以将Sl进行右旋操作，右旋之后，Sl为黑色，S为红色，Sr不变，这样保持P节点右子树中各简单路径黑色节点数目和旋转前一样。
这个时候，原来的S相当于Sl的位置，Sl相当与a，Sr相当与S。
更新S，Sl，Sr新指向的位置，进行下一步操作。
后续情形为：6.
情形6、Sr为红色
这时，将P节点做一次左旋操作，将Sr的颜色设置为黑色，P和S交换颜色，调整之后，各简单路径的黑色节点数目和删除节点之前一样。
此时调整结束。
int is_black(rbnode * node) {
if (node == NULL) return 1;
if (node-&color == COLOR_BLACK) return 1;
// check and adjust after deletion
void rbt_delete_check(rbnode* p, bool delLeft) {
&& &rbnode * n = delLeft ? p-&left : p-&
&& &// case 1: n is red
&& &if (NULL != n && n-&color == COLOR_RED) {
&& &&& &n-&color = COLOR_BLACK;
&& &// else the other subtree of p at least has one more node.
&& &rbnode * s = delLeft ? p-&right : p-&
&& &rbnode * sl = s-&
&& &rbnode * sr = s-&
&& &// case 2 : S is red , p left rotate
&& &if (s-&color == COLOR_RED) {
&& &&& &if (delLeft) {
&& &&& &&& &rb_left_rotate(p);
&& &&& &} else {
&& &&& &&& &rb_right_rotate(p);
&& &&& &p =
&& &&& &s = delLeft ? sl :
&& &&& &sl = s-&
&& &&& &sr = s-&
&& &// Other cases : S is black
&& &// when SL and SR& are black
&& &if (is_black(sl) && is_black(sr)) {
&& &&& &// case 3 : P is red,& S SL and SR are black
&& &&& &if (!is_black(p)) {
&& &&& &&& &p-&color = COLOR_BLACK;
&& &&& &&& &s-&color = COLOR_RED;
&& &&& &// case 4: P ,S, SL and SR are black
&& &&& &else {
&& &&& &&& &s-&color = COLOR_RED;
&& &&& &&& &if (NULL == p-&parent) {
&& &&& &&& &&& &
&& &&& &&& &}
&& &&& &&& &delLeft = (p == p-&parent-&left);
&& &&& &&& &rbt_delete_check(p-&parent, delLeft);
&& &// when SL and SR has red node
&& &if (delLeft) {
&& &&& &if (is_black(sr)) {&& &// case 5(a) : delLeft is true and SR is black
&& &&& &&& &rb_right_rotate(s);
&& &&& &&& &sr = s-&
&& &&& &rb_left_rotate(p);&& &// case 6(a) : rotate the p node
&& &&& &sr-&color = COLOR_BLACK;
&& &} else {
&& &&& &if (is_black(sl)) {&& &// case 5(b) : delLeft is false and SL is black
&& &&& &&& &rb_left_rotate(s);
&& &&& &&& &sl = s-&
&& &&& &rb_right_rotate(p);&& &// case 6(b) : rotate the p node
&& &&& &sl-&color = COLOR_BLACK;
// delete a key from the RBT
int rbt_delete(rbtree* &tree, keyType key) {
&& &if (NULL == tree) {
&& &&& &return 0;
&& &// find the node
&& &rbnode *curr, *
&& &for (curr =;) {
&& &&& &if (key == curr-&key) {
&& &&& &&& &
&& &&& &curr = (key & curr-&key) ? curr-&right : curr-&
&& &&& &if (NULL == curr) {
&& &&& &&& &return 0;
&& &// if the node to delete has two children
&& &if (NULL != curr-&left && NULL != curr-&right) {
&& &&& &for (temp = curr-& NULL != temp-& temp = temp-&right) {
&& &&& &curr-&key = temp-&
&& &&& &curr =
&& &if (NULL == curr-&parent) { // it is the tree root
&& &&& &tree = (NULL == curr-&left) ? curr-&right : curr-&
&& &&& &if (tree != NULL) {
&& &&& &&& &tree-&color = COLOR_BLACK;
&& &&& &&& &tree-&parent = NULL;
&& &&& &free(curr);
&& &&& &return 1;
&& &// delete the node
&& &rbnode* fa = curr-&
&& &temp = (NULL == curr-&left) ? curr-&right : curr-&
&& &bool delLeft = (fa-&left == curr);
&& &if (NULL != temp) {
&& &&& &temp-&parent =
&& &delLeft ? fa-&left = temp : fa-&right =
&& &if (curr-&color != COLOR_RED) { // adjust after deletion
&& &&& &rbt_delete_check(fa, delLeft);
&& &free(curr);
&& &return 1;
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：212217次
积分：2708
积分：2708
排名：第9145名
原创：56篇
评论：72条
(1)(1)(1)(1)(1)(1)(1)(3)(4)(5)(12)(1)(1)(2)(2)(2)(2)(3)(3)(4)(2)(1)(1)(2)(2)红黑树(五)之 Java的实现 - 如果天空不死 - 推酷
红黑树(五)之 Java的实现 - 如果天空不死
前面分别介绍红黑树的理论知识、红黑树的C语言和C++的实现。本章介绍红黑树的Java实现，若读者对红黑树的理论知识不熟悉，建立先学习
，再来学习本章。还是那句老话，红黑树的C/C++/Java实现，原理一样，择其一了解即可。
1.红黑树的介绍
4.红黑树的Java测试程序
转载请注明出处：
更多内容：
红黑树(Red-Black Tree，简称R-B Tree)，它一种特殊的二叉查找树。
红黑树是特殊的二叉查找树，意味着它满足二叉查找树的特征：任意一个节点所包含的键值，大于等于左孩子的键值，小于等于右孩子的键值。
除了具备该特性之外，红黑树还包括许多额外的信息。
红黑树的每个节点上都有存储位表示节点的颜色，颜色是红(Red)或黑(Black)。
红黑树的特性:
(1) 每个节点或者是黑色，或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]
(4) 如果一个节点是红色的，则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
关于它的特性，需要注意的是：
第一，特性(3)中的叶子节点，是只为空(NIL或null)的节点。
第二，特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。
红黑树示意图如下：
红黑树的Java实现(代码说明)
红黑树的基本操作是
。在对红黑树进行添加或删除后，会用到旋转方法。为什么呢？道理很简单，添加或删除红黑树中的节点之后，红黑树就发生了变化，可能不满足红黑树的5条性质，也就不再是一颗红黑树了，而是一颗普通的树。而通过旋转，可以使这颗树重新成为红黑树。简单点说，旋转的目的是让树保持红黑树的特性。
旋转包括两种：
。下面分别对红黑树的基本操作进行介绍。
1. 基本定义
public class RBTree&T extends Comparable&T&& {
private RBTNode&T& mR // 根结点
private static final boolean RED
private static final boolean BLACK = true;
public class RBTNode&T extends Comparable&T&& {
// 关键字(键值)
RBTNode&T& // 左孩子
RBTNode&T& // 右孩子
RBTNode&T& // 父结点
public RBTNode(T key, boolean color, RBTNode&T& parent, RBTNode&T& left, RBTNode&T& right) {
this.key =
this.color =
this.parent =
this.left =
this.right =
RBTree是红黑树对应的类，RBTNode是红黑树的节点类。在RBTree中包含了根节点mRoot和红黑树的相关API。
注意：在实现红黑树API的过程中，我重载了许多函数。重载的原因，一是因为有的API是内部接口，有的是外部接口；二是为了让结构更加清晰。
对x进行左旋，意味着&将x变成一个左节点&。
左旋的实现代码(Java语言)
* 对红黑树的节点(x)进行左旋转
* 左旋示意图(对节点x进行左旋)：
--(左旋)-.
private void leftRotate(RBTNode&T& x) {
// 设置x的右孩子为y
RBTNode&T& y = x.
// 将 “y的左孩子” 设为 “x的右孩子”；
// 如果y的左孩子非空，将 “x” 设为 “y的左孩子的父亲”
x.right = y.
if (y.left != null)
y.left.parent =
// 将 “x的父亲” 设为 “y的父亲”
y.parent = x.
if (x.parent == null) {
this.mRoot =
// 如果 “x的父亲” 是空节点，则将y设为根节点
if (x.parent.left == x)
x.parent.left = // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
x.parent.right = // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
// 将 “x” 设为 “y的左孩子”
// 将 “x的父节点” 设为 “y”
x.parent =
对y进行左旋，意味着&将y变成一个右节点&。
右旋的实现代码(Java语言)
* 对红黑树的节点(y)进行右旋转
* 右旋示意图(对节点y进行左旋)：
--(右旋)-.
private void rightRotate(RBTNode&T& y) {
// 设置x是当前节点的左孩子。
RBTNode&T& x = y.
// 将 “x的右孩子” 设为 “y的左孩子”；
// 如果&x的右孩子&不为空的话，将 “y” 设为 “x的右孩子的父亲”
y.left = x.
if (x.right != null)
x.right.parent =
// 将 “y的父亲” 设为 “x的父亲”
x.parent = y.
if (y.parent == null) {
this.mRoot =
// 如果 “y的父亲” 是空节点，则将x设为根节点
if (y == y.parent.right)
y.parent.right = // 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子”
y.parent.left = // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”
// 将 “y” 设为 “x的右孩子”
// 将 “y的父节点” 设为 “x”
y.parent =
将一个节点插入到红黑树中，需要执行哪些步骤呢？首先，将红黑树当作一颗二叉查找树，将节点插入；然后，将节点着色为红色；最后，通过&旋转和重新着色&等一系列操作来修正该树，使之重新成为一颗红黑树。详细描述如下：
第一步: 将红黑树当作一颗二叉查找树，将节点插入。
& & & &红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。也就意味着，树的键值仍然是有序的。此外，无论是左旋还是右旋，若旋转之前这棵树是二叉查找树，旋转之后它一定还是二叉查找树。这也就意味着，任何的旋转和重新着色操作，都不会改变它仍然是一颗二叉查找树的事实。
好吧？那接下来，我们就来想方设法的旋转以及重新着色，使这颗树重新成为红黑树！
第二步：将插入的节点着色为&红色&。
& & & &为什么着色成红色，而不是黑色呢？为什么呢？在回答之前，我们需要重新温习一下红黑树的特性：
(1) 每个节点或者是黑色，或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]
(4) 如果一个节点是红色的，则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
& & & 将插入的节点着色为红色，不会违背&特性(5)&！少违背一条特性，就意味着我们需要处理的情况越少。接下来，就要努力的让这棵树满足其它性质即可；满足了的话，它就又是一颗红黑树了。o(∩∩)o...哈哈
第三步: 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树。
& & & &第二步中，将插入节点着色为&红色&之后，不会违背&特性(5)&。那它到底会违背哪些特性呢？
& & & &对于&特性(1)&，显然不会违背了。因为我们已经将它涂成红色了。
& & & &对于&特性(2)&，显然也不会违背。在第一步中，我们是将红黑树当作二叉查找树，然后执行的插入操作。而根据二叉查找数的特点，插入操作不会改变根节点。所以，根节点仍然是黑色。
& & & &对于&特性(3)&，显然不会违背了。这里的叶子节点是指的空叶子节点，插入非空节点并不会对它们造成影响。
& & & &对于&特性(4)&，是有可能违背的！
& & & &那接下来，想办法使之&满足特性(4)&，就可以将树重新构造成红黑树了。
添加操作的实现代码(Java语言)
* 将结点插入到红黑树中
* 参数说明：
node 插入的结点
// 对应《算法导论》中的node
private void insert(RBTNode&T& node) {
RBTNode&T& y = null;
RBTNode&T& x = this.mR
// 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。
while (x != null) {
cmp = pareTo(x.key);
if (cmp & 0)
node.parent =
if (y!=null) {
cmp = pareTo(y.key);
if (cmp & 0)
this.mRoot =
// 2. 设置节点的颜色为红色
node.color = RED;
// 3. 将它重新修正为一颗二叉查找树
insertFixUp(node);
* 新建结点(key)，并将其插入到红黑树中
* 参数说明：
key 插入结点的键值
public void insert(T key) {
RBTNode&T& node=new RBTNode&T&(key,BLACK,null,null,null);
// 如果新建结点失败，则返回。
if (node != null)
insert(node);
-- insert(node)的作用是将&node&节点插入到红黑树中。
-- insert(key)的作用是将&key&添加到红黑树中。
添加修正操作的实现代码(Java语言)
* 红黑树插入修正函数
* 在向红黑树中插入节点之后(失去平衡)，再调用该函数；
* 目的是将它重新塑造成一颗红黑树。
* 参数说明：
node 插入的结点
// 对应《算法导论》中的z
private void insertFixUp(RBTNode&T& node) {
RBTNode&T& parent,
// 若“父节点存在，并且父节点的颜色是红色”
while (((parent = parentOf(node))!=null) && isRed(parent)) {
gparent = parentOf(parent);
//若“父节点”是“祖父节点的左孩子”
if (parent == gparent.left) {
// Case 1条件：叔叔节点是红色
RBTNode&T& uncle = gparent.
if ((uncle!=null) && isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
// Case 2条件：叔叔是黑色，且当前节点是右孩子
if (parent.right == node) {
RBTNode&T&
leftRotate(parent);
// Case 3条件：叔叔是黑色，且当前节点是左孩子。
setBlack(parent);
setRed(gparent);
rightRotate(gparent);
} else { //若“z的父节点”是“z的祖父节点的右孩子”
// Case 1条件：叔叔节点是红色
RBTNode&T& uncle = gparent.
if ((uncle!=null) && isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
// Case 2条件：叔叔是黑色，且当前节点是左孩子
if (parent.left == node) {
RBTNode&T&
rightRotate(parent);
// Case 3条件：叔叔是黑色，且当前节点是右孩子。
setBlack(parent);
setRed(gparent);
leftRotate(gparent);
// 将根节点设为黑色
setBlack(this.mRoot);
insertFixUp(node)的作用是对应&上面所讲的第三步&。它是一个内部接口。
5. 删除操作
将红黑树内的某一个节点删除。需要执行的操作依次是：首先，将红黑树当作一颗二叉查找树，将该节点从二叉查找树中删除；然后，通过&旋转和重新着色&等一系列来修正该树，使之重新成为一棵红黑树。详细描述如下：
第一步：将红黑树当作一颗二叉查找树，将节点删除。
& & & &这和&删除常规二叉查找树中删除节点的方法是一样的&。分3种情况：
① 被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就OK了。
② 被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。
③ 被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。在这里，后继节点相当于替身，在将后继节点的内容复制给&被删除节点&之后，再将后继节点删除。这样就巧妙的将问题转换为&删除后继节点&的情况了，下面就考虑后继节点。 在&被删除节点&有两个非空子节点的情况下，它的后继节点不可能是双子非空。既然&的后继节点&不可能双子都非空，就意味着&该节点的后继节点&要么没有儿子，要么只有一个儿子。若没有儿子，则按&情况① &进行处理；若只有一个儿子，则按&情况② &进行处理。
第二步：通过&旋转和重新着色&等一系列来修正该树，使之重新成为一棵红黑树。
& & & & 因为&第一步&中删除节点之后，可能会违背红黑树的特性。所以需要通过&旋转和重新着色&来修正该树，使之重新成为一棵红黑树。
删除操作的实现代码(Java语言)
* 删除结点(node)，并返回被删除的结点
* 参数说明：
node 删除的结点
private void remove(RBTNode&T& node) {
RBTNode&T& child,
// 被删除节点的&左右孩子都不为空&的情况。
if ( (node.left!=null) && (node.right!=null) ) {
// 被删节点的后继节点。(称为&取代节点&)
// 用它来取代&被删节点&的位置，然后再将&被删节点&去掉。
RBTNode&T& replace =
// 获取后继节点
replace = replace.
while (replace.left != null)
replace = replace.
// &node节点&不是根节点(只有根节点不存在父节点)
if (parentOf(node)!=null) {
if (parentOf(node).left == node)
parentOf(node).left =
parentOf(node).right =
// &node节点&是根节点，更新根节点。
this.mRoot =
// child是&取代节点&的右孩子，也是需要&调整的节点&。
// &取代节点&肯定不存在左孩子！因为它是一个后继节点。
child = replace.
parent = parentOf(replace);
// 保存&取代节点&的颜色
color = colorOf(replace);
// &被删除节点&是&它的后继节点的父节点&
if (parent == node) {
// child不为空
if (child!=null)
setParent(child, parent);
parent.left =
replace.right = node.
setParent(node.right, replace);
replace.parent = node.
replace.color = node.
replace.left = node.
node.left.parent =
if (color == BLACK)
removeFixUp(child, parent);
node = null;
if (node.left !=null) {
child = node.
child = node.
parent = node.
// 保存&取代节点&的颜色
color = node.
if (child!=null)
child.parent =
// &node节点&不是根节点
if (parent!=null) {
if (parent.left == node)
parent.left =
parent.right =
this.mRoot =
if (color == BLACK)
removeFixUp(child, parent);
node = null;
* 删除结点(z)，并返回被删除的结点
* 参数说明：
tree 红黑树的根结点
z 删除的结点
public void remove(T key) {
RBTNode&T&
if ((node = search(mRoot, key)) != null)
remove(node);
-- remove(node)的作用是将&node&节点插入到红黑树中。
-- remove(key)删除红黑树中键值为key的节点。
删除修正操作的实现代码(Java语言)
* 红黑树删除修正函数
* 在从红黑树中删除插入节点之后(红黑树失去平衡)，再调用该函数；
* 目的是将它重新塑造成一颗红黑树。
* 参数说明：
node 待修正的节点
private void removeFixUp(RBTNode&T& node, RBTNode&T& parent) {
RBTNode&T&
while ((node==null || isBlack(node)) && (node != this.mRoot)) {
if (parent.left == node) {
other = parent.
if (isRed(other)) {
// Case 1: x的兄弟w是红色的
setBlack(other);
setRed(parent);
leftRotate(parent);
other = parent.
if ((other.left==null || isBlack(other.left)) &&
(other.right==null || isBlack(other.right))) {
// Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
setRed(other);
parent = parentOf(node);
if (other.right==null || isBlack(other.right)) {
// Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
setBlack(other.left);
setRed(other);
rightRotate(other);
other = parent.
// Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
setColor(other, colorOf(parent));
setBlack(parent);
setBlack(other.right);
leftRotate(parent);
node = this.mR
other = parent.
if (isRed(other)) {
// Case 1: x的兄弟w是红色的
setBlack(other);
setRed(parent);
rightRotate(parent);
other = parent.
if ((other.left==null || isBlack(other.left)) &&
(other.right==null || isBlack(other.right))) {
// Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
setRed(other);
parent = parentOf(node);
if (other.left==null || isBlack(other.left)) {
// Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
setBlack(other.right);
setRed(other);
leftRotate(other);
other = parent.
// Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
setColor(other, colorOf(parent));
setBlack(parent);
setBlack(other.left);
rightRotate(parent);
node = this.mR
if (node!=null)
setBlack(node);
removeFixup(node, parent)是对应&上面所讲的第三步&。它是一个内部接口。
红黑树的Java实现(完整源码)
下面是红黑树实现的完整代码和相应的测试程序。
(1) 除了上面所说的&左旋&、&右旋&、&添加&、&删除&等基本操作之后，还实现了&遍历&、&查找&、&打印&、&最小值&、&最大值&、&创建&、&销毁&等接口。
(2) 函数接口大多分为内部接口和外部接口。内部接口是private函数，外部接口则是public函数。
(3) 测试代码中提供了&插入&和&删除&动作的检测开关。默认是关闭的，打开方法可以参考&代码中的说明&。建议在打开开关后，在草稿上自己动手绘制一下红黑树。
红黑树的实现文件(RBTree.java)
* Java 语言: 红黑树
* @author skywang
8 public class RBTree&T extends Comparable&T&& {
private RBTNode&T& mR
private static final boolean RED
private static final boolean BLACK = true;
public class RBTNode&T extends Comparable&T&& {
// 关键字(键值)
RBTNode&T&
RBTNode&T&
RBTNode&T&
public RBTNode(T key, boolean color, RBTNode&T& parent, RBTNode&T& left, RBTNode&T& right) {
this.key =
this.color =
this.parent =
this.left =
this.right =
public T getKey() {
public String toString() {
return &&+key+(this.color==RED?&(R)&:&B&);
public RBTree() {
mRoot=null;
private RBTNode&T& parentOf(RBTNode&T& node) {
return node!=null ? node.parent : null;
private boolean colorOf(RBTNode&T& node) {
return node!=null ? node.color : BLACK;
private boolean isRed(RBTNode&T& node) {
return ((node!=null)&&(node.color==RED)) ? true : false;
private boolean isBlack(RBTNode&T& node) {
return !isRed(node);
private void setBlack(RBTNode&T& node) {
if (node!=null)
node.color = BLACK;
private void setRed(RBTNode&T& node) {
if (node!=null)
node.color = RED;
private void setParent(RBTNode&T& node, RBTNode&T& parent) {
if (node!=null)
node.parent =
private void setColor(RBTNode&T& node, boolean color) {
if (node!=null)
node.color =
* 前序遍历&红黑树&
private void preOrder(RBTNode&T& tree) {
if(tree != null) {
System.out.print(tree.key+& &);
preOrder(tree.left);
preOrder(tree.right);
public void preOrder() {
preOrder(mRoot);
* 中序遍历&红黑树&
private void inOrder(RBTNode&T& tree) {
if(tree != null) {
inOrder(tree.left);
System.out.print(tree.key+& &);
inOrder(tree.right);
public void inOrder() {
inOrder(mRoot);
* 后序遍历&红黑树&
private void postOrder(RBTNode&T& tree) {
if(tree != null)
postOrder(tree.left);
postOrder(tree.right);
System.out.print(tree.key+& &);
public void postOrder() {
postOrder(mRoot);
* (递归实现)查找&红黑树x&中键值为key的节点
private RBTNode&T& search(RBTNode&T& x, T key) {
if (x==null)
int cmp = pareTo(x.key);
if (cmp & 0)
return search(x.left, key);
else if (cmp & 0)
return search(x.right, key);
public RBTNode&T& search(T key) {
return search(mRoot, key);
* (非递归实现)查找&红黑树x&中键值为key的节点
private RBTNode&T& iterativeSearch(RBTNode&T& x, T key) {
while (x!=null) {
int cmp = pareTo(x.key);
if (cmp & 0)
else if (cmp & 0)
public RBTNode&T& iterativeSearch(T key) {
return iterativeSearch(mRoot, key);
* 查找最小结点：返回tree为根结点的红黑树的最小结点。
private RBTNode&T& minimum(RBTNode&T& tree) {
if (tree == null)
return null;
while(tree.left != null)
tree = tree.
public T minimum() {
RBTNode&T& p = minimum(mRoot);
if (p != null)
return null;
* 查找最大结点：返回tree为根结点的红黑树的最大结点。
private RBTNode&T& maximum(RBTNode&T& tree) {
if (tree == null)
return null;
while(tree.right != null)
tree = tree.
public T maximum() {
RBTNode&T& p = maximum(mRoot);
if (p != null)
return null;
* 找结点(x)的后继结点。即，查找&红黑树中数据值大于该结点&的&最小结点&。
public RBTNode&T& successor(RBTNode&T& x) {
// 如果x存在右孩子，则&x的后继结点&为 &以其右孩子为根的子树的最小结点&。
if (x.right != null)
return minimum(x.right);
// 如果x没有右孩子。则x有以下两种可能：
// (01) x是&一个左孩子&，则&x的后继结点&为 &它的父结点&。
// (02) x是&一个右孩子&，则查找&x的最低的父结点，并且该父结点要具有左孩子&，找到的这个&最低的父结点&就是&x的后继结点&。
RBTNode&T& y = x.
while ((y!=null) && (x==y.right)) {
* 找结点(x)的前驱结点。即，查找&红黑树中数据值小于该结点&的&最大结点&。
public RBTNode&T& predecessor(RBTNode&T& x) {
// 如果x存在左孩子，则&x的前驱结点&为 &以其左孩子为根的子树的最大结点&。
if (x.left != null)
return maximum(x.left);
// 如果x没有左孩子。则x有以下两种可能：
// (01) x是&一个右孩子&，则&x的前驱结点&为 &它的父结点&。
// (01) x是&一个左孩子&，则查找&x的最低的父结点，并且该父结点要具有右孩子&，找到的这个&最低的父结点&就是&x的前驱结点&。
RBTNode&T& y = x.
while ((y!=null) && (x==y.left)) {
* 对红黑树的节点(x)进行左旋转
* 左旋示意图(对节点x进行左旋)：
--(左旋)-.
private void leftRotate(RBTNode&T& x) {
// 设置x的右孩子为y
RBTNode&T& y = x.
// 将 “y的左孩子” 设为 “x的右孩子”；
// 如果y的左孩子非空，将 “x” 设为 “y的左孩子的父亲”
x.right = y.
if (y.left != null)
y.left.parent =
// 将 “x的父亲” 设为 “y的父亲”
y.parent = x.
if (x.parent == null) {
this.mRoot =
// 如果 “x的父亲” 是空节点，则将y设为根节点
if (x.parent.left == x)
x.parent.left =
// 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
x.parent.right =
// 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
// 将 “x” 设为 “y的左孩子”
// 将 “x的父节点” 设为 “y”
x.parent =
* 对红黑树的节点(y)进行右旋转
* 右旋示意图(对节点y进行左旋)：
--(右旋)-.
private void rightRotate(RBTNode&T& y) {
// 设置x是当前节点的左孩子。
RBTNode&T& x = y.
// 将 “x的右孩子” 设为 “y的左孩子”；
// 如果&x的右孩子&不为空的话，将 “y” 设为 “x的右孩子的父亲”
y.left = x.
if (x.right != null)
x.right.parent =
// 将 “y的父亲” 设为 “x的父亲”
x.parent = y.
if (y.parent == null) {
this.mRoot =
// 如果 “y的父亲” 是空节点，则将x设为根节点
if (y == y.parent.right)
y.parent.right =
// 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子”
y.parent.left =
// (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”
// 将 “y” 设为 “x的右孩子”
// 将 “y的父节点” 设为 “x”
y.parent =
* 红黑树插入修正函数
* 在向红黑树中插入节点之后(失去平衡)，再调用该函数；
* 目的是将它重新塑造成一颗红黑树。
* 参数说明：
node 插入的结点
// 对应《算法导论》中的z
private void insertFixUp(RBTNode&T& node) {
RBTNode&T& parent,
// 若“父节点存在，并且父节点的颜色是红色”
while (((parent = parentOf(node))!=null) && isRed(parent)) {
gparent = parentOf(parent);
//若“父节点”是“祖父节点的左孩子”
if (parent == gparent.left) {
// Case 1条件：叔叔节点是红色
RBTNode&T& uncle = gparent.
if ((uncle!=null) && isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
// Case 2条件：叔叔是黑色，且当前节点是右孩子
if (parent.right == node) {
RBTNode&T&
leftRotate(parent);
// Case 3条件：叔叔是黑色，且当前节点是左孩子。
setBlack(parent);
setRed(gparent);
rightRotate(gparent);
//若“z的父节点”是“z的祖父节点的右孩子”
// Case 1条件：叔叔节点是红色
RBTNode&T& uncle = gparent.
if ((uncle!=null) && isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
// Case 2条件：叔叔是黑色，且当前节点是左孩子
if (parent.left == node) {
RBTNode&T&
rightRotate(parent);
// Case 3条件：叔叔是黑色，且当前节点是右孩子。
setBlack(parent);
setRed(gparent);
leftRotate(gparent);
// 将根节点设为黑色
setBlack(this.mRoot);
* 将结点插入到红黑树中
* 参数说明：
node 插入的结点
// 对应《算法导论》中的node
private void insert(RBTNode&T& node) {
RBTNode&T& y = null;
RBTNode&T& x = this.mR
// 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。
while (x != null) {
cmp = pareTo(x.key);
if (cmp & 0)
node.parent =
if (y!=null) {
cmp = pareTo(y.key);
if (cmp & 0)
this.mRoot =
// 2. 设置节点的颜色为红色
node.color = RED;
// 3. 将它重新修正为一颗二叉查找树
insertFixUp(node);
* 新建结点(key)，并将其插入到红黑树中
* 参数说明：
key 插入结点的键值
public void insert(T key) {
RBTNode&T& node=new RBTNode&T&(key,BLACK,null,null,null);
// 如果新建结点失败，则返回。
if (node != null)
insert(node);
* 红黑树删除修正函数
* 在从红黑树中删除插入节点之后(红黑树失去平衡)，再调用该函数；
* 目的是将它重新塑造成一颗红黑树。
* 参数说明：
node 待修正的节点
private void removeFixUp(RBTNode&T& node, RBTNode&T& parent) {
RBTNode&T&
while ((node==null || isBlack(node)) && (node != this.mRoot)) {
if (parent.left == node) {
other = parent.
if (isRed(other)) {
// Case 1: x的兄弟w是红色的
setBlack(other);
setRed(parent);
leftRotate(parent);
other = parent.
if ((other.left==null || isBlack(other.left)) &&
(other.right==null || isBlack(other.right))) {
// Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
setRed(other);
parent = parentOf(node);
if (other.right==null || isBlack(other.right)) {
// Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
setBlack(other.left);
setRed(other);
rightRotate(other);
other = parent.
// Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
setColor(other, colorOf(parent));
setBlack(parent);
setBlack(other.right);
leftRotate(parent);
node = this.mR
other = parent.
if (isRed(other)) {
// Case 1: x的兄弟w是红色的
setBlack(other);
setRed(parent);
rightRotate(parent);
other = parent.
if ((other.left==null || isBlack(other.left)) &&
(other.right==null || isBlack(other.right))) {
// Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
setRed(other);
parent = parentOf(node);
if (other.left==null || isBlack(other.left)) {
// Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
setBlack(other.right);
setRed(other);
leftRotate(other);
other = parent.
// Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
setColor(other, colorOf(parent));
setBlack(parent);
setBlack(other.left);
rightRotate(parent);
node = this.mR
if (node!=null)
setBlack(node);
* 删除结点(node)，并返回被删除的结点
* 参数说明：
node 删除的结点
private void remove(RBTNode&T& node) {
RBTNode&T& child,
// 被删除节点的&左右孩子都不为空&的情况。
if ( (node.left!=null) && (node.right!=null) ) {
// 被删节点的后继节点。(称为&取代节点&)
// 用它来取代&被删节点&的位置，然后再将&被删节点&去掉。
RBTNode&T& replace =
// 获取后继节点
replace = replace.
while (replace.left != null)
replace = replace.
// &node节点&不是根节点(只有根节点不存在父节点)
if (parentOf(node)!=null) {
if (parentOf(node).left == node)
parentOf(node).left =
parentOf(node).right =
// &node节点&是根节点，更新根节点。
this.mRoot =
// child是&取代节点&的右孩子，也是需要&调整的节点&。
// &取代节点&肯定不存在左孩子！因为它是一个后继节点。
child = replace.
parent = parentOf(replace);
// 保存&取代节点&的颜色
color = colorOf(replace);
// &被删除节点&是&它的后继节点的父节点&
if (parent == node) {
// child不为空
if (child!=null)
setParent(child, parent);
parent.left =
replace.right = node.
setParent(node.right, replace);
replace.parent = node.
replace.color = node.
replace.left = node.
node.left.parent =
if (color == BLACK)
removeFixUp(child, parent);
node = null;
if (node.left !=null) {
child = node.
child = node.
parent = node.
// 保存&取代节点&的颜色
color = node.
if (child!=null)
child.parent =
// &node节点&不是根节点
if (parent!=null) {
if (parent.left == node)
parent.left =
parent.right =
this.mRoot =
if (color == BLACK)
removeFixUp(child, parent);
node = null;
* 删除结点(z)，并返回被删除的结点
* 参数说明：
tree 红黑树的根结点
z 删除的结点
public void remove(T key) {
RBTNode&T&
if ((node = search(mRoot, key)) != null)
remove(node);
* 销毁红黑树
private void destroy(RBTNode&T& tree) {
if (tree==null)
if (tree.left != null)
destroy(tree.left);
if (tree.right != null)
destroy(tree.right);
tree=null;
public void clear() {
destroy(mRoot);
mRoot = null;
* 打印&红黑树&
-- 节点的键值
* direction
0，表示该节点是根节点;
-1，表示该节点是它的父结点的左孩子;
1，表示该节点是它的父结点的右孩子。
private void print(RBTNode&T& tree, T key, int direction) {
if(tree != null) {
if(direction==0)
// tree是根节点
System.out.printf(&%2d(B) is root\n&, tree.key);
// tree是分支节点
System.out.printf(&%2d(%s) is %2d's %6s child\n&, tree.key, isRed(tree)?&R&:&B&, key, direction==1?&right& : &left&);
print(tree.left, tree.key, -1);
print(tree.right,tree.key,
public void print() {
if (mRoot != null)
print(mRoot, mRoot.key, 0);
红黑树的测试文件(RBTreeTest.java)
* Java 语言: 二叉查找树
* @author skywang
7 public class RBTreeTest {
private static final int a[] = {10, 40, 30, 60, 90, 70, 20, 50, 80};
private static final boolean mDebugInsert = false;
// &插入&动作的检测开关(false，关闭；true，打开)
private static final boolean mDebugDelete = false;
// &删除&动作的检测开关(false，关闭；true，打开)
public static void main(String[] args) {
int i, ilen = a.
RBTree&Integer& tree=new RBTree&Integer&();
System.out.printf(&== 原始数据: &);
for(i=0; i& i++)
System.out.printf(&%d &, a[i]);
System.out.printf(&\n&);
for(i=0; i& i++) {
tree.insert(a[i]);
// 设置mDebugInsert=true,测试&添加函数&
if (mDebugInsert) {
System.out.printf(&== 添加节点: %d\n&, a[i]);
System.out.printf(&== 树的详细信息: \n&);
tree.print();
System.out.printf(&\n&);
System.out.printf(&== 前序遍历: &);
tree.preOrder();
System.out.printf(&\n== 中序遍历: &);
tree.inOrder();
System.out.printf(&\n== 后序遍历: &);
tree.postOrder();
System.out.printf(&\n&);
System.out.printf(&== 最小值: %s\n&, tree.minimum());
System.out.printf(&== 最大值: %s\n&, tree.maximum());
System.out.printf(&== 树的详细信息: \n&);
tree.print();
System.out.printf(&\n&);
// 设置mDebugDelete=true,测试&删除函数&
if (mDebugDelete) {
for(i=0; i& i++)
tree.remove(a[i]);
System.out.printf(&== 删除节点: %d\n&, a[i]);
System.out.printf(&== 树的详细信息: \n&);
tree.print();
System.out.printf(&\n&);
// 销毁二叉树
tree.clear();
红黑树的Java测试程序
前面已经给出了红黑树的测试代码(RBTreeTest.java)，这里就不再重复说明。下面是测试程序的运行结果：
== 原始数据: 10 40 30 60 90 70 20 50 80
== 前序遍历: 30 10 20 60 40 50 80 70 90
== 中序遍历: 10 20 30 40 50 60 70 80 90
== 后序遍历: 20 10 50 40 70 90 80 60 30
== 最小值: 10
== 最大值: 90
== 树的详细信息:
30(B) is root
10(B) is 30's
left child
20(R) is 10's
right child
60(R) is 30's
right child
40(B) is 60's
left child
50(R) is 40's
right child
80(B) is 60's
right child
70(R) is 80's
left child
90(R) is 80's
right child
已发表评论数()
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见
正文不准确
标题不准确
排版有问题
主题不准确
没有分页内容
图片无法显示
视频无法显示
与原文不一致}