〈如何创建二叉排序树〉创建一个二叉排序树…

红黑树是一种自平衡的二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组(C++ STL 中的map/set)。它是在1972年由Rudolf Bayer发明的，他称之为"对称二叉B树"，它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。红黑树虽然很复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。

自平衡二叉查找树（BBST(Balance Binary Search Tree)主要有AVL树和红黑树，前者要求节点的 |balFact| <= 1，后者只要求部分达到平衡。

红黑树在每个结点上增加一个数据域表示结点的颜色，可以是Red或BLACK。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。

普通的二叉查找树不具备自动平衡的功能, 因此普通的二叉查找树树很有可能会退化成为一条链表, 若二叉树退化成了一棵具有n个结点的线性链后，则插入/删除/查找操作最坏情况运行时间就变为了O（n）。

因此就有了红黑树, 他的最终查找、插入、删除的时间复杂度最坏情况下依然为O（logn）, 而红黑树之所以这么牛的原因就是它在二叉查找树的基础上增加了着色和相关的性质, 这就是红黑规则：

① 每一个节点不是红色的就是黑色的;

② 根总是黑色的;

③ 如果节点是红色的, 则它的子节点必须是黑色的;

④ 从根到叶节点的每条路径, 必须包含相同数目的黑色节点(黑高度相同);

⑤ 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的;

1 简单版的insert函数和单独的旋转函数

#include <iostream> #include <string> using namespace std; template <class Comparable> class RedBlackTree; template <class Comparable> class RedBlackNode; template <class Comparable> class RedBlackTree { public: RedBlackTree(const Comparable& negInf); enum{RED,BLACK}; ~RedBlackTree(); void insert(const Comparable& x); typedef RedBlackNode<Comparable> Node; //private: // for test Node* header; Node* nullNode; Node* current; Node* parent; Node* grand; Node* great; void rotateWithLeftChild(Node* &k2) const; void rotateWithrightChild(Node* &k1) const; void doubleRotateWithLeftChild(Node* &k3) const; void doubleRotateWithrightChild(Node* &k4) const; }; template <class Comparable> class RedBlackNode { public: // for test Comparable element; RedBlackNode* left; RedBlackNode* right; int color; RedBlackNode(const Comparable& theElement = Comparable(), RedBlackNode* lt=NULL, RedBlackNode* rt=NULL, int c=RedBlackTree<Comparable>::BLACK) :element(theElement),left(lt),right(rt),color(c){} friend class RedBlackTree<Comparable>; }; template <class Comparable> RedBlackTree<Comparable>:: RedBlackTree(const Comparable& negInf) { nullNode = new Node(); nullNode->left = nullNode->right=nullNode; header=new Node(negInf); header->left=header->right=nullNode; } template <class comparable> RedBlackTree<comparable>::~RedBlackTree() { delete nullNode; delete header; } class DSException { public: DSException(const string & msg = ""):message(msg){} virtual ~DSException(){} virtual string toString() const { return "Exception " + string(": ") + what(); } virtual string what() const { return message; } private: string message; }; class DuplicateItemException: public DSException { public: DuplicateItemException(const string& msg = "") : DSException(msg){} }; template <class Comparable> void RedBlackTree<Comparable>::insert(const Comparable& x) { current=parent=grand=header; nullNode->element = x; while(current->element != x) { great = grand, grand = parent; parent = current; current = x < current->element ? current->left : current->right; } if(current != nullNode) throw DuplicateItemException(); current = new Node(x,nullNode,nullNode); if(x < parent->element) parent->left = current; else parent->right = current; // 需要自动动态平衡才是红黑树 // 新插入的节点是红色的 // 新插入的是外部孙子（左），做单旋转，如果是内部孙子（右），做双旋转 } template <class Comparable> void RedBlackTree<Comparable>::rotateWithLeftChild(Node* &k2) const { Node* k1=k2->left; k2->left=k1->right; k1->right=k2; k2=k1; //k1现在是根 } template <class Comparable> void RedBlackTree<Comparable>::rotateWithRightChild(Node* &k1) const { Node* k2=k1->right; k1->right = k2->left; k2->left=k1; k1=k2; } template <class Comparable> void RedBlackTree<Comparable>::doubleRotateWithLeftChild(Node* &k3) const { rotateWithRightChild(k3->left); rotateWithLeftChild(k3); } template <class Comparable> void RedBlackTree<Comparable>::doubleRotateWithrightChild(Node* &k4) const { rotateWithLeftChild(k4->right); rotateWithRightChild(k4); } /* -∞ \ 30 / \ 15 70 \ 20 */ int main() { const int NEG_INF = -99999; RedBlackTree<int> t(NEG_INF); #if 0 t.insert(30); t.insert(15); t.insert(70); t.insert(20); cout<< t.header->right->element<<endl; cout<< t.header->right->left->element<<endl; cout<< t.header->right->right->element<<endl; cout<< t.header->right->left->right->element<<endl; cout<<"向右转"<<endl; t.rotateWithLeftChild;right); /* -∞ \ 30 / \ 15 70 \ 20 */ /* -∞ \ 15 \ 30 / \ 20 70 */ cout<<t.header->right->element<<endl; cout<<t.header->right->right->left->element<<endl; cout<<"向左转"<<endl; t.rotateWithRightChild;right); cout<< t.header->right->element<<endl; cout<< t.header->right->left->element<<endl; cout<< t.header->right->right->element<<endl; cout<< t.header->right->left->right->element<<endl; #else t.insert(12); t.insert(16); t.insert(8); t.insert(10); t.insert(4); t.insert(14); t.insert(2); t.insert(6); t.insert(5); /* 12 / \ 8 16 /\ / 4 10 14 / \ 2 6 / 5 */ cout<<t.header->right->left->element<<endl; t.doubleRotateWithLeftChild;right->left); cout<<t.header->right->left->element<<endl; /* 12 / \ 6 16 /\ / 4 8 14 / \ \ 2 5 10 */ #endif cout<<"OK"<<endl; system("pause"); return 0; } /* 30 15 70 20 向右转 15 20 向左转 30 15 70 20 OK */

