博客轉(zhuǎn)自自己的新浪博客，屬于自己原創(chuàng) 下面對紅黑樹刪除某節(jié)點(diǎn)后，旋轉(zhuǎn)三次的例子做出詳解： 先利用代碼建立樹如下： 修改顏色分布為下列樹：



修改顏色分布后，利用 tree->insert(1); tree->remove(1); 來判斷是否是紅黑樹 如果不是紅黑樹，在插入刪除的過程中，會進(jìn)入各個case，并有相關(guān)語句會輸出到cmd上。顯然，上述語句執(zhí)行后，沒有任何信息，說明修改顏色分布后依然為一棵標(biāo)準(zhǔn)的紅黑樹樹。 然后刪除黑節(jié)點(diǎn)10； 由于刪除的節(jié)點(diǎn)是葉子節(jié)點(diǎn)（黑），所以左右子節(jié)點(diǎn)都是NULL； 下面開始對刪除過程中四種修正case進(jìn)行分析
首先進(jìn)入case 2 對被刪除節(jié)點(diǎn)10的兄弟節(jié)點(diǎn)27染色，改為紅 執(zhí)行后效果如下：

---

由于node不為紅色節(jié)點(diǎn)，所以繼續(xù)進(jìn)行下輪的while循環(huán)，此時進(jìn)入case 1 染色后（橙黃色代表將要進(jìn)行旋轉(zhuǎn)的部分，下同）


左旋后

---

之后進(jìn)入case 3
染色后


準(zhǔn)備右旋轉(zhuǎn)，旋轉(zhuǎn)后并且調(diào)整other后如下：

---

最后進(jìn)入case 4 染色前



讓other的顏色等于parent的顏色，parent變黑，other->right變黑，處理后如下：



開始左旋，左旋后結(jié)果如下：

---

最終刪除節(jié)點(diǎn)10，結(jié)果如下：


