/***************************************************************************** * 紅黑色： * 或是1顆空樹，或是1顆2叉樹，滿足以下性質(zhì) *1.節(jié)點(diǎn)非紅即黑。 *2.根節(jié)點(diǎn)是黑色。 *3.所有NULL結(jié)點(diǎn)稱為葉子節(jié)點(diǎn)，且認(rèn)為色彩為黑。 *4.所有紅節(jié)點(diǎn)的子節(jié)點(diǎn)都為黑色。 *5.從任1節(jié)點(diǎn)到其葉子節(jié)點(diǎn)的所有路徑上都包括相同數(shù)目的黑節(jié)點(diǎn)。 * *紅黑樹具有較好的自平衡性，性能優(yōu)于BST，但是低于AVL，在linux中用于內(nèi)存管理 * *因此紅黑色在插入節(jié)點(diǎn)必定是紅節(jié)點(diǎn)，由于黑節(jié)點(diǎn)會(huì)破壞性質(zhì)5，但是會(huì)出現(xiàn)以下問(wèn)題 *****************************************************************************/ #ifndef REDBLACK_H_ #define REDBLACK_H_ #include <iostream> #define BLACK 1 #define RED 0 using namespace std; /**************每一個(gè)節(jié)點(diǎn)的信息***********************/ class Node { public: int value;/******節(jié)點(diǎn)寄存的值******/ bool color;/***節(jié)點(diǎn)色彩****/ Node *leftTree, *rightTree, *parent;/*******左右子樹，父節(jié)點(diǎn)**********/ Node(void):color(RED),leftTree(NULL),rightTree(NULL),parent(NULL),value(0) {} /**********獲得祖父節(jié)點(diǎn)************/ Node* grandparent(void) { return parent==NULL?NULL:parent->parent; } /***********獲得叔節(jié)點(diǎn)***********/ Node* uncle(void) { if (grandparent() == NULL) { return NULL; } if (parent == grandparent()->rightTree) return grandparent()->leftTree; else return grandparent()->rightTree; } /******獲得兄弟節(jié)點(diǎn)*********/ Node* sibling(void) { return parent->leftTree==this?parent->rightTree:parent->leftTree; } }; /******************紅黑色類*********************/ class RedBlackTree { private: void rotate_right(Node *p);/*******右旋********/ void rotate_left(Node *p);/*******左旋********/ void inorder(Node *p);/********先序遍歷***********/ string outputColor(bool color);/********輸出色彩**********/ Node* getSmallestChild(Node *p);/**********獲得最小子樹***********/ bool delete_child(Node *p, int data);/*********刪除子樹************/ void delete_one_child(Node *p);/*********刪除1個(gè)孩子************/ void delete_case(Node *p);/*********刪除情況************/ void insert(Node *p, int data);/********插入*********/ void insert_case(Node *p);/********插入情況***********/ void DeleteTree(Node *p);/********刪除樹***********/ bool find_data(Node* p,int data);/*********查找節(jié)點(diǎn)************/ public: RedBlackTree(void);/********構(gòu)造接口***********/ ~RedBlackTree();/********燒毀接口***********/ void InOrderTraverse();/********遍歷接口***********/ void Insert(int x);/********插入接口***********/ bool Delete(int data);/********刪除接口***********/ bool Find(int data);/********查找接口***********/ private: Node *root, *NIL; }; //******************************************************************* // Method: rotate_right // FullName: RedBlackTree::rotate_right // Access: private // Returns: void // Qualifier: 右旋轉(zhuǎn) // Parameter: Node * p //******************************************************************* //*******************GP********************GP************************ //******************/********************/************************* //****************FA****x****************P****X********************** //***************/******--->***********/*************************** //*************P*****U*****************L**FA************************* //************/*************************Y************************** //***********L***Y***************************U*********************** //******************************************************************* void RedBlackTree::rotate_right(Node *p) { Node *gp = p->grandparent(); Node *fa = p->parent; Node *y = p->rightTree; fa->leftTree = y; if (y != NIL) y->parent = fa; p->rightTree = fa; fa->parent = p; if (root == fa) root = p; p->parent = gp; if (gp != NULL)/******判讀父節(jié)點(diǎn)與祖父節(jié)點(diǎn)的關(guān)系，從而修復(fù)關(guān)系********/ { if (gp->leftTree == fa) gp->leftTree = p; else gp->rightTree = p; } } //******************************************************************* // Method: rotate_left // FullName: RedBlackTree::rotate_left // Access: private // Returns: void // Qualifier: 左旋 // Parameter: Node * p //******************************************************************* //******************************************************************* //*******************GP********************GP************************ //******************/********************/************************* //****************FA****x****************P****X********************** //***************/******--->***********/*************************** //**************X****P*****************FA**R************************* //******************/****************/***************************** //*****************Y***R*************X****Y************************** //******************************************************************* void RedBlackTree::rotate_left(Node *p) { if (p->parent == NULL) { root = p; return; } Node *gp = p->grandparent(); Node *fa = p->parent; Node *y = p->leftTree; fa->rightTree = y; if (y != NIL) y->parent = fa; p->leftTree = fa; fa->parent = p; if (root == fa) root = p; p->parent = gp; if (gp != NULL)/******判讀父節(jié)點(diǎn)與祖父節(jié)點(diǎn)的關(guān)系，從而修復(fù)關(guān)系********/ { if (gp->leftTree == fa) gp->leftTree = p; else gp->rightTree = p; } } //************************************ // Method: inorder // FullName: RedBlackTree::inorder // Access: private // Returns: void // Qualifier: 中序遍歷節(jié)點(diǎn) // Parameter: Node * p //************************************ void RedBlackTree::inorder(Node *p) { if (p == NIL) return; if (p->leftTree) inorder(p->leftTree); cout << p->value << " "; if (p->rightTree) inorder(p->rightTree); } //************************************ // Method: outputColor // FullName: RedBlackTree::outputColor // Access: private // Returns: std::string // Qualifier: 輸出色彩 // Parameter: bool color //************************************ string RedBlackTree::outputColor(bool color) { return color ? "BLACK" : "RED"; } //************************************ // Method: getSmallestChild // FullName: RedBlackTree::getSmallestChild // Access: private // Returns: Node* // Qualifier: 獲得最小孩子 // Parameter: Node * p //************************************ Node* RedBlackTree::getSmallestChild(Node* p) { if (p->leftTree == NIL) return p; return getSmallestChild(p->leftTree); } //************************************ // Method: delete_child // FullName: RedBlackTree::delete_child // Access: private // Returns: bool // Qualifier: 刪除孩子 // Parameter: Node * p // Parameter: int data //************************************ bool RedBlackTree::delete_child(Node *p, int data) { if (p->value > data)/*****在左側(cè)*******/ { if (p->leftTree == NIL)/*****沒(méi)有找到元素*******/ { return false; } return delete_child(p->leftTree, data); } else if (p->value < data)/*****在右側(cè)*******/ { if (p->rightTree == NIL) { return false; } return delete_child(p->rightTree, data); } else if (p->value == data)/*****找到*******/ { if (p->rightTree == NIL) {/******如果節(jié)點(diǎn)右子樹空了，這樣最多只有1個(gè)孩子，否則需要替換節(jié)點(diǎn)，再進(jìn)入單節(jié)點(diǎn)刪除*******/ delete_one_child(p); return true; } Node *smallest = getSmallestChild(p->rightTree);/*找打后繼節(jié)點(diǎn)，然后交換，后刪除*/ swap(p->value, smallest->value); delete_one_child(smallest); return true; } return false; } //************************************ // Method: delete_one_child // FullName: RedBlackTree::delete_one_child // Access: private // Returns: void // Qualifier: 刪除最多只有1個(gè)孩子的節(jié)點(diǎn) // Parameter: Node * p //************************************ void RedBlackTree::delete_one_child(Node *p) { Node *child = p->leftTree == NIL ? p->rightTree : p->leftTree; if (p->parent == NULL && p->leftTree == NIL && p->rightTree == NIL) {/****只有根節(jié)點(diǎn)*******/ p = NULL; root = p; return; } if (p->parent == NULL)/****根節(jié)點(diǎn)****/ { delete p; child->parent = NULL;/**重置根節(jié)點(diǎn)*/ root = child; root->color = BLACK; return; } if (p->parent->leftTree == p)/**替換掉該節(jié)點(diǎn)**/ { p->parent->leftTree = child; } else { p->parent->rightTree = child; } child->parent = p->parent; if (p->color == BLACK) {/*****如果刪除的節(jié)點(diǎn)是黑節(jié)點(diǎn)，需要調(diào)劑樹，如果是紅節(jié)點(diǎn)，那末子樹也是不沖突的，則直接刪除便可********/ if (child->color == RED)/****子樹是紅節(jié)點(diǎn)的話，則直接退換成黑節(jié)點(diǎn)，并且性質(zhì)沒(méi)有遭到破壞****/ { child->color = BLACK; } else/*******否則需要調(diào)劑性質(zhì)*******/ delete_case(child); } delete p; } //************************************ // Method: delete_case // FullName: RedBlackTree::delete_case // Access: private // Returns: void // Qualifier: 刪除情況 // Parameter: Node * p //************************************ void RedBlackTree::delete_case(Node *p) { if (p->parent == NULL)/***為根節(jié)點(diǎn)，直接染黑色***/ { p->color = BLACK; return; } if (p->sibling()->color == RED)/****情況1：如果兄弟節(jié)點(diǎn)是紅色的話，調(diào)劑色彩后旋轉(zhuǎn)，最后依照2,3,4處理****/ { p->parent->color = RED; p->sibling()->color = BLACK; if (p == p->parent->leftTree) rotate_left(p->sibling()); else rotate_right(p->sibling()); } if (p->parent->color == BLACK && p->sibling()->color == BLACK && p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK) {/****情況2.1：父節(jié)點(diǎn)黑色，兄弟節(jié)點(diǎn)是黑色，而且兄弟有兩個(gè)黑色的子節(jié)點(diǎn)，這樣可以染紅兄弟，然后調(diào)劑父節(jié)點(diǎn)****/ p->sibling()->color = RED; delete_case(p->parent); } else if (p->parent->color == RED && p->sibling()->color == BLACK && p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK) {/****情況2.2：如果兄弟節(jié)點(diǎn)是紅色的話，而且兄弟有兩個(gè)黑色的子節(jié)點(diǎn)，這樣可以染紅兄弟，然后調(diào)劑父節(jié)點(diǎn)****/ p->sibling()->color = RED; p->parent->color = BLACK; } else { if (p->sibling()->color == BLACK) {/****情況3.1：如果兄弟節(jié)點(diǎn)是黑色的話，而且兄弟左孩子紅色，右孩子黑色，交換兄弟節(jié)點(diǎn)和左孩子色彩變成第第4種情況****/ if (p == p->parent->leftTree && p->sibling()->leftTree->color == RED && p->sibling()->rightTree->color == BLACK) { p->sibling()->color = RED; p->sibling()->leftTree->color = BLACK; rotate_right(p->sibling()->leftTree); } else if (p == p->parent->rightTree && p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == RED) {/****情況3.2：如果兄弟節(jié)點(diǎn)是黑色的話，而且兄弟左孩子黑色，右孩子紅色****/ p->sibling()->color = RED; p->sibling()->rightTree->color = BLACK; rotate_left(p->sibling()->rightTree); } } /****情況4：如果兄弟節(jié)點(diǎn)是黑色的話，而且兄弟對(duì)面節(jié)點(diǎn)孩子為紅色****/ p->sibling()->color = p->parent->color; p->parent->color = BLACK; if (p == p->parent->leftTree) {/****情況4.1：節(jié)點(diǎn)為左子樹，那末兄弟右孩子為紅色****/ p->sibling()->rightTree->color = BLACK; rotate_left(p->sibling()); } else {/****情況4.2：節(jié)點(diǎn)為右子樹，那末兄弟左孩子為紅色****/ p->sibling()->leftTree->color = BLACK; rotate_right(p->sibling()); } } } //************************************ // Method: insert // FullName: RedBlackTree::insert // Access: private // Returns: void // Qualifier: 插入數(shù)據(jù) // Parameter: Node * p // Parameter: int data //************************************ void RedBlackTree::insert(Node *p, int data) { if (p->value >= data)/**插入數(shù)據(jù)比data小（含等于）的話，進(jìn)入左側(cè)，否則進(jìn)入右側(cè)**/ { if (p->leftTree != NIL) insert(p->leftTree, data); else { Node *tmp = new Node(); tmp->value = data; tmp->leftTree = tmp->rightTree = NIL; tmp->parent = p; p->leftTree = tmp; insert_case(tmp); } } else { if (p->rightTree != NIL) insert(p->rightTree, data); else { Node *tmp = new Node(); tmp->value = data; tmp->leftTree = tmp->rightTree = NIL; tmp->parent = p; p->rightTree = tmp; insert_case(tmp); } } } //************************************ // Method: insert_case // FullName: RedBlackTree::insert_case // Access: private // Returns: void // Qualifier: 插入情況，1共有5種情況 // Parameter: Node * p //************************************ void RedBlackTree::insert_case(Node *p) { if (p->parent == NULL)/****情形1：直接染黑色*****/ { root = p; p->color = BLACK; return; } if (p->parent->color == RED) { if (p->uncle()->color == RED) {/*情形3：父節(jié)點(diǎn)和叔節(jié)點(diǎn)都是紅色，將祖父，父、叔全換色，最后遞歸處理祖父節(jié)點(diǎn)*/ p->parent->color = p->uncle()->color = BLACK; p->grandparent()->color = RED; insert_case(p->grandparent()); } else/*父節(jié)點(diǎn)和叔節(jié)點(diǎn)都是紅色，叔叔節(jié)點(diǎn)黑色*/ { if (p->parent->rightTree == p && p->grandparent()->leftTree == p->parent) {/**情形4：p是父節(jié)點(diǎn)的右孩子，父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的左孩子**/ /********這類情況先調(diào)劑父節(jié)點(diǎn)，使得其和祖父和父親均在1條線上，注意，這里旋轉(zhuǎn)后p成新的父節(jié)點(diǎn)********/ rotate_left(p); rotate_right(p); p->color = BLACK; p->leftTree->color = p->rightTree->color = RED; } else if (p->parent->leftTree == p && p->grandparent()->rightTree == p->parent) {/**情形5：p是父節(jié)點(diǎn)的左孩子，父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的右孩子**/ /********這類情況先調(diào)劑父節(jié)點(diǎn)，使得其和祖父和父親均在1條線上，注意，這里旋轉(zhuǎn)后p成新的父節(jié)點(diǎn)********/ rotate_right(p); rotate_left(p); p->color = BLACK; p->leftTree->color = p->rightTree->color = RED; } else if (p->parent->leftTree == p && p->grandparent()->leftTree == p->parent) {/**情形5.2：p是父節(jié)點(diǎn)的右孩子，父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的左孩子**/ p->parent->color = BLACK; p->grandparent()->color = RED; rotate_right(p->parent); } else if (p->parent->rightTree == p && p->grandparent()->rightTree == p->parent) {/**情形4.2：p是父節(jié)點(diǎn)的右孩子，父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的左孩子**/ p->parent->color = BLACK; p->grandparent()->color = RED; rotate_left(p->parent); } } } /*******最后斟酌case2：情況，由于父節(jié)點(diǎn)是黑色，所以可以直接退出********/ } //************************************ // Method: DeleteTree // FullName: RedBlackTree::DeleteTree // Access: private // Returns: void // Qualifier: 刪除樹 // Parameter: Node * p //************************************ void RedBlackTree::DeleteTree(Node *p) { if (!p || p == NIL) { return; } DeleteTree(p->leftTree); DeleteTree(p->rightTree); delete p; } //************************************ // Method: find_data // FullName: RedBlackTree::find_data // Access: public // Returns: bool // Qualifier: 查找值 // Parameter: int data //************************************ bool RedBlackTree::find_data(Node* p,int data) { if(p==NULL||p==NIL) return false; if(data>p->value) return find_data(p->rightTree,data); else if(data<p->value) return find_data(p->leftTree,data); return true; } /**************************************接口部份********************************/ //************************************ // Method: RedBlackTree // FullName: RedBlackTree::RedBlackTree // Access: public // Returns: // Qualifier: 初始化 // Parameter: void //************************************ RedBlackTree::RedBlackTree(void) { NIL = new Node(); NIL->color = BLACK; root = NULL; } RedBlackTree::~RedBlackTree(void) { if (root) DeleteTree(root); delete NIL; } //************************************ // Method: inorder // FullName: RedBlackTree::inorder // Access: public // Returns: void // Qualifier: 遍歷節(jié)點(diǎn) // Parameter: void //************************************ void RedBlackTree::InOrderTraverse(void) { if (root == NULL) return; inorder(root); cout << endl; } //************************************ // Method: insert // FullName: RedBlackTree::insert // Access: public // Returns: void // Qualifier: 插入值 // Parameter: int x //************************************ void RedBlackTree::Insert(int x) { if (root == NULL) { root = new Node(); root->color = BLACK; root->leftTree = root->rightTree = NIL; root->value = x; } else { insert(root, x); } } //************************************ // Method: delete_value // FullName: RedBlackTree::delete_value // Access: public // Returns: bool // Qualifier: 刪除值 // Parameter: int data //************************************ bool RedBlackTree::Delete(int data) { return delete_child(root, data); } //************************************ // Method: Find // FullName: RedBlackTree::Find // Access: public // Returns: bool // Qualifier: 查找值 // Parameter: int data //************************************ bool RedBlackTree::Find(int data) { return find_data(root,data); } #endif /*redblaock.h*/