红黑树源代码  //RedBlack.h
#ifndef REDBLACK_INCLUDE
#define REDBLACK_INCLUDE
template<typename T>
class RedBlackTree
  ...{
  struct Node...{
 T key;
bool color;
Node* parent;
Node* left;
Node* right;
Node(T data_, bool color_, Node* p, Node* l, Node* r)
:key(data_),color(color_),parent(p),left(l),right(r)...{}
 };
Node* NIL;
Node* root;
bool RED ;
bool BLACK ;
public:
RedBlackTree(T data=0, bool str=false, Node* p=NULL, Node* q=NULL, Node* e=NULL):RED(true),BLACK(false)
...{
NIL = new Node(0, BLACK, NIL, NIL, NIL);//哨兵结点
root = NIL;
}
~RedBlackTree()
...{
DeleteTree(root);
delete NIL;
}
void LeftRotate(Node* x);
void RightRotate(Node* y);
void RBInsert(T data);
void RBInsertFixup(Node* z);
void RBDelete(T data);
void RBDeleteFixUp(Node* x);
Node* TreeSearchNumber(Node* x, T k);
Node* TreeSuccessor(Node* x);
void DeleteTree(Node* x);
void PrintTree(Node* x);
Node* GetNode(void);
Node* TreeMinIMUM(Node* x );
 };
#endif
//RedBlackTree_.h
#ifndef REDBLACKTREE_H_INCLUDE
#define REDBLACKTREE_H_INCLUDE
#include "RedBlack.h"
#include <assert.h>
#include <string>
#include <iostream>
template<typename T>
RedBlackTree<T>::Node* RedBlackTree<T>::TreeMinIMUM(Node* x )
...{
while(x->left != NIL)
x = x->left;
return x;
}
template<typename T>
RedBlackTree<T>::Node* RedBlackTree<T>::GetNode(void)
...{
return root;
}
template<typename T>
void RedBlackTree<T>::PrintTree(Node* x)
...{
if(NIL != x)...{
if(NIL != x->left)
...{
PrintTree(x->left);
}
if(NIL != x->right)
...{
PrintTree(x->right);
}
std::cout<<x->key<<std::endl;
}
}
template<typename T>
void RedBlackTree<T>::DeleteTree(Node* x)
...{
if(x != NIL)
...{
if(NIL != x->left )
...{
DeleteTree(x->left);
}
if(NIL != x->right )
...{
DeleteTree(x->right);
}
delete x;
x = NULL;
}
}
template<typename T>
RedBlackTree<T>::Node* RedBlackTree<T>::TreeSearchNumber(Node* x, T k)
...{
if( x == NIL || k == x->key )
return x;
if( k < x->key )
return TreeSearchNumber(x->left, k);
else
return TreeSearchNumber(x->right, k);
}
template<typename T>
RedBlackTree<T>::Node* RedBlackTree<T>::TreeSuccessor(Node* x)//存在两种情况:
...{
if (x->right != NIL)//如果结点x的右子树非空，则x的后继即右子树中的最左的结点。
return TreeMinIMUM(x->right) ;
Node* y = x->parent;//如果结点x的右子树为空，且x有一个后继y，则y是x的最低祖先结点，
while( (y != NIL) && (x == x->right))//且y的左儿子也是x的祖先票篇 p154,p155《算法导论》
...{
x = y;
y = y->parent;
}
return y;
}
template<typename T>
void RedBlackTree<T>::LeftRotate(Node* x)
...{
Node* y = x->right; //y是x的右结点
if(NIL == y)
return;
x->right = y->left; //让x的右指针指向y的左结点。
if(NIL != y->left) //y的左结点不是哨兵
y->left->parent = x;//让y的左结点的parent指向x
y->parent = x->parent; //让y的父子针指向x的父结点
if(x->parent == NIL) //x为根结点
...{
root = y;//让y成为根结点
}
else if(x == x->parent->left)//如果x为左子女
...{
x->parent->left = y; //y便代替x成为左子女
}
else
x->parent->right =y; //否则代替x成为右子女
y->left = x; //x成为y的左子女
x->parent = y; //y成为x的父结点
}
//______________________________________________________________//
// //
// | | //
// X left_Rotate(T,x) Y //
// / -----------------> / //
// α Y <---------------- X γ //
// / Right_Rotate(T,y) / //
// β γ α β //
//______________________________________________________________//
template<typename T>
void RedBlackTree<T>::RightRotate(Node* y )
...{
Node* x = y->left;
if(NIL == x)
return;
y->left = x->right;
if(x->right != NIL)
x->right->parent = y;
x->parent = y->parent;
if(y->parent == NIL)
...{
root = x;
}
else if (y == y->parent->right)
...{
y->parent->right = x;
}
else
...{
y->parent->left = x;
}
x->right = y;
y->parent = x;
}
template<typename T>
void RedBlackTree<T>::RBInsert(T data)
...{
Node* x = root;
Node* z = new Node(data,RED,NULL,NULL,NULL);//将要插入的结点
assert(z != NULL);
Node* y = NIL;
while( x != NIL)
...{
y = x;
if(z->key < x->key)
...{
if(x->left != NIL)
...{
x = x->left;
}
else
...{
break;
}
}
else
...{
if(x->right != NIL)
...{
x = x->right;
}
else
...{
break;
}
}
}
z->parent = y;
if(y == NIL)
root = z;
else if(z->key < y->key)
y->left = z;
else
y->right = z;
z->left = NIL;
z->right = NIL;
z->color = RED;
RBInsertFixup(z);
}
//在调用RBInsertFixup()，那些红黑树的性质可能会被破坏呢？性质1和性质3当然继续成立，
//因为新插入的结点的子女都是哨兵NIL。性质5即从一个制定结点开始的每条路径上黑结点的个数
//都是相等的，也会成立，因为结点z本身就是具有哨兵子女的红结点。因此，可能被破坏的就是根节点2，
//以及一个红结点不能有红子女的性质4。这两个可能的破坏是因为z被着为红色。如果z是根结点则破坏了性质2,
//如果z的父结点是红色就破坏了性质4.
template<typename T>
void RedBlackTree<T>::RBInsertFixup(Node* z)
...{
Node* y = NIL;
while( root != z && z->parent->color == RED)
...{
if( z->parent == z->parent->parent->left)
...{
y = z->parent->parent->right;
if(y != NIL && y->color == RED )
...{
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else
...{
if( z == z->parent->right)
...{
z = z->parent;
LeftRotate(z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;//还没旋转
|