使用測試代碼為#include"RBTree.h" #include #include #include using namespace std;int main() {//int a[] = {40,20,60,50,80,70,90 }; int a[] = { 35,20,10,27,400,105,600,70,150,500,700,50,85 };int check_insert = 0; // "插入"動作的檢測開關(guān)(0，關(guān)閉；1，打開) int check_remove = 0; // "刪除"動作的檢測開關(guān)(0，關(guān)閉；1，打開) int i; int ilen = (sizeof(a)) / (sizeof(a[0])); RBTree* tree = new RBTree();cout << "== 原始數(shù)據(jù): "; for (i = 0; i cout << a[i] << " "; cout << endl;for (i = 0; i { tree->insert(a[i]); // 設(shè)置check_insert=1,測試"添加函數(shù)" if (check_insert) { cout << "== 添加節(jié)點(diǎn): " << a[i] << endl; cout << "== 樹的詳細(xì)信息: " << endl; tree->print(); cout << endl; }}cout << "== 前序遍歷: "; tree->preOrder();cout << "\n== 中序遍歷: "; tree->inOrder();cout << "\n== 后序遍歷: "; tree->postOrder(); cout << endl;cout << "== 最小值: " << tree->minimum() << endl; cout << "== 最大值: " << tree->maximum() << endl; cout << "== 樹的詳細(xì)信息: " << endl; tree->print(); cout << "開始修改顏色分布" << endl; //黑色是1，紅色是零 tree->mRoot->right->left->color = BLACK;// 修改105的顏色 tree->mRoot->right->left->left->color = RED;// 修改70的顏色 tree->mRoot->right->left->left->left->color = BLACK;// 修改50的顏色 tree->mRoot->right->left->left->right->color = BLACK;// 修改85的顏色 tree->mRoot->right->right->right->color = BLACK;//修改700的顏色 tree->mRoot->right->right->left->color = BLACK;//修改500的顏色 tree->mRoot->right->color = RED;//修改400的顏色tree->insert(1);//驗證修改顏色分布后的樹是否是紅黑樹 tree->remove(1);//驗證修改顏色分布后的樹是否是紅黑樹tree->remove(10);// 銷毀紅黑樹 tree->destroy();cout << "代碼運(yùn)行結(jié)束"; cin.get(); cin.get(); return 0; }使用的頭文件來自連接 http://www.tuicool.com/articles/Freyya
代碼如下： /** * C++ 語言: 紅黑樹 * * @author skywang * @date 2013/11/07 */#ifndef _RED_BLACK_TREE_HPP_ #define _RED_BLACK_TREE_HPP_ #include <iomanip> #include <iostream> using namespace std;enum RBTColor { RED, BLACK };template <class T> class RBTNode { public:RBTColor color; // 顏色T key; // 關(guān)鍵字(鍵值)RBTNode *left; // 左孩子RBTNode *right; // 右孩子RBTNode *parent; // 父結(jié)點(diǎn)RBTNode(T value, RBTColor c, RBTNode *p, RBTNode *l, RBTNode *r) :key(value), color(c), parent(), left(l), right(r) {} };template <class T> class RBTree {public:RBTNode<T> *mRoot; // 根結(jié)點(diǎn)RBTree();~RBTree();// 前序遍歷"紅黑樹"void preOrder();// 中序遍歷"紅黑樹"void inOrder();// 后序遍歷"紅黑樹"void postOrder();// (遞歸實現(xiàn))查找"紅黑樹"中鍵值為key的節(jié)點(diǎn)RBTNode<T>* search(T key);// (非遞歸實現(xiàn))查找"紅黑樹"中鍵值為key的節(jié)點(diǎn)RBTNode<T>* iterativeSearch(T key);// 查找最小結(jié)點(diǎn)：返回最小結(jié)點(diǎn)的鍵值。T minimum();// 查找最大結(jié)點(diǎn)：返回最大結(jié)點(diǎn)的鍵值。T maximum();// 找結(jié)點(diǎn)(x)的后繼結(jié)點(diǎn)。即，查找"紅黑樹中數(shù)據(jù)值大于該結(jié)點(diǎn)"的"最小結(jié)點(diǎn)"。RBTNode<T>* successor(RBTNode<T> *x);// 找結(jié)點(diǎn)(x)的前驅(qū)結(jié)點(diǎn)。即，查找"紅黑樹中數(shù)據(jù)值小于該結(jié)點(diǎn)"的"最大結(jié)點(diǎn)"。RBTNode<T>* predecessor(RBTNode<T> *x);// 將結(jié)點(diǎn)(key為節(jié)點(diǎn)鍵值)插入到紅黑樹中void insert(T key);// 刪除結(jié)點(diǎn)(key為節(jié)點(diǎn)鍵值)void remove(T key);// 銷毀紅黑樹void destroy();// 打印紅黑樹void print(); private:// 前序遍歷"紅黑樹"void preOrder(RBTNode<T>* tree) const;// 中序遍歷"紅黑樹"void inOrder(RBTNode<T>* tree) const;// 后序遍歷"紅黑樹"void postOrder(RBTNode<T>* tree) const;// (遞歸實現(xiàn))查找"紅黑樹x"中鍵值為key的節(jié)點(diǎn)RBTNode<T>* search(RBTNode<T>* x, T key) const;// (非遞歸實現(xiàn))查找"紅黑樹x"中鍵值為key的節(jié)點(diǎn)RBTNode<T>* iterativeSearch(RBTNode<T>* x, T key) const;// 查找最小結(jié)點(diǎn)：返回tree為根結(jié)點(diǎn)的紅黑樹的最小結(jié)點(diǎn)。RBTNode<T>* minimum(RBTNode<T>* tree);// 查找最大結(jié)點(diǎn)：返回tree為根結(jié)點(diǎn)的紅黑樹的最大結(jié)點(diǎn)。RBTNode<T>* maximum(RBTNode<T>* tree);// 左旋void leftRotate(RBTNode<T>* &root, RBTNode<T>* x);// 右旋void rightRotate(RBTNode<T>* &root, RBTNode<T>* y);// 插入函數(shù)void insert(RBTNode<T>* &root, RBTNode<T>* node);// 插入修正函數(shù)void insertFixUp(RBTNode<T>* &root, RBTNode<T>* node);// 刪除函數(shù)void remove(RBTNode<T>* &root, RBTNode<T> *node);// 刪除修正函數(shù)void removeFixUp(RBTNode<T>* &root, RBTNode<T> *node, RBTNode<T> *parent);// 銷毀紅黑樹void destroy(RBTNode<T>* &tree);// 打印紅黑樹void print(RBTNode<T>* tree, T key, int direction);#define rb_parent(r) ((r)->parent) #define rb_color(r) ((r)->color) #define rb_is_red(r) ((r)->color==RED) #define rb_is_black(r) ((r)->color==BLACK) #define rb_set_black(r) do { (r)->color = BLACK; } while (0) #define rb_set_red(r) do { (r)->color = RED; } while (0) #define rb_set_parent(r,p) do { (r)->parent = (p); } while (0) #define rb_set_color(r,c) do { (r)->color = (c); } while (0) };/* * 構(gòu)造函數(shù) */ template <class T> RBTree<T>::RBTree() :mRoot(NULL) {mRoot = NULL; }/* * 析構(gòu)函數(shù) */ template <class T> RBTree<T>::~RBTree() {destroy(); }/* * 前序遍歷"紅黑樹" */ template <class T> void RBTree<T>::preOrder(RBTNode<T>* tree) const {if (tree != NULL){cout << tree->key << " ";preOrder(tree->left);preOrder(tree->right);} }template <class T> void RBTree<T>::preOrder() {preOrder(mRoot); }/* * 中序遍歷"紅黑樹" */ template <class T> void RBTree<T>::inOrder(RBTNode<T>* tree) const {if (tree != NULL){inOrder(tree->left);cout << tree->key << " ";inOrder(tree->right);} }template <class T> void RBTree<T>::inOrder() {inOrder(mRoot); }/* * 后序遍歷"紅黑樹" */ template <class T> void RBTree<T>::postOrder(RBTNode<T>* tree) const {if (tree != NULL){postOrder(tree->left);postOrder(tree->right);cout << tree->key << " ";} }template <class T> void RBTree<T>::postOrder() {postOrder(mRoot); }/* * (遞歸實現(xiàn))查找"紅黑樹x"中鍵值為key的節(jié)點(diǎn) */ template <class T> RBTNode<T>* RBTree<T>::search(RBTNode<T>* x, T key) const {if (x == NULL || x->key == key)return x;if (key < x->key)return search(x->left, key);elsereturn search(x->right, key); }template <class T> RBTNode<T>* RBTree<T>::search(T key) {search(mRoot, key); }/* * (非遞歸實現(xiàn))查找"紅黑樹x"中鍵值為key的節(jié)點(diǎn) */ template <class T> RBTNode<T>* RBTree<T>::iterativeSearch(RBTNode<T>* x, T key) const {while ((x != NULL) && (x->key != key)){if (key < x->key)x = x->left;elsex = x->right;}return x; }template <class T> RBTNode<T>* RBTree<T>::iterativeSearch(T key) {iterativeSearch(mRoot, key); }/* * 查找最小結(jié)點(diǎn)：返回tree為根結(jié)點(diǎn)的紅黑樹的最小結(jié)點(diǎn)。 */ template <class T> RBTNode<T>* RBTree<T>::minimum(RBTNode<T>* tree) {if (tree == NULL)return NULL;while (tree->left != NULL)tree = tree->left;return tree; }template <class T> T RBTree<T>::minimum() {RBTNode<T> *p = minimum(mRoot);if (p != NULL)return p->key;return (T)NULL; }/* * 查找最大結(jié)點(diǎn)：返回tree為根結(jié)點(diǎn)的紅黑樹的最大結(jié)點(diǎn)。 */ template <class T> RBTNode<T>* RBTree<T>::maximum(RBTNode<T>* tree) {if (tree == NULL)return NULL;while (tree->right != NULL)tree = tree->right;return tree; }template <class T> T RBTree<T>::maximum() {RBTNode<T> *p = maximum(mRoot);if (p != NULL)return p->key;return (T)NULL; }/* * 找結(jié)點(diǎn)(x)的后繼結(jié)點(diǎn)。即，查找"紅黑樹中數(shù)據(jù)值大于該結(jié)點(diǎn)"的"最小結(jié)點(diǎn)"。 */ template <class T> RBTNode<T>* RBTree<T>::successor(RBTNode<T> *x) {// 如果x存在右孩子，則"x的后繼結(jié)點(diǎn)"為 "以其右孩子為根的子樹的最小結(jié)點(diǎn)"。if (x->right != NULL)return minimum(x->right);//返回右子樹中的最小值// 如果x沒有右孩子。則x有以下兩種可能：// (01) x是"一個左孩子"，則"x的后繼結(jié)點(diǎn)"為 "它的父結(jié)點(diǎn)"。// (02) x是"一個右孩子"，則查找"x的最低的父結(jié)點(diǎn)，并且該父結(jié)點(diǎn)要具有左孩子"，找到的這個"最低的父結(jié)點(diǎn)"就是"x的后繼結(jié)點(diǎn)"。RBTNode<T>* y = x->parent;while ((y != NULL) && (x == y->right)){x = y;y = y->parent;} return y; }/* * 找結(jié)點(diǎn)(x)的前驅(qū)結(jié)點(diǎn)。即，查找"紅黑樹中數(shù)據(jù)值小于該結(jié)點(diǎn)"的"最大結(jié)點(diǎn)"。 */ template <class T> RBTNode<T>* RBTree<T>::predecessor(RBTNode<T> *x) {// 如果x存在左孩子，則"x的前驅(qū)結(jié)點(diǎn)"為 "以其左孩子為根的子樹的最大結(jié)點(diǎn)"。if (x->left != NULL)return maximum(x->left);// 如果x沒有左孩子。則x有以下兩種可能：// (01) x是"一個右孩子"，則"x的前驅(qū)結(jié)點(diǎn)"為 "它的父結(jié)點(diǎn)"。// (01) x是"一個左孩子"，則查找"x的最低的父結(jié)點(diǎn)，并且該父結(jié)點(diǎn)要具有右孩子"，找到的這個"最低的父結(jié)點(diǎn)"就是"x的前驅(qū)結(jié)點(diǎn)"。RBTNode<T>* y = x->parent;while ((y != NULL) && (x == y->left)){x = y;y = y->parent;}return y; }/* * 對紅黑樹的節(jié)點(diǎn)(x)進(jìn)行左旋轉(zhuǎn) * * 左旋示意圖(對節(jié)點(diǎn)x進(jìn)行左旋)： * px px * / / * x y * / \ --(左旋)--> / \ # * lx y x ry * / \ / \ * ly ry lx ly * * */ template <class T> void RBTree<T>::leftRotate(RBTNode<T>* &root, RBTNode<T>* x) {cout << "左旋轉(zhuǎn)" << endl;// 設(shè)置x的右孩子為yRBTNode<T> *y = x->right;// 將 “y的左孩子” 設(shè)為 “x的右孩子”；// 如果y的左孩子非空，將 “x” 設(shè)為 “y的左孩子的父親”x->right = y->left;if (y->left != NULL)y->left->parent = x;// 將 “x的父親” 設(shè)為 “y的父親”y->parent = x->parent;if (x->parent == NULL){root = y; // 如果 “x的父親” 是空節(jié)點(diǎn)，則將y設(shè)為根節(jié)點(diǎn)}else{if (x->parent->left == x)x->parent->left = y; // 如果 x是它父節(jié)點(diǎn)的左孩子，則將y設(shè)為“x的父節(jié)點(diǎn)的左孩子”elsex->parent->right = y; // 如果 x是它父節(jié)點(diǎn)的左孩子，則將y設(shè)為“x的父節(jié)點(diǎn)的左孩子”}// 將 “x” 設(shè)為 “y的左孩子”y->left = x;// 將 “x的父節(jié)點(diǎn)” 設(shè)為 “y”x->parent = y; }/* * 對紅黑樹的節(jié)點(diǎn)(y)進(jìn)行右旋轉(zhuǎn) * * 右旋示意圖(對節(jié)點(diǎn)y進(jìn)行左旋)： * py py * / / * y x * / \ --(右旋)--> / \ # * x ry lx y * / \ / \ # * lx rx rx ry * */ template <class T> void RBTree<T>::rightRotate(RBTNode<T>* &root, RBTNode<T>* y) {cout << "右旋轉(zhuǎn)" << endl;// 設(shè)置x是當(dāng)前節(jié)點(diǎn)的左孩子。RBTNode<T> *x = y->left;// 將 “x的右孩子” 設(shè)為 “y的左孩子”；// 如果"x的右孩子"不為空的話，將 “y” 設(shè)為 “x的右孩子的父親”y->left = x->right;if (x->right != NULL)x->right->parent = y;// 將 “y的父親” 設(shè)為 “x的父親”x->parent = y->parent;if (y->parent == NULL){root = x; // 如果 “y的父親” 是空節(jié)點(diǎn)，則將x設(shè)為根節(jié)點(diǎn)}else{if (y == y->parent->right)y->parent->right = x; // 如果 y是它父節(jié)點(diǎn)的右孩子，則將x設(shè)為“y的父節(jié)點(diǎn)的右孩子”elsey->parent->left = x; // (y是它父節(jié)點(diǎn)的左孩子) 將x設(shè)為“x的父節(jié)點(diǎn)的左孩子”}// 將 “y” 設(shè)為 “x的右孩子”x->right = y;// 將 “y的父節(jié)點(diǎn)” 設(shè)為 “x”y->parent = x; }/* * 紅黑樹插入修正函數(shù) * * 在向紅黑樹中插入節(jié)點(diǎn)之后(失去平衡)，再調(diào)用該函數(shù)； * 目的是將它重新塑造成一顆紅黑樹。 * * 參數(shù)說明： * root 紅黑樹的根 * node 插入的結(jié)點(diǎn) // 對應(yīng)《算法導(dǎo)論》中的z */ template <class T> void RBTree<T>::insertFixUp(RBTNode<T>* &root, RBTNode<T>* node) {RBTNode<T> *parent, *gparent;// 若“父節(jié)點(diǎn)存在，并且父節(jié)點(diǎn)的顏色是紅色”//這里注意，下面的代碼中之所以沒有給出gparent的顏色的判斷，是因為//紅色節(jié)點(diǎn)的兩個孩子必定都是黑色，那么必有逆否命題，如果不都是黑色，孩子的父親節(jié)點(diǎn)肯定不是紅色while ((parent = rb_parent(node)) && rb_is_red(parent)){gparent = rb_parent(parent);//若“父節(jié)點(diǎn)”是“祖父節(jié)點(diǎn)的左孩子”if (parent == gparent->left){// Case 1條件：叔叔節(jié)點(diǎn)是紅色{RBTNode<T> *uncle = gparent->right;if (uncle && rb_is_red(uncle)){rb_set_black(uncle);rb_set_black(parent);rb_set_red(gparent);node = gparent;cout << "End of Execution for Case1" << endl;continue;}}// Case 2條件：叔叔是黑色，且當(dāng)前節(jié)點(diǎn)是右孩子if (parent->right == node){RBTNode<T> *tmp;leftRotate(root, parent);tmp = parent;parent = node;node = tmp;cout << "End of Execution for Case2" << endl;}// Case 3條件：叔叔是黑色，且當(dāng)前節(jié)點(diǎn)是左孩子。rb_set_black(parent);rb_set_red(gparent);rightRotate(root, gparent);cout << "End of Execution for Case3" << endl;}else//若“z的父節(jié)點(diǎn)”是“z的祖父節(jié)點(diǎn)的右孩子”{// Case 1條件：叔叔節(jié)點(diǎn)是紅色{RBTNode<T> *uncle = gparent->left;if (uncle && rb_is_red(uncle)){rb_set_black(uncle);rb_set_black(parent);rb_set_red(gparent);node = gparent;continue;}}// Case 2條件：叔叔是黑色，且當(dāng)前節(jié)點(diǎn)是左孩子if (parent->left == node){RBTNode<T> *tmp;rightRotate(root, parent);tmp = parent;parent = node;node = tmp;}// Case 3條件：叔叔是黑色，且當(dāng)前節(jié)點(diǎn)是右孩子。rb_set_black(parent);rb_set_red(gparent);leftRotate(root, gparent);cout << "End of Execution for Case3" << endl;}}// 將根節(jié)點(diǎn)設(shè)為黑色rb_set_black(root); }/* * 將結(jié)點(diǎn)插入到紅黑樹中 * * 參數(shù)說明： * root 紅黑樹的根結(jié)點(diǎn) * node 插入的結(jié)點(diǎn) // 對應(yīng)《算法導(dǎo)論》中的node */ template <class T> void RBTree<T>::insert(RBTNode<T>* &root, RBTNode<T>* node) {RBTNode<T> *y = NULL;RBTNode<T> *x = root;// 1. 將紅黑樹當(dāng)作一顆二叉查找樹，將節(jié)點(diǎn)添加到二叉查找樹中。while (x != NULL)//注意插入的時候，肯定是通過替換當(dāng)前樹的某個節(jié)點(diǎn)的空子節(jié)點(diǎn)來實現(xiàn)的。{y = x;if (node->key < x->key)x = x->left;elsex = x->right;}node->parent = y;//node替換了y的空子節(jié)點(diǎn)，由于紅黑樹的是搜索樹，所以要插入的節(jié)點(diǎn)的值比y小時，成為y的做節(jié)點(diǎn)，否則成為y的右節(jié)點(diǎn)if (y != NULL){if (node->key < y->key)y->left = node;elsey->right = node;}elseroot = node;// 2. 設(shè)置節(jié)點(diǎn)的顏色為紅色node->color = RED;// 3. 將它重新修正為一顆二叉查找樹insertFixUp(root, node); }/* * 將結(jié)點(diǎn)(key為節(jié)點(diǎn)鍵值)插入到紅黑樹中 * * 參數(shù)說明： * tree 紅黑樹的根結(jié)點(diǎn) * key 插入結(jié)點(diǎn)的鍵值 */ template <class T> void RBTree<T>::insert(T key) {RBTNode<T> *z = NULL;// 如果新建結(jié)點(diǎn)失敗，則返回。if ((z = new RBTNode<T>(key, BLACK, NULL, NULL, NULL)) == NULL)return;insert(mRoot, z); }/* * 紅黑樹刪除修正函數(shù) * * 在從紅黑樹中刪除插入節(jié)點(diǎn)之后(紅黑樹失去平衡)，再調(diào)用該函數(shù)； * 目的是將它重新塑造成一顆紅黑樹。 * * 參數(shù)說明： * root 紅黑樹的根 * node 待修正的節(jié)點(diǎn) */ template <class T> void RBTree<T>::removeFixUp(RBTNode<T>* &root, RBTNode<T> *node, RBTNode<T> *parent) {RBTNode<T> *other;while ((!node || rb_is_black(node)) && node != root){cout << "進(jìn)入removeFixup" << endl;if (parent->left == node){cout << "進(jìn)入此處1" << endl;other = parent->right;//在這里對other進(jìn)行了修正，所以進(jìn)入新的case時，other指針?biāo)概c之前的不同if (rb_is_red(other)){// Case 1: x的兄弟w是紅色的 cout << "進(jìn)入case1 ☆☆☆" << endl;rb_set_black(other);rb_set_red(parent);cout << "root->key=" << root->key << endl;cout << "parent->key=" << parent->key << endl;cout << "other->key=" << other->key << endl;cout << "left-rotate of case 1 in the corner" << endl;leftRotate(root, parent);other = parent->right;cout << other->key << endl;cout << root->key << endl;cout << node->key << endl;cout << "End of Execution for Case1 ☆☆☆" << endl;cout << "-----------------------------------------" << endl;}if ((!other->left || rb_is_black(other->left)) &&(!other->right || rb_is_black(other->right))){// Case 2: x的兄弟w是黑色，且w的倆個孩子也都是黑色的cout << "進(jìn)入case2 ☆☆☆" << endl;rb_set_red(other);node = parent;parent = rb_parent(node);cout << "node->key=" << node->key<<endl;cout << "parent->key=" << parent->key << endl;cout << "other->key=" << other->key << endl;cout << "other->color=" << other->color << endl;cout << "End of Execution for Case2 ☆☆☆" << endl;}else{if (!other->right || rb_is_black(other->right)){cout << "進(jìn)入case3 ☆☆☆" << endl;// Case 3: x的兄弟w是黑色的，并且w的左孩子是紅色，右孩子為黑色。 cout << "other->left->key=" << other->left->key<< endl;cout << "root->key=" <<root->key << endl;cout << "node->key=" << node->key << endl;cout << "parent->key=" << parent->key << endl;rb_set_black(other->left);rb_set_red(other);rightRotate(root, other);other = parent->right;cout << "other->left->key=" << other->left->key << endl;cout << "root->key=" << root->key << endl;cout << "node->key=" << node->key << endl;cout << "parent->key=" << parent->key << endl;cout << "End of Execution for Case3 ☆☆☆" << endl;}// Case 4: x的兄弟w是黑色的；并且w的右孩子是紅色的，左孩子任意顏色。cout << "進(jìn)入case4 ☆☆☆" << endl;cout << "other->key=" << other->key << endl;cout << "root->key=" << root->key << endl;cout << "node->key=" << node->key << endl;cout << "parent->key=" << parent->key << endl;rb_set_color(other, rb_color(parent));rb_set_black(parent);rb_set_black(other->right);leftRotate(root, parent);cout << "other->key=" << other->key << endl;cout << "root->key=" << root->key << endl;cout << "node->key=" << node->key << endl;cout << "parent->key=" << parent->key << endl;node = root;cout << "End of Execution for Case4 ☆☆☆" << endl;break;}}else{other = parent->left;if (rb_is_red(other)){cout << "Enter into case1 ☆☆☆" << endl;// Case 1: x的兄弟w是紅色的 rb_set_black(other);rb_set_red(parent);rightRotate(root, parent);other = parent->left;cout << "End of Execution for Case1 ☆☆☆" << endl;}if ((!other->left || rb_is_black(other->left)) &&(!other->right || rb_is_black(other->right))){cout << "Enter into case2 ☆☆☆" << endl;// Case 2: x的兄弟w是黑色，且w的倆個孩子也都是黑色的 rb_set_red(other);node = parent;parent = rb_parent(node);cout << "End of Execution for Case2 ☆☆☆" << endl;}else{if (!other->left || rb_is_black(other->left)){cout << "Enter into case3 ☆☆☆" << endl;// Case 3: x的兄弟w是黑色的，并且w的左孩子是紅色，右孩子為黑色。 rb_set_black(other->right);rb_set_red(other);leftRotate(root, other);other = parent->left;cout << "End of Execution for Case3 ☆☆☆" << endl;}// Case 4: x的兄弟w是黑色的；并且w的右孩子是紅色的，左孩子任意顏色。cout << "Enter into case4 ☆☆☆" << endl;rb_set_color(other, rb_color(parent));rb_set_black(parent);rb_set_black(other->left);rightRotate(root, parent);node = root;cout << "End of Execution for Case4 ☆☆☆" << endl;break;}}}if (node)rb_set_black(node); }/* * 刪除結(jié)點(diǎn)(node)，并返回被刪除的結(jié)點(diǎn) * * 參數(shù)說明： * root 紅黑樹的根結(jié)點(diǎn) * node 刪除的結(jié)點(diǎn) */ template <class T> void RBTree<T>::remove(RBTNode<T>* &root, RBTNode<T> *node) {cout << "進(jìn)入此處3" << endl;RBTNode<T> *child, *parent;RBTColor color;// 被刪除節(jié)點(diǎn)的"左右孩子都不為空"的情況。if ((node->left != NULL) && (node->right != NULL)){cout << "進(jìn)入if ((node->left != NULL) && (node->right != NULL))" << endl;// 被刪節(jié)點(diǎn)的后繼節(jié)點(diǎn)。(稱為"取代節(jié)點(diǎn)")// 用它來取代"被刪節(jié)點(diǎn)"的位置，然后再將"被刪節(jié)點(diǎn)"去掉。RBTNode<T> *replace = node;// 接下來讓replace獲取后繼節(jié)點(diǎn)replace = replace->right;while (replace->left != NULL)replace = replace->left;cout << "replace->key = " << replace->key << endl;// 如果將要被刪除的"node節(jié)點(diǎn)"不是根節(jié)點(diǎn)(只有根節(jié)點(diǎn)不存在父節(jié)點(diǎn))if (rb_parent(node)){if (rb_parent(node)->left == node)//對應(yīng)算法導(dǎo)論P(yáng)183中的：elseif u==u.p.leftrb_parent(node)->left = replace;elserb_parent(node)->right = replace;}else// "node節(jié)點(diǎn)"是根節(jié)點(diǎn)，更新根節(jié)點(diǎn)。root = replace;// child是"取代節(jié)點(diǎn)"的右孩子，也是需要"調(diào)整的節(jié)點(diǎn)"。// "取代節(jié)點(diǎn)"肯定不存在左孩子！因為它是一個后繼節(jié)點(diǎn)。child = replace->right;parent = rb_parent(replace);// 保存"取代節(jié)點(diǎn)"的顏色color = rb_color(replace);cout << "parent->key = "<<parent->key << endl;cout << "node->key = " << node->key << endl;if(child!=NULL)cout << "child->key = " << child->key << endl;cout << "replace->key = " << replace->key << endl;cout << "###############" << endl;// "被刪除節(jié)點(diǎn)"是"它的后繼節(jié)點(diǎn)的父節(jié)點(diǎn)"if (parent == node){parent = replace;}else{// child不為空if (child)rb_set_parent(child, parent);parent->left = child;replace->right = node->right;rb_set_parent(node->right, replace);}cout << "進(jìn)入Fixup前" << endl;cout << "parent->key = " << parent->key << endl;cout << "node->key = " << node->key << endl;if (child != NULL)cout << "child->key = " << child->key << endl;cout << "replace->key = " << replace->key << endl;replace->parent = node->parent;replace->color = node->color;replace->left = node->left;//讓后繼節(jié)點(diǎn)與被刪節(jié)點(diǎn)的左子樹建立連接node->left->parent = replace;//這些代碼的作用是讓后繼節(jié)點(diǎn)代替被刪除的節(jié)點(diǎn)if (color == BLACK)removeFixUp(root, child, parent);delete node;return;}if (node->left != NULL)child = node->left;elsechild = node->right;//-----------以上是對被刪除節(jié)點(diǎn)的三種情況的判斷--------------------------------------------------parent = node->parent;// 保存"取代節(jié)點(diǎn)"的顏色color = node->color;if (child)child->parent = parent;// "node節(jié)點(diǎn)"不是根節(jié)點(diǎn)if (parent){if (parent->left == node)parent->left = child;elseparent->right = child;}elseroot = child;if (color == BLACK){cout << "即將進(jìn)入Fixup" << endl;if(child!=NULL)cout << "child->key=" << child->key << endl;if (parent != NULL)cout << "parent->key=" << parent->key << endl;removeFixUp(root, child, parent);cout << "進(jìn)入此處5" << endl;}cout << "node->key=" << node->key << endl;delete node; }/* * 刪除紅黑樹中鍵值為key的節(jié)點(diǎn) * * 參數(shù)說明： * tree 紅黑樹的根結(jié)點(diǎn) */ template <class T> void RBTree<T>::remove(T key) {RBTNode<T> *node;// 查找key對應(yīng)的節(jié)點(diǎn)(node)，找到的話就刪除該節(jié)點(diǎn)if ((node = search(mRoot, key)) != NULL)remove(mRoot, node); }/* * 銷毀紅黑樹 */ template <class T> void RBTree<T>::destroy(RBTNode<T>* &tree) {if (tree == NULL)return;if (tree->left != NULL)return destroy(tree->left);if (tree->right != NULL)return destroy(tree->right);delete tree;tree = NULL; }template <class T> void RBTree<T>::destroy() {destroy(mRoot); }/* * 打印"二叉查找樹" * * key -- 節(jié)點(diǎn)的鍵值 * direction -- 0，表示該節(jié)點(diǎn)是根節(jié)點(diǎn); * -1，表示該節(jié)點(diǎn)是它的父結(jié)點(diǎn)的左孩子; * 1，表示該節(jié)點(diǎn)是它的父結(jié)點(diǎn)的右孩子。 */ template <class T> void RBTree<T>::print(RBTNode<T>* tree, T key, int direction) {if (tree != NULL){if (direction == 0) // tree是根節(jié)點(diǎn)cout << setw(2) << tree->key << "(B) is root" << endl;else // tree是分支節(jié)點(diǎn)cout << setw(2) << tree->key << (rb_is_red(tree) ? "(R)" : "(B)") << " is " << setw(2) << key << "'s " << setw(12) << (direction == 1 ? "right child" : "left child") << endl;print(tree->left, tree->key, -1);print(tree->right, tree->key, 1);} }template <class T> void RBTree<T>::print()//RBTree<T>的意思是，類中存在模板，T是對模板的提取，表示該類對各種類型的數(shù)據(jù)通用 {if (mRoot != NULL)print(mRoot, mRoot->key, 0); }#endif

總結(jié)

以上是生活随笔為你收集整理的红黑树 删除某节点后 旋转3次 举例的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。