2025年（1小时数据结构）数据结构c++描述（二十四）--- 红黑树

大家好，我是讯享网，很高兴认识大家。

本章的红黑树，在《数据结构与算法c++描述》中只是提了相关知识点，但是没有细讲相关内容，本人结合此书，与其他参考书籍与网上相关博客，记录一下红黑树的数据结构，与其对应的代码：

红黑树定义：

红黑树是一种二叉搜索树，并且相对于二叉搜索树做了一定的改进。

书的节点包括5个属性：key 、color、p、left、right。

红黑树具有下列五种性质：

根节点黑色。
每个节点为红色/黑色。
每个叶节点（NIL）是黑的。
红色节点下两个节点必为黑色。
从任一节点到其叶子节点的所有路径上都包含相同数目的黑节点。

设书的高度为h，节点为n，他们之间的关系就是： $n\geq 2^{h/2} -1$
讯享网

定义来自《算法导论第三版》

如图：

为了方便，让所有NIL都是一样的，就可以变成：

上边的图是不是不好看，换个有颜色的图吧，上边为算法导论中的图。

红黑树的节点：

/* 数组结构中 RBTree 对应书中代码：数据结构算法与应用c++描述 程序编写：比卡丘不皮 编写时间：2020年7月29日 14:20:23 */ #pragma once #include<iostream> using namespace std; template<class T> class RBTreeNode { public: T key; //主要的值 RBTreeNode *p; //父亲节点 RBTreeNode *left; //左节点 RBTreeNode *right; //右节点 enum Color { RED, BREAK }; Color color; //颜色 RBTreeNode(T k):key(k) { p = left = right = NULL; color = BREAK; } };

讯享网

红黑树类

讯享网//这里定义了NIL 节点，为了方便，所有的“叶子点”都指向它 RBTreeNode<int> nil(-1); RBTreeNode<int> *NIL = &nil; template<class T> class RBTree { public: RBTree() //初始化 { root = NIL; } RBTree(RBTreeNode<T> * n); //初始化 RBTreeNode<T> * Search(T k); //查找k值返回当前节点指针 bool IsEmpty()const //判断AVLTree是否为空 { return root == NULL; } void InOrder() //中序遍历节点 { InOrder(root); } //找到最大值 T MaxNum(); //找到最小值 T miniNum(); RBTreeNode<T> * Predecessor(RBTreeNode<T> * u); //前者 RBTreeNode<T> * Successor(RBTreeNode<T> * u);//继承者 RBTreeNode<T> * insert(T k); bool Delete(T k); private: void InOrder(RBTreeNode<T> * n) const; //中序遍历节点 RBTreeNode<T> * root; //根节点 RBTreeNode<T> * miniNum(RBTreeNode<T> * u); RBTreeNode<T>* MaxNum(RBTreeNode<T> * u); void InsertFixup(RBTreeNode<T> * u); //插入修正 void DeleteFixup(RBTreeNode<T> * u); //删除修正 void LeftRotate(RBTreeNode<T> * u); //左旋 void RightRotate(RBTreeNode<T> * u); //右旋 void TransPlant(RBTreeNode<T> * u1, RBTreeNode<T> * u2); };

初始化函数：

template<class T> RBTree<T>::RBTree(RBTreeNode<T> * n):root(n) { n->p = n->left = n->right = NIL; }

收索函数：

讯享网 template<class T> RBTreeNode<T>* RBTree<T>::Search(T k) { RBTreeNode<T>* cur = root; while (cur->key != k) { if (cur->key < k && cur->right != NIL) { cur = cur->right; } else if (cur->key>k&&cur->left != NIL) { cur = cur->left; } else { return NIL; } } return cur; }

本树的最大值最小值：

 template<class T> T RBTree<T>::MaxNum() { RBTreeNode<T> * cur = root; while (cur->right != NIL) { cur = cur->right; } return cur->key; } template<class T> T RBTree<T>::miniNum() { RBTreeNode<T> * cur = root; while (cur->left != NIL) { cur = cur->left; } return cur->key; }

当前节点下的最大，最小值

