/***************************************************************************** * 紅黑色： * 或是1顆空樹，或是1顆2叉樹，滿足以下性質 *1.節點非紅即黑。 *2.根節點是黑色。 *3.所有NULL結點稱為葉子節點，且認為色彩為黑。 *4.所有紅節點的子節點都為黑色。 *5.從任1節點到其葉子節點的所有路徑上都包括相同數目的黑節點。 * *紅黑樹具有較好的自平衡性，性能優于BST，但是低于AVL，在linux中用于內存管理 * *因此紅黑色在插入節點必定是紅節點，由于黑節點會破壞性質5，但是會出現以下問題 *****************************************************************************/ #ifndef REDBLACK_H_ #define REDBLACK_H_ #include <iostream> #define BLACK 1 #define RED 0 using namespace std; /**************每一個節點的信息***********************/ class Node { public: int value;/******節點寄存的值******/ bool color;/***節點色彩****/ Node *leftTree, *rightTree, *parent;/*******左右子樹，父節點**********/ Node(void):color(RED),leftTree(NULL),rightTree(NULL),parent(NULL),value(0) {} /**********獲得祖父節點************/ Node* grandparent(void) { return parent==NULL?NULL:parent->parent; } /***********獲得叔節點***********/ Node* uncle(void) { if (grandparent() == NULL) { return NULL; } if (parent == grandparent()->rightTree) return grandparent()->leftTree; else return grandparent()->rightTree; } /******獲得兄弟節點*********/ 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個孩子************/ 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);/*********查找節點************/ public: RedBlackTree(void);/********構造接口***********/ ~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: 右旋轉 // 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)/******判讀父節點與祖父節點的關系，從而修復關系********/ { 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)/******判讀父節點與祖父節點的關系，從而修復關系********/ { if (gp->leftTree == fa) gp->leftTree = p; else gp->rightTree = p; } } //************************************ // Method: inorder // FullName: RedBlackTree::inorder // Access: private // Returns: void // Qualifier: 中序遍歷節點 // 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)/*****在左側*******/ { if (p->leftTree == NIL)/*****沒有找到元素*******/ { return false; } return delete_child(p->leftTree, data); } else if (p->value < data)/*****在右側*******/ { if (p->rightTree == NIL) { return false; } return delete_child(p->rightTree, data); } else if (p->value == data)/*****找到*******/ { if (p->rightTree == NIL) {/******如果節點右子樹空了，這樣最多只有1個孩子，否則需要替換節點，再進入單節點刪除*******/ delete_one_child(p); return true; } Node *smallest = getSmallestChild(p->rightTree);/*找打后繼節點，然后交換，后刪除*/ 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個孩子的節點 // 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) {/****只有根節點*******/ p = NULL; root = p; return; } if (p->parent == NULL)/****根節點****/ { delete p; child->parent = NULL;/**重置根節點*/ root = child; root->color = BLACK; return; } if (p->parent->leftTree == p)/**替換掉該節點**/ { p->parent->leftTree = child; } else { p->parent->rightTree = child; } child->parent = p->parent; if (p->color == BLACK) {/*****如果刪除的節點是黑節點，需要調劑樹，如果是紅節點，那末子樹也是不沖突的，則直接刪除便可********/ if (child->color == RED)/****子樹是紅節點的話，則直接退換成黑節點，并且性質沒有遭到破壞****/ { child->color = BLACK; } else/*******否則需要調劑性質*******/ 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)/***為根節點，直接染黑色***/ { p->color = BLACK; return; } if (p->sibling()->color == RED)/****情況1：如果兄弟節點是紅色的話，調劑色彩后旋轉，最后依照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：父節點黑色，兄弟節點是黑色，而且兄弟有兩個黑色的子節點，這樣可以染紅兄弟，然后調劑父節點****/ 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：如果兄弟節點是紅色的話，而且兄弟有兩個黑色的子節點，這樣可以染紅兄弟，然后調劑父節點****/ p->sibling()->color = RED; p->parent->color = BLACK; } else { if (p->sibling()->color == BLACK) {/****情況3.1：如果兄弟節點是黑色的話，而且兄弟左孩子紅色，右孩子黑色，交換兄弟節點和左孩子色彩變成第第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：如果兄弟節點是黑色的話，而且兄弟左孩子黑色，右孩子紅色****/ p->sibling()->color = RED; p->sibling()->rightTree->color = BLACK; rotate_left(p->sibling()->rightTree); } } /****情況4：如果兄弟節點是黑色的話，而且兄弟對面節點孩子為紅色****/ p->sibling()->color = p->parent->color; p->parent->color = BLACK; if (p == p->parent->leftTree) {/****情況4.1：節點為左子樹，那末兄弟右孩子為紅色****/ p->sibling()->rightTree->color = BLACK; rotate_left(p->sibling()); } else {/****情況4.2：節點為右子樹，那末兄弟左孩子為紅色****/ p->sibling()->leftTree->color = BLACK; rotate_right(p->sibling()); } } } //************************************ // Method: insert // FullName: RedBlackTree::insert // Access: private // Returns: void // Qualifier: 插入數據 // Parameter: Node * p // Parameter: int data //************************************ void RedBlackTree::insert(Node *p, int data) { if (p->value >= data)/**插入數據比data?。ê扔冢┑脑挘M入左側，否則進入右側**/ { 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：父節點和叔節點都是紅色，將祖父，父、叔全換色，最后遞歸處理祖父節點*/ p->parent->color = p->uncle()->color = BLACK; p->grandparent()->color = RED; insert_case(p->grandparent()); } else/*父節點和叔節點都是紅色，叔叔節點黑色*/ { if (p->parent->rightTree == p && p->grandparent()->leftTree == p->parent) {/**情形4：p是父節點的右孩子，父節點是祖父節點的左孩子**/ /********這類情況先調劑父節點，使得其和祖父和父親均在1條線上，注意，這里旋轉后p成新的父節點********/ 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是父節點的左孩子，父節點是祖父節點的右孩子**/ /********這類情況先調劑父節點，使得其和祖父和父親均在1條線上，注意，這里旋轉后p成新的父節點********/ 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是父節點的右孩子，父節點是祖父節點的左孩子**/ 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是父節點的右孩子，父節點是祖父節點的左孩子**/ p->parent->color = BLACK; p->grandparent()->color = RED; rotate_left(p->parent); } } } /*******最后斟酌case2：情況，由于父節點是黑色，所以可以直接退出********/ } //************************************ // 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: 遍歷節點 // 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*/