单旋转（内侧孙子节点横向移动）：

① 右旋：

void RedBlackTree<Comparable>::rotateWithLeftChild(Node* &S) const { Node* E=S->left; S->left=E->right; E->right=S; S=E; //k1现在是根 }

② 左旋：

template <class Comparable> void RedBlackTree<Comparable>::rotateWithRightChild(Node* &E) const { Node* T=E->right; // T现在指向S E->right = T->left; // S的右节点做E的左节点 T->left=E; // 做S的左节点 E=T; // E被S取代 }

③ 双旋转：

void RedBlackTree<Comparable>::doubleRotateWithLeftChild(Node* &k3) const { rotateWithRightChild(k3->left); rotateWithLeftChild(k3); }

参考：

2 插入时实现自动动态平衡

新增函数和修改insert函数

template <class Comparable> void RedBlackTree<Comparable>::insert(const Comparable& x) { current=parent=grand=header; nullNode->element = x; while(current->element != x) { great = grand, grand = parent; parent = current; current = x < current->element ? current->left : current->right; if(current->left->color == RED && current->right->color == RED) handleReorient(x); } if(current != nullNode) throw DuplicateItemException(); current = new Node(x,nullNode,nullNode); if(x < parent->element) parent->left = current; else parent->right = current; // 需要自动动态平衡才是红黑树 // 新插入的节点是红色的 // 新插入的是外部孙子（左），做单旋转，如果是内部孙子（右），做双旋转 handleReorient(x); } template <class Comparable> void RedBlackTree<Comparable>:: handleReorient(const Comparable& item) { // 变色 current->color=RED; current->left->color=BLACK; current->right->color=BLACK; if(parent->color == RED) { grand->color=RED; if(item < grand->element != item < parent->element) // 内部孙子（右） parent = rotate(item,grand); // 多一次旋转 current = rotate(item,great); current->color = BLACK; } header->right->color = BLACK; } template <class Comparable> RedBlackNode<Comparable>* void RedBlackTree<Comparable>::rotate(const Comparable& item, Node* parent) const { if(item < parent->element) { item < parent->left->element ? rotateWithLeftChild(parent->left): rotateWithRightChild(parent->left); return parent->left; } else { item < parent->right->element ? rotateWithLeftChild(parent->right) : rotateWithRightChild(parent->right); return parent->right; } }

3 实现更多方法的红黑树

#include <iostream> #include <string> using namespace std; template <class Comparable> class RedBlackTree; template <class Comparable> class RedBlackNode; template <typename Object> class Cref; template <class Comparable> class RedBlackTree // ReadBlackTree类 { public: RedBlackTree(const Comparable& negInf); enum{RED,BLACK}; ~RedBlackTree(); void insert(const Comparable& x); bool isEmpty() const; void makeEmpty(); Cref<Comparable> find(const Comparable & x) const; // 返回一个用指针封装的引用，因为引用不能为空 Cref<Comparable> findMin() const; Cref<Comparable> findMax() const; typedef RedBlackNode<Comparable> Node; private: Node* header; //指向红黑树的头(伪根节点) Node* nullNode; //在insert时使用以下四个指针 Node *current; // 当前节点 Node *parent; // 父节点 Node *grand; // 祖父节点 Node *great; // 曾祖父节点 void rotateWithLeftChild(Node* &k2) const; // 向右转(带着右孩子) void rotateWithRightChild(Node* &k1) const; // 向左转(带着左孩子) void doubleRotateWithLeftChild(Node* &k3) const; void doubleRotateWithrightChild(Node* &k4) const; // 自动处理: [1]重新染色; [2]:自动旋转 void handleReorient(const Comparable& item); // 自动旋转函数(返回旋转以后的theParent子树的根) RedBlackNode<Comparable>* rotate(const Comparable& item, Node* parent) const; void reclainMemory(Node *t) const; // 递归删除所有节点 }; template <class Comparable> class RedBlackNode // RedBlackNode类 { public: Comparable element; RedBlackNode* left; RedBlackNode* right; int color; RedBlackNode(const Comparable& theElement = Comparable(), RedBlackNode* lt=NULL, RedBlackNode* rt=NULL, int c=RedBlackTree<Comparable>::BLACK) :element(theElement),left(lt),right(rt),color(c){} friend class RedBlackTree<Comparable>; }; template <class Comparable> RedBlackTree<Comparable>:: RedBlackTree(const Comparable& negInf) // RedBlackTree构造函数 { nullNode = new Node(); //nullNode 的左右子节点都指向自己 nullNode->left = nullNode->right=nullNode; header=new Node(negInf); header->left=header->right=nullNode; } template <class comparable> RedBlackTree<comparable>::~RedBlackTree() // RedBlackTree析构函数 { if (!isEmpty()) makeEmpty(); delete nullNode; delete header; } class DSException // DSException类 { public: DSException(const string & msg = ""):message(msg){} virtual ~DSException(){} virtual string toString() const { return "Exception " + string(": ") + what(); } virtual string what() const { return message; } private: string message; }; class DuplicateItemException: public DSException { public: DuplicateItemException(const string& msg = "") : DSException(msg){} }; class NullPointerException : public DSException { public: NullPointerException(const string &_msg = string()) : DSException(_msg) {} }; template <class Comparable> void RedBlackTree<Comparable>::insert(const Comparable& x) // insert() { current=parent=grand=header; nullNode->element = x; while(current->element != x) { // 让祖父成为曾祖父, 父亲成为祖父, 自己成为父亲 // 每个节点都成长一辈 great = grand, grand = parent; parent = current; current = x < current->element ? current->left : current->right; //处理1. 如果current节点有两个红色孩子 if(current->left->color == RED && current->right->color == RED) handleReorient(x); } if(current != nullNode) // 如果树中包含相同的元素 throw DuplicateItemException(); current = new Node(x,nullNode,nullNode); if(x < parent->element) parent->left = current; else parent->right = current; // 需要自动动态平衡才是红黑树 // 新插入的节点是红色的 // 新插入的是外部孙子（左），做单旋转，如果是内部孙子（右），做双旋转 // 处理2. 如果新插入的节点破坏了红黑规则 handleReorient(x); } // 自动平衡函数:[1]重新染色；[2]自动旋转 template <class Comparable> void RedBlackTree<Comparable>:: handleReorient(const Comparable& item) // handleReorient() { current->color=RED; // 将current节点染成红色 current->left->color=BLACK; // 将current的left和right节点染成黑色 current->right->color=BLACK; // 如果current节点的父节点也是红的 -> 单旋转 or 双旋转 if(parent->color == RED) { grand->color=RED; // 则将其祖父(爷爷)的颜色染成红色 // 然后判断新插入的节点是否是内部孙子(右节点)? // 如果是, 则增加一次旋转->构成双旋转 // if注释: 如果该节点小于爷爷, 小于爸爸, 这两种情况不同时满足 // 则说明其是爷爷的内孙子 if(item < grand->element != item < parent->element) parent = rotate(item,grand); // 依grand(祖父)节点进行旋转 current = rotate(item,great); // 依great(曾祖父)节点进行旋转 current->color = BLACK; // 令当前节点为黑色 } header->right->color = BLACK; // 根节点必须是黑色的 } template <class Comparable> //自动判断并进行旋转函数 RedBlackNode<Comparable>* void RedBlackTree<Comparable>:: rotate(const Comparable& item, Node* parent) const // rotate() { if(item < parent->element) //位于parent的左子树 { //如果为真, 则说明parent->left有左孩子,否则, 有右孩子 item < parent->left->element ? //如果parent左边有一棵子树, 则以parent->left为轴, 向右转 rotateWithLeftChild( parent->left ) : // LL //如果parent右边有一棵子树, 则以parent->left为轴, 向左转 rotateWithRightChild( parent->left ) ; // LR return parent->left; //返回左子树 } else //位于右子树 { //如果为真, 则说明parent->right有左孩子,往右转，否则, 有右孩子, 往左转 item < parent->right->element ? rotateWithLeftChild( parent->right ) : // RL rotateWithRightChild( parent->right ); // RR return parent->right; // 返回右子树 } } template <class Comparable> void RedBlackTree<Comparable>::rotateWithLeftChild(Node* &k2) const // 右(单)旋转 { Node* k1=k2->left; k2->left=k1->right; k1->right=k2; k2=k1; //k1现在是根 } template <class Comparable> void RedBlackTree<Comparable>::rotateWithRightChild(Node* &k1) const // 左(单)旋转 { Node* k2=k1->right; k1->right = k2->left; k2->left=k1; k1=k2; } template <class Comparable> void RedBlackTree<Comparable>::doubleRotateWithLeftChild(Node* &k3) const { rotateWithRightChild(k3->left); rotateWithLeftChild(k3); } template <class Comparable> void RedBlackTree<Comparable>::doubleRotateWithrightChild(Node* &k4) const { rotateWithLeftChild(k4->right); rotateWithRightChild(k4); } template <typename Comparable> Cref<Comparable> RedBlackTree<Comparable>::find(const Comparable &x) const // find() { if (isEmpty()) return Cref<Comparable>(); nullNode->element = x; Node *iter = header->right; while (true) { if (x < iter->element) iter = iter->left; else if (x > iter->element) iter = iter->right; else if (iter != nullNode) return Cref<Comparable>(iter->element) ; else return Cref<Comparable>(); } } template <typename Comparable> Cref<Comparable> RedBlackTree<Comparable>::findMax() const // findMax() { if (isEmpty()) return Cref<Comparable>(); Node *iter = header->right; while (iter->right != nullNode) { iter = iter->right; // 一直向右走 } return Cref<Comparable>(iter->element); } template <typename Comparable> Cref<Comparable> RedBlackTree<Comparable>::findMin() const // findMin() { if (isEmpty()) return Cref<Comparable>(); Node *iter = header->right; while (iter->left != nullNode) { // 一直向左走 iter = iter->left; } return Cref<Comparable>(iter->element); } template <typename Comparable> bool RedBlackTree<Comparable>::isEmpty() const // isEmpty() { if (header->right == nullNode) return true; return false; } template <typename Comparable> void RedBlackTree<Comparable>::makeEmpty() // makeEmpty() { reclainMemory(header->right); header->right = nullNode; } template <typename Comparable> void RedBlackTree<Comparable>::reclainMemory(Node *t) const // reclainMemory() { //t == t->left的时候, 是当t==nullNode时 if (t != t->left) { reclainMemory(t->left); reclainMemory(t->right); delete t; } } // 一个用指针封装的引用，因为查找时可能返回空，但引用是不能为空的 template <typename Object> // Cref类 class Cref { public: Cref():obj(NULL) {} explicit Cref(const Object &x) : obj(& x) {} const Object &get() const { if (isNull()) throw NullPointerException(); else return * obj; } bool isNull() const { if (obj == NULL) return true; return false; } private: const Object * obj; }; int main() { const int NEG_INF = -999999; RedBlackTree<int> tree(NEG_INF); (50); (40); (30); (10); (55); (88); (200); (100); (70); (80); (650); Cref<int> g = (); cout << "Min = " << g.get() << endl; g = (); cout << "Max = " << g.get() << endl; int searchVal; cout<<"请输入需要查找的数字(输入null则清空树)："; while (cin >> searchVal) { g = (searchVal); if ()) cout << "not found" << endl; else cout << g.get() << " founded" << endl; } (); if ()) { cout << "is Empty" << endl; } else { cout << "not Empty" << endl; } system("pause"); return 0; } /* Min = 10 Max = 650 请输入需要查找的数字(输入null则清空树)：10 10 founded 200 200 founded 234 not found null is Empty */

AVL树是最先发明的自平衡二叉查找树（BBST(Balance Binary Search Tree)）。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它。

红黑树（RB-Tree）和AVL树作为BBST，其实现的算法时间复杂度相同，AVL作为最先提出的BBST，貌似RB-tree实现的功能都可以用AVL树是代替，那么为什么还需要引入RB-Tree呢？

① 黑树不追求"完全平衡"，即不像AVL那样要求节点的 |balFact| <= 1，它只要求部分达到平衡，但是提出了为节点增加颜色，红黑是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，而AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多。

② 就插入节点导致树失衡的情况，AVL和RB-Tree都是最多两次树旋转来实现复衡rebalance，旋转的量级是O(1)。删除节点导致失衡，AVL需要维护从被删除节点到根节点root这条路径上所有节点的平衡，旋转的量级为O(logN)，而RB-Tree最多只需要旋转3次实现复衡，只需O(1)，所以说RB-Tree删除节点的rebalance的效率更高，开销更小！

③ AVL的结构相较于RB-Tree更为平衡，插入和删除引起失衡，如②所述，RB-Tree复衡效率更高；当然，由于AVL高度平衡，因此AVL的Search效率更高啦。

④ 针对插入和删除节点导致失衡后的rebalance操作，红黑树能够提供一个比较"便宜"的解决方案，降低开销，是对search，insert ，以及delete效率的折衷，总体来说，RB-Tree的统计性能高于AVL。

⑤ 故引入RB-Tree是功能、性能、空间开销的折中结果。
5.1 AVL更平衡，结构上更加直观，时间效能针对读取而言更高；维护稍慢，空间开销较大。
5.2 红黑树，读取略逊于AVL，维护强于AVL，空间开销与AVL类似，内容极多时略优于AVL，维护优于AVL。
基本上就主要的几种平衡树看来，红黑树有着良好的稳定性和完整的功能，性能表现也很不错，综合实力强，在诸如STL的场景中需要稳定表现。

红黑树的查询性能略微逊色于AVL树，因为其比AVL树会稍微不平衡最多一层，也就是说红黑树的查询性能只比相同内容的AVL树最多多一次比较，但是，红黑树在插入和删除上优于AVL树，AVL树每次插入删除会进行大量的平衡度计算，而红黑树为了维持红黑性质所做的红黑变换和旋转的开销，相较于AVL树为了维持平衡的开销要小得多

总结：实际应用中，若搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，应该选择RB。

－End－