讯享网template<class T> RBTreeNode<T>* RBTree<T>::miniNum(RBTreeNode<T> * u) { RBTreeNode<T> * cur = u; while (cur->left != NIL) { cur = cur->left; } return cur; } template<class T> RBTreeNode<T>* RBTree<T>::MaxNum(RBTreeNode<T>* u) { RBTreeNode<T> * cur = u; while (cur->right != NIL) { cur = cur->right; } return cur; }

InOrder中序遍历：

//中序遍历 template<class T> void RBTree<T>::InOrder(RBTreeNode<T> * n) const { if (n != NIL) { InOrder(n->left); cout << n->key << " "; InOrder(n->right); } }

旋转：

红黑树的查找操作与二叉搜索树BST完全一致。但是插入和删除算法会破坏红黑树的性质。所以对红黑树执行删除、插入操作后需要调整使其恢复红黑树性质。调整过程仅需要少量的染色（O(log n) 或者 O(1)的复杂度）和至多3次的旋转操作（插入仅需2次）。虽然这样会使插入、删除操作很复杂，但其时间复杂度仍然在O(log n)以内。

两种旋转，如下动态图：

左旋：

为方便理解其中 u 是 11 u2指向了18

讯享网 //左转， template<class T> void RBTree<T>::LeftRotate(RBTreeNode<T>* u) { RBTreeNode<T> * u2 = u->right; u->right = u2->left; if (u2->left != NIL) { u2->left->p = u; //u是 u2->left的父亲 } u2->p = u->p; if (u->p == NIL) //u为根简单 { root = u2; } else if ( u == u->p->left) { u->p->left = u2; } else //在右边 { u->p->right = u2; } u2->left = u; u->p = u2; }

右旋：

