1、基本概念

  红黑树是一种平衡二叉查找树，不同于AVL树，红黑树必须满足一下几个规则： 1. 树中的节点不是为红色就是为黑色； 2. 根节点的颜色为黑色； 3. 若节点的颜色为红色，则其子节点必然为黑色； 4. 任意节点至NULL的路径上黑色节点的数目是相同的。   根据规则4，可知新增节点必须为红色；根据规则2和3，若节点为红色，则其父节点必然为黑色；根据规则3，若插入节点的父节点为红色，就需要进行平衡调整。

2、节点结构

  红黑树的操作过程需要经常性地访问节点的父节点，因而相对于二叉树的节点结构，这里需要增加指向父节点的指针。同时，红黑树的节点还需要存储该节点的颜色值。这里我还加了子节点位置的定义，可以方便我们获取节点的兄弟节点以及判断节点属于外侧还是内侧。具体定义如下：

enum Color { RED, BLACK }; enum ChildType { NONE, LEFT, RIGHT }; struct RBTreeNode:BTreeNode { RBTreeNode():BTreeNode(),parent(NULL),color(RED){} RBTreeNode(int data,RBTreeNode* leftChild = NULL,RBTreeNode* rightChild = NULL) :BTreeNode(data,leftChild,rightChild),parent(NULL),color(RED) { } RBTreeNode*& getLeftChild() { return (RBTreeNode*&)leftChild; } RBTreeNode*& getRightChild() { return (RBTreeNode*&)rightChild; } RBTreeNode*& getChildByType(ChildType type) { return type == LEFT?getLeftChild():getRightChild(); } RBTreeNode* getSibling() { ChildType type = getChildType(); switch (type) { case LEFT: return (RBTreeNode*)parent->rightChild; case RIGHT: return (RBTreeNode*)parent->leftChild; default: break; } return NULL; } ChildType getChildType() { if (parent != NULL) { return data < parent->data?LEFT:RIGHT; } return NONE; } void handleChildren() { if (getLeftChild() != NULL) { getLeftChild()->parent = this; } if (getRightChild() != NULL) { getRightChild()->parent = this; } } RBTreeNode* parent; Color color; };

3、旋转操作

  红黑树与AVL树一样，需要借助旋转操作进行树的平衡，但红黑树的节点还定义了指向父节点的指针，这个在旋转过程中也需要对应调整，具体实现如下：

void RBTree::rotateWithLeftChild(RBTreeNode* node) { RBTreeNode* leftChild = node->getLeftChild(); node->leftChild = leftChild->rightChild; if (leftChild->rightChild != NULL) { leftChild->getRightChild()->parent = node; } leftChild->parent = node->parent; if (node->getChildType() == NONE) { m_pRoot = leftChild; } else if (node->getChildType() == LEFT) { node->parent->leftChild = leftChild; } else { node->parent->rightChild = leftChild; } leftChild->rightChild = node; node->parent = leftChild; } void RBTree::rotateWithRightChild(RBTreeNode* node) { RBTreeNode* rightChild = (RBTreeNode*)node->rightChild; node->rightChild = rightChild->leftChild; if (rightChild->leftChild != NULL) { rightChild->getLeftChild()->parent = node; } rightChild->parent = node->parent; if (node->getChildType() == NONE) { m_pRoot = rightChild; } else if (node->getChildType() == LEFT) { node->parent->leftChild = rightChild; } else { node->parent->rightChild = rightChild; } rightChild->leftChild = node; node->parent = rightChild; } void RBTree::doubleWithLeftChild(RBTreeNode* node) { rotateWithRightChild(node->getLeftChild()); rotateWithLeftChild(node); } void RBTree::doubleWithRightChild(RBTreeNode* node) { rotateWithLeftChild(node->getRightChild()); rotateWithRightChild(node); }

4、查找操作

  红黑树的查找操作与二叉查找树的查找操作一致，直接复用。

5、插入操作

  红黑树的插入算法与二叉查找树的插入算法一致，但插入节点后，需要根据不同的情况进行不同的操作，插入情况分以下几点： 1. 父节点为空。插入节点的父节点为空，则可知插入节点为根节点，根据规则2将其设置为黑色； 2. 黒父。插入节点的父节点为黑色，此时没有违反任何规则，无需进行平衡处理； 3. 红父红叔。插入节点的父节点和叔父节点的颜色为红色，根据规则可知祖父节点必然为黑色。此时无需旋转，只用将祖父节点设置为红色，将父节点和叔父节点的颜色设置为黑色，祖父节点达到平衡。但是祖父节点可能为根节点或者引起其父节点不平衡，因而需要将祖父节点作为插入节点进行平衡处理； 4. 红父黑叔。插入节点的父节点为红色，叔父节点为空或者黑色，根据规则可知祖父节点必然为黑色。此时根据插入节点的插入位置分为外侧插入和内侧插入：   4.1外侧插入。若插入节点和父节点都是其对应父节点的左子女或者右子女，则为外侧插入。此时将祖父节点设置为红色，父节点的颜色设置为黑色，然后对祖父节点进行单旋转，使祖父节点成为父节点的子节点，达到平衡；   4.2内侧插入。若插入节点和父节点处于其对应父节点的不同子女位置，则为内侧插入。此时将祖父节点设置为红色，插入节点的颜色设置为黑色，然后对祖父节点进行双旋转，使祖父节点成为插入节点的子节点，达到平衡。   以下为插入算法和平衡算法的具体实现：