右旋是上图反过来，这个时候u 为18，u2 为11

 template<class T> void RBTree<T>::RightRotate(RBTreeNode<T>* u) { RBTreeNode<T> * u2 = u->left; u->left = u2->right; if (u2->right != NIL) { u2->right->p = u; } u2->p = u->p; //右转导致U的父亲变成u2的父亲。 if (u->p == NIL) { root = u2; } else if (u == u->p->left) { u->p->left = u2; } else { u->p->right = u2; } u2->right = u; u->p = u2; }

插入部分：

由于性质的约束：插入点不能为黑节点，应插入红节点。因为你插入黑节点将破坏性质5，所以每次插入的点都是红结点，但是若他的父节点也为红，那岂不是破坏了性质4？对啊，所以要做一些“旋转”和一些节点的变色！另为叙述方便我们给要插入的节点标为N（红色），父节点为P，祖父节点为G，叔节点为U。下边将一一列出所有插入时遇到的情况：

情况1：该树为空树，直接插入根结点的位置，违反性质1，把节点颜色有红改为黑即可。

情况2：插入节点N的父节点P为黑色，不违反任何性质，无需做任何修改。

情况3：N为红，P为红，（祖节点一定存在，且为黑，下边同理）U也为红，这里不论P是G的左孩子，还是右孩子；不论N是P的左孩子，还是右孩子。

操作：如图把P、U改为黑色，G改为红色，未结束。

N、P都为红，违反性质4；若把P改为黑，符合性质4，显然左边少了一个黑节点，违反性质5；所以我们把G，U都改为相反色，这样一来通过G的路径的黑节点数目没变，即符合4、5，但是G变红了，若G的父节点又是红的不就有违反了4，是这样，所以经过上边操作后未结束，需把G作为起始点，即把G看做一个插入的红节点继续向上检索----属于哪种情况，按那种情况操作~要么中间就结束，要么知道根结点（此时根结点变红，一根结点向上检索，那木有了，那就把他变为黑色吧）。

情况4：N为红，P为红，U为黑，P为G的左孩子，N为P的左孩子（或者P为G的右孩子，N为P的左孩子；反正就是同向的）。

操作：如图P、G变色，P、G变换即左左单旋（或者右右单旋），结束。

解析：要知道经过P、G变换（旋转），变换后P的位置就是当年G的位置，所以红P变为黑，而黑G变为红都是为了不违反性质5，而维持到达叶节点所包含的黑节点的数目不变！还可以理解为：也就是相当于（只是相当于，并不是实事，只是为了更好理解；）把红N头上的红节点移到对面黑U的头上；这样即符合了性质4也不违反性质5，这样就结束了。

情况5：N为红，P为红，U为黑，P为G的左孩子，N为P的右孩子（或者P为G的右孩子，N为P的左孩子；反正两方向相反）。

操作：需要进行两次变换（旋转），图中只显示了一次变换-----首先P、N变换，颜色不变；然后就变成了情形4的情况，按照情况4操作，即结束。

解析：由于P、N都为红，经变换，不违反性质5；然后就变成4的情形，此时G与G现在的左孩子变色，并变换，结束。

在《算法导论》中，情况3,4,5.对应的就是对应的1 2 3，看算法导论可以对应的来解决。

插入函数：

讯享网template<class T> RBTreeNode<T>* RBTree<T>::insert(T k) { RBTreeNode<T>* cur = root; RBTreeNode<T>* prev = root; while (cur != NIL && (cur != NULL)) { prev = cur; if (k < cur->key) //小的放左边 { cur = cur->left; } else if (k > cur->key) //大的放右边 { cur = cur->right; } else //插入的相等 { cout << "当前节点已经存在，不予插入" << endl; return NIL; } } if (IsEmpty()) //若根指向了NIL { root = new RBTreeNode<T>(k); return root; } if (k < prev->key) { prev->left = new RBTreeNode<T>(k); prev->left->p = prev; prev->left->left = prev->left->right = NIL; prev->left->color = RBTreeNode<T>::RED; //记录为红色 InsertFixup(prev->left); return prev->left; } else if (k > prev->key) { prev->right = new RBTreeNode<T>(k); prev->right->p = prev; prev->right->left = prev->right->right = NIL; prev->right->color = RBTreeNode<T>::RED; //记录为红色 InsertFixup(prev->right); return prev->right; } return NIL; }

InsertFixup：

插入数据后可能会出现问题，通过此函数修订后，解决上面的情况。仔细读取代码，你会更好的理解。

 template<class T> void RBTree<T>::InsertFixup(RBTreeNode<T>* u) { //判断当前的父节点是不是红的，红的改变 while (u->p->color == RBTreeNode<T>::RED) { if (u->p == u->p->p->left) //父节点在祖父的左边 { RBTreeNode<T> * uncle = u->p->p->right; //当nucle的颜色为红色的时候 为情况3（算法导论中的情况1） if (uncle->color == RBTreeNode<T>::RED) { u->p->color = uncle->color = RBTreeNode<T>::BLACK; u->p->p->color = RBTreeNode<T>::RED; u = u->p->p; //让祖父位新的节点，知道遍历到根节点，然后让跟节点 } else //当nucle的颜色为黑色的时候 { //当nucle的颜色为黑色的时候 为情况4 （算法导论中的情况3） if ( (uncle->color == RBTreeNode<T>::BLACK) && (u == u->p->left) ) { u->p->color = RBTreeNode<T>::BLACK; u->p->p->color = RBTreeNode<T>::RED; RightRotate(u->p->p); //右转 都在左边 } //当nucle的颜色为黑色的时候 为情况5先变4 （算法导论中的情况2 变3） else if ((uncle->color == RBTreeNode<T>::BLACK) && (u == u->p->right) ) { u = u->p; LeftRotate(u); } } } else if (u->p == u->p->p->right) //父节点在祖父的右边 { RBTreeNode<T> * uncle = u->p->p->left; //当nucle的颜色为红色的时候 为情况3（算法导论中的情况1） if (uncle->color == RBTreeNode<T>::RED) { u->p->color = uncle->color = RBTreeNode<T>::BLACK; u->p->p->color = RBTreeNode<T>::RED; u = u->p->p; //让祖父位新的节点，知道遍历到根节点，然后让跟节点 } else { //当nucle的颜色为黑色的时候 为情况4 （算法导论中的情况3） if ((uncle->color == RBTreeNode<T>::BLACK) && (u == u->p->right)) { u->p->color = RBTreeNode<T>::BLACK; u->p->p->color = RBTreeNode<T>::RED; LeftRotate(u->p->p); }//当nucle的颜色为黑色的时候 为情况5先变4 （算法导论中的情况2 变3） else if ((uncle->color == RBTreeNode<T>::BLACK) && (u == u->p->left) ) { u = u->p; RightRotate(u); } } } } root->color = RBTreeNode<T>::BLACK; //根节点一定是黑的 }

删除：

情况1：S为红色（那么父节点P一定是黑，子节点一定是黑），N是P的左孩子（或者N是P的右孩子）。

操作：P、S变色，并交换----相当于AVL中的右右中旋转即以P为中心S向左旋（或者是AVL中的左左中的旋转），未结束。

解析：我们知道P的左边少了一个黑节点，这样操作相当于在N头上又加了一个红节点----不违反任何性质，但是到通过N的路径仍少了一个黑节点，需要再把对N进行一次检索，并作相应的操作才可以平衡。

情况2：P、S及S的孩子们都为黑。

操作：S改为红色，未结束。
解析：S变为红色后经过S节点的路径的黑节点数目也减少了1，那个从P出发到其叶子节点到所有路径所包含的黑节点数目（记为num）相等了。但是这个num比之前少了1，因为左右子树中的黑节点数目都减少了！一般地，P是他父节点G的一个孩子，那么由G到其叶子节点的黑节点数目就不相等了，所以说没有结束，需把P当做新的起始点开始向上检索。

情况3： P为红（S一定为黑），S的孩子们都为黑。

操作：P该为黑，S改为红，结束。

解析：这种情况最简单了，既然N这边少了一个黑节点，那么S这边就拿出了一个黑节点来共享一下，这样一来，S这边没少一个黑节点，而N这边便多了一个黑节点，这样就恢复了平衡，多么美好的事情哈！

情况4: P任意色，S为黑，N是P的左孩子，S的右孩子SR为红，S的左孩子任意（或者是N是P的右孩子，S的左孩子为红，S的右孩子任意）。

操作：SR（SL）改为黑，P改为黑，S改为P的颜色，P、S变换--这里相对应于AVL中的右右中的旋转（或者是AVL中的左左旋转），结束。
解析：P、S旋转有变色，等于给N这边加了一个黑节点，P位置（是位置而不是P）的颜色不变，S这边少了一个黑节点；SR有红变黑，S这边又增加了一个黑节点；这样一来又恢复了平衡，结束。

情况5:P任意色，S为黑，N是P的左孩子，S的左孩子SL为红，S的右孩子SR为黑（或者N是P的有孩子，S的右孩子为红，S的左孩子为黑）。

操作：SL（或SR）改为黑，S改为红，SL（SR）、S变换；此时就回到了情形4，SL（SR）变成了黑S，S变成了红SR（SL），做情形4的操作即可，这两次变换，其实就是对应AVL的右左的两次旋转（或者是AVL的左右的两次旋转）。删除

删除函数：

讯享网template<class T> bool RBTree<T>::Delete(T k) { RBTreeNode<T> * toDelete = Search(k); if (toDelete == NIL) { return false; } RBTreeNode<T> * toReplace = toDelete; RBTreeNode<T> ::Color original_color = toDelete->color; RBTreeNode<T> * tRTR; toReplace->color = toDelete->color; if (toDelete->left == NIL) { tRTR = toDelete->right; TransPlant(toDelete, toDelete->right); } else if (toDelete->right == NIL) { tRTR = toDelete->left; TransPlant(toDelete, toDelete->left); } else { toReplace = Successor(toDelete); //找到要删除toDelete右节点的最小值的位置 original_color = toReplace->color; tRTR = toReplace->right; //当前最小节点，的右子树，或者是NIL if (toReplace->p == toDelete) { tRTR->p = toReplace; } else { //删除替换的点 TransPlant(toReplace, toReplace->right); toReplace->right = toDelete->right; toReplace->right->p = toReplace; } //将替换的点与 本该删除的点互换。 TransPlant(toDelete, toReplace); toReplace->left = toDelete->left; toReplace->left->p = toReplace; toReplace->color = toDelete->color; } //当删除的点是红的话，没有关系，当删除的点是黑色的就是上面的情况 if (original_color == RBTreeNode<T>::BLACK) { DeleteFixup(tRTR); } return true; }

DeleteFixup函数：

 template<class T> void RBTree<T>::DeleteFixup(RBTreeNode<T>* u) { while (u != root && u->color == RBTreeNode<T>::BLACK) { if (u == u->p->left) { RBTreeNode<T> * S = u->p->right; if (S->color == RBTreeNode<T>::RED) //情况1 { S->color = RBTreeNode<T>::BLACK; //S变红 u->p->color = RBTreeNode<T>::RED; //图中的p变红 LeftRotate(u->p); //左旋 S = u->p->right; }else if (S->left->color == RBTreeNode<T>::BLACK && (S->right->color == RBTreeNode<T>::BLACK) )//情况3 或 2（有情况1变成3） 对应书中情况2 { S->color = RBTreeNode<T>::RED; u = u->p; //如果是黑色向上遍历, 若是红的话，把u变黑就结束了 } else if (S->right->color == RBTreeNode<T>::RED) //情况4 { S->right->color = RBTreeNode<T>::BLACK; RBTreeNode<T>::Color temp = u->p->color; S->color = temp; u->p->color = RBTreeNode<T>::BLACK; LeftRotate(u->p); u = root; //完全结束 } else if (S->left->color == RBTreeNode<T>::RED && (S->right->color == RBTreeNode<T>::BLACK) && (S->color == RBTreeNode<T>::BLACK) ) //情况5 转化成4 { S->color = RBTreeNode<T>::RED; S->left->color = RBTreeNode<T>::BLACK; RightRotate(S);//然后变成了4的情况 } } else if (u == u->p->right) { RBTreeNode<T> * S = u->p->left; if (S->color == RBTreeNode<T>::RED) { S->color = RBTreeNode<T>::BLACK; //S变红 u->p->color = RBTreeNode<T>::RED; //图中的p变红 RightRotate(u->p); S = u->p->left; } else if (S->left->color == RBTreeNode<T>::BLACK && (S->right->color == RBTreeNode<T>::BLACK) ) { S->color = RBTreeNode<T>::RED; u = u->p; //如果是黑色向上遍历, 若是红的话，把u变黑就结束了 } else if (S->left->color == RBTreeNode<T>::RED) //情况4 { S->left->color == RBTreeNode<T>::BLACK; RBTreeNode<T>::Color temp = u->p->color; S->color = temp; u->p->color = RBTreeNode<T>::BLACK; RightRotate(u->p); u = root; } else if (S->color == RBTreeNode<T>::BLACK && (S->left->color == RBTreeNode<T>::BLACK)&& (S->right->color == RBTreeNode<T>::RED)) { S->color = RBTreeNode<T>::RED; S->right->color = RBTreeNode<T>::BLACK; LeftRotate(S); } } } u->color = RBTreeNode<T>::BLACK; }

Predecessor 与 Successor 函数：

讯享网template<class T> RBTreeNode<T>* RBTree<T>::Predecessor(RBTreeNode<T>* u) { if (u->left != NIL) { return MaxNum(u->left); } else if (u->p != NIL) { return u->p; } else { return NIL; } } template<class T> RBTreeNode<T>* RBTree<T>::Successor(RBTreeNode<T>* u) { if (u->right != NIL) { return miniNum(u->right); } else if (u->p != NIL) { return u->p; } else { return NIL; } }

测试函数：

void testBRTree() { int arr[] = { 3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9 }; int length = sizeof(arr) / sizeof(arr[0]); cout << "源数组为：" << endl; for (int i = 0; i < length; i++) { cout << arr[i] << " "; } cout << endl; RBTree<int> *tree = new RBTree<int>(); for (int i = 0; i < length; i++) { tree->insert(arr[i]); } cout << endl; cout << "中序遍历：" << endl; tree->InOrder(); int Value = 8; cout << "\n删除根节点: " << Value; tree->Delete(Value); cout << endl; cout << "中序遍历：" << endl; tree->InOrder(); }

输出结果：

红黑树算是完成了，需要代码的可以私信我，真的十分的有趣。主要目的是了解插入与删除的情况，很有趣的。