void RBTree::_insert(int key, BTreeNode* &node) { RBTreeNode* &curNode = (RBTreeNode* &)node; if (curNode == NULL) { curNode = new RBTreeNode(key); balanceTreeNode(curNode); } else { if (key < curNode->data) { if (curNode->leftChild != NULL) { _insert(key, node->leftChild); } else { curNode->leftChild = new RBTreeNode(key); curNode->getLeftChild()->parent = curNode; balanceTreeNode(curNode->getLeftChild()); } } else if (key > curNode->data) { if (curNode->rightChild != NULL) { _insert(key, node->rightChild); } else { curNode->rightChild = new RBTreeNode(key); curNode->getRightChild()->parent = curNode; balanceTreeNode(curNode->getRightChild()); } } else { } } } void RBTree::balanceTreeNode(RBTreeNode* node) { if (node == NULL) { return; } //插入节点为根节点，根节点必须为黑色 if (node->parent == NULL) { node->color = BLACK; return; } //插入节点的父节点为黑色，不破坏平衡 if (node->parent->color == BLACK) { return; } RBTreeNode* parent = node->parent; RBTreeNode* grand = parent->parent; RBTreeNode* uncle = parent->getSibling(); //伯父节点为空或者黑色 if(uncle == NULL || uncle->color == BLACK) { if(node->getChildType() == parent->getChildType()) { //外侧插入 grand->color = RED; parent->color = BLACK; if(node->getChildType() == LEFT) { rotateWithLeftChild(grand); } else { rotateWithRightChild(grand); } } else { //内侧插入 grand->color = RED; node->color = BLACK; if(node->getChildType() == LEFT) { doubleWithRightChild(grand); } else { doubleWithLeftChild(grand); } } } else { //无需旋转，直接改变颜色，然后对祖父节点进行平衡操作 grand->color = RED; parent->color = BLACK; uncle->color = BLACK; balanceTreeNode(grand); } }

6、删除操作

  红黑树的删除算法与二叉查找树的删除算法一致，因此删除的节点必然为单支节点或者叶子节点。但删除节点后，需要进行平衡检测，删除情况分为以下几种： 1. 删除节点为红色。此时根据红黑树规则，删除节点必然为叶子节点，删除后不破坏平衡规则，直接删除即可； 2. 删除节点为黑色。删除该节点后，会选子节点作为替代节点。若替代节点为红色，此时所有经过子节点的路径上的黑色节点的数目都减少了一个，只需将子节点的颜色设置为黑色即可达到平衡； 3. 替换节点为空或者黑色。根据红黑树规则，黑色节点只有一个黑色子节点的情况是不存在的。同时，若删除节点不为根节点，则其兄弟节点必然不为空。此时又有以下几种情况：   3.1替换节点成为根节点。此时不做处理；   3.2红兄。删除节点的兄弟节点为红色，此时父节点的颜色为黑色，兄弟节点的子节点也必然为黑色，将父节点的颜色设置为红色，兄弟节点的颜色设置为黑色，并对父节点进行单旋转，使父节点成为兄弟节点的子节点，转换为黑兄情况；   3.3黑兄二黑侄。删除节点的兄弟节点为黑色，同时兄弟节点没有子节点或者有两个黑色子节点，此时将兄弟节点的颜色设置为红色，父节点达到平衡。但是父节点的颜色不确定，需要把父节点作为新的替换节点进行平衡处理；   3.4黑兄内侧红侄。此时设置兄弟节点的颜色为红色，红侄的颜色设置为黑色，并对兄弟节点进行单旋操作，使红侄成为新的兄弟节点，转为下一种情况；   3.5黑兄外侧红侄。此时设置兄弟节点的颜色为父节点的颜色，设置父节点的颜色为黑色，设置红侄节点的颜色为黑色，然后对父节点进行单旋操作，使兄弟节点成为新的父节点，达到平衡。   以下是删除算法和删除平衡算法的具体实现：

void RBTree::_remove(int key, BTreeNode* &node) { if (node == NULL) { return; } if (key == node->data) { if (node->leftChild != NULL && node->rightChild != NULL) { //替换键值 BTreeNode * temp = _findMin(node->rightChild); node->data = temp->data; //递归删除 _remove(temp->data,node->rightChild); } else { RBTreeNode* &curNode = (RBTreeNode* &)node; RBTreeNode* temp = curNode; RBTreeNode* parent = curNode->parent; RBTreeNode* sibling = curNode->getSibling(); curNode = (curNode->getLeftChild() != NULL)?curNode->getLeftChild():curNode->getRightChild(); if (curNode != NULL) { curNode->parent = parent; } if (temp->color == RED) { //红色节点直接删除 delete temp; } else { balanceTreeNodeRemove(curNode,parent); delete temp; } } } else if (key < node->data) { _remove(key,node->leftChild); } else { _remove(key,node->rightChild); } } void RBTree::balanceTreeNodeRemove(RBTreeNode* node, RBTreeNode* parent) { while (true) { //根节点，不再处理 if (node == m_pRoot) { break; } //红色节点，直接变为黑色 if (node != NULL && node->color == RED) { node->color = BLACK; break; } RBTreeNode* sibling = parent->getLeftChild() == node? parent->getRightChild():parent->getLeftChild(); if (sibling->color == RED) { //兄弟节点为红色，转为兄弟节点为黑色的情况 parent->color = RED; sibling->color = BLACK; if (sibling->getChildType() == LEFT) { rotateWithLeftChild(parent); } else { rotateWithRightChild(parent); } //重新获取兄弟节点 sibling = parent->getLeftChild() == node? parent->getRightChild():parent->getLeftChild(); } //黑兄二黑侄 if ((sibling->leftChild == NULL || sibling->getLeftChild()->color == BLACK) && (sibling->rightChild == NULL || sibling->getRightChild()->color == BLACK)) { //黑兄二黑侄红父或黑兄二黑侄黑父 sibling->color = RED; node = parent; parent = node->parent; } else { ChildType type = sibling->getChildType() == LEFT?RIGHT:LEFT; RBTreeNode* child = sibling->getChildByType(type); //黑兄内侧红侄 if (child != NULL && child->color == RED) { sibling->color = RED; if (type == LEFT) { sibling->getLeftChild()->color = BLACK; rotateWithLeftChild(sibling); sibling = sibling->getLeftChild(); } else { sibling->getRightChild()->color = BLACK; rotateWithRightChild(sibling); sibling = sibling->getRightChild(); } } //黑兄外侧红侄 sibling->color = parent->color; parent->color = BLACK; type = sibling->getChildType(); if (type == LEFT) { if (sibling->getLeftChild() != NULL) { sibling->getLeftChild()->color = BLACK; } rotateWithLeftChild(parent); } else { if (sibling->getLeftChild() != NULL) { sibling->getLeftChild()->color = BLACK; } rotateWithRightChild(parent); } break; } } }

5、清理操作

  红黑树的清理操作与二叉树的清理操作一致，直接复用。

6、结果测试

  这里对红黑树进行具体的测试，代码如下：

RBTree* rbTree = new RBTree(); rbTree->insert(3); rbTree->insert(2); rbTree->insert(4); rbTree->insert(1); rbTree->insert(5); rbTree->insert(6); rbTree->insert(7); rbTree->insert(8); rbTree->insert(9); cout<<"contains 5:"<<rbTree->contains(5)<<endl; //contains 5:1 cout<<"contains 10:"<<rbTree->contains(10)<<endl; //contains 10:0 rbTree->breadthFirstTravel(); //bft:5 3 7 2 4 6 8 1 9 rbTree->depthFirstTravel_DLR(); //depthFirstTravel_DLR:5(b) 3(r) 2(b) 1(r) 4(b) 7(r) 6(b) 8(b) 9(r) rbTree->depthFirstTravel_LDR(); //depthFirstTravel_LDR:1 2 3 4 5 6 7 8 9 rbTree->depthFirstTravel_LRD(); //depthFirstTravel_LRD:1 2 4 3 6 9 8 7 5 rbTree->remove(7); rbTree->breadthFirstTravel(); //bft:5 3 8 2 4 6 9 1 rbTree->depthFirstTravel_DLR(); //depthFirstTravel_DLR:5(b) 3(r) 2(b) 1(r) 4(b) 8(r) 6(b) 9(b) rbTree->depthFirstTravel_LDR(); //depthFirstTravel_LDR:1 2 3 4 5 6 8 9 rbTree->depthFirstTravel_LRD(); //depthFirstTravel_LRD:1 2 4 3 6 9 8 5 rbTree->clear(); rbTree->breadthFirstTravel(); //bft:

6、效率分析

  红黑树与AVL树效率一致，但其平衡性没有AVL树那么严格，能够在保持平衡的情况下出现更少需要进行平衡调整的情况，因而拥有更好的统计性能。