rb-tree.txt

红黑树的算法

/*
 *
  red-black tree
  for xxx
  author : xxx
  date : xxx
 *
 */
 
#ifndef __RBTREE__H__
#define __RBTREE__H__

#include "unistd.h"
#include "fstream.h"

#define true	1
#define false	0


typedef enum {
    RBT_STATUS_OK,
    RBT_STATUS_MEM_EXHAUSTED,
    RBT_STATUS_DUPLICATE_KEY,
    RBT_STATUS_KEY_NOT_FOUND
} RbtStatus;

//这是一个难以解决的问题，下面的这样声明就是不行
// warning: dangling comma in an enum list
//然后就是不认识变量 nodeColor，TNND，烂编译器
//typedef enum { BLACK, RED } nodeColor;

#define BLACK 0
#ifdef RED
    #undef RED
#endif
#define RED 1
typedef int nodeColor;

template <class type> class RBTree;

template <class type>
class TreeNode
{
public:
	type key;
	nodeColor color;
	TreeNode<type>* left;
	TreeNode<type>* right;
	TreeNode<type>* parent;

public:

	friend class RBTree<type>;

	TreeNode():left(NULL), right(NULL), parent(NULL){ memset(&key, 0, sizeof(type));};
	TreeNode(const type& item, 
		TreeNode<type>* l =NULL,
		TreeNode<type>* r =NULL,// key(item),
		TreeNode<type>* p =NULL):left(l), right(r),parent(p){key =item;};
	~TreeNode()
	{
		//if(left !=NULL){	delete left;	left =NULL;		}
		//if(right !=NULL){	delete right;	right =NULL;	}
	}
//TNND, 都定义友元了，还要这些函数干什么
	type& GetKey(){ return key;};

	void SetData(type& item) {key =item;}
	void SetLeft(TreeNode<type>* l) { left =l;}
	void SetRight(TreeNode<type>* r) { right =r;}

//	friend ostream& operator <<(ostream& out, const TreeNode<type>* p)
//	{		return out<<"node-> "<<p.GetKey()<<endl;	}
};


template <class type> 
class RBTree
{
	TreeNode<type>* header;
	unsigned int node_count;
	void init()
	{
		
		header =new TreeNode<type>;
		header->color =RED;
		header->parent =NULL;
		header->left =header;
		header->right =header;
	}

public:
	RBTree(): node_count(0){ init(); };
	virtual ~RBTree()
	{
		Destroy();
		if(header !=NULL){
//			cout<<"header add : "<<header<<endl;
			delete header;
		}
		header =NULL;
	}

void Destroy()
{
//	static int flag =0;
//	cout<<"destroy [flag] = "<<flag ++<<endl;
	
	Delete(root());
	node_count =0;
	
	if(header){
		header->parent =NULL;
		header->color =RED;
		header->left =header;
		header->right =header;
	}
}
void Delete(TreeNode<type> *p)
{
	if (p == NULL) return;
	
//	cout<<"addr [p] : "<<p<<endl;
	
//	static int flag =0;
//	cout<<"delete [flag] = "<<flag ++<<endl;
	
    Delete(p->left);
    Delete(p->right);
    delete p;
	p =NULL;
}


TreeNode<type>*& leftmost(){ return header->left;} 
TreeNode<type>*& rightmost(){ return header->right;} 
TreeNode<type>*& root(){ return header->parent;} 

TreeNode<type>* begin(){ return leftmost();} 
TreeNode<type>* end(){ return header;} 

/*
	type* next()
	{
		//真是奇怪，在这里 p 始终为 null 值
		static TreeNode<type>* p =leftmost();
		increment(p);
		return &p->key;
	}
*/
	
//这个变量 mark 不得已加的，因为上面注释掉的函数不好用，不知道为什么。在 VC 中没有问题
TreeNode<type>* mark;
type* first(){ mark =leftmost(); return &leftmost()->key;}
type* last(){ return &end()->key;}

type* next()
{
	increment(mark);
	return &mark->key;
}


int empty() const { return node_count == 0; }
unsigned int size() const { return node_count; }
unsigned int height()
{
	while(root() ==NULL)  return 0;
	TreeNode<type>* p =leftmost();

	int a =0;
	while(p !=root()){
		p =p->parent;
		a ++;
	}
	
	int b =0;
	p =rightmost();
	while(p !=root()){
		p =p->parent;
		b ++;
	}
	return a >b ? a: b;
}
	
void rotateLeft(TreeNode<type>* x)
{
 // x 为旋转点
  TreeNode<type>* y = x->right;	// 令y 为旋转点的右子节点
  x->right = y->left;
  if (y->left !=0)
    y->left->parent = x;		// 别忘了回马枪设定父节点
  y->parent = x->parent;

  // 令 y 完全顶替 x 的地位（必须将 x 对其父节点的关系完全接收过来）
  if (x == root())					// x 为根节点
    root() = y;
  else if (x == x->parent->left)	// x 为其父节点的左子节点
    x->parent->left = y;
  else							// x 为其父节点的右子节点
    x->parent->right = y;			
  y->left = x;
  x->parent = y;
}


void rotateRight(TreeNode<type>* x)
{
  // x 为旋转点
  TreeNode<type>* y = x->left;	// y 为旋转点的左子节点
  x->left = y->right;
  if (y->right != 0)
    y->right->parent = x; 	// 别忘了回马枪设定父节点
  y->parent = x->parent;

  // 令 y 完全顶替 x 的地位（必须将 x 对其父节点的关系完全接收过来）
  if (x == root())					// x 为根节点
    root() = y;
  else if (x == x->parent->right)	// x 为其父节点的右子节点
    x->parent->right = y;
  else							// x 为其父节点的左子节点
    x->parent->left = y;
  y->right = x;
  x->parent = y;
}




void deleteFixup( TreeNode<type> *x) {

    // maintain red-black tree balance
    // after deleting node x

    while (x != root() && x->color == BLACK) {
        if (x == x->parent->left) {
            TreeNode<type> *w = x->parent->right;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                rotateLeft (x->parent);
                w = x->parent->right;
            }
            if (w->left->color == BLACK && w->right->color == BLACK) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->right->color == BLACK) {
                    w->left->color = BLACK;
                    w->color = RED;
                    rotateRight (w);
                    w = x->parent->right;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->right->color = BLACK;
                rotateLeft (x->parent);
                x = root();
            }
        } else {
            TreeNode<type> *w = x->parent->left;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                rotateRight (x->parent);
                w = x->parent->left;
            }
            if (w->right->color == BLACK && w->left->color == BLACK) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->left->color == BLACK) {
                    w->right->color = BLACK;
                    w->color = RED;
                    rotateLeft (w);
                    w = x->parent->left;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color = BLACK;
                rotateRight (x->parent);
                x = root();
            }
        }
    }
    x->color = BLACK;
}

RbtStatus Insert_equal(type& v)
{
  TreeNode<type>* y = header;
  TreeNode<type>* x = root();	// 從根節點開始
  while (x != 0) {		// 從根節點開始，往下尋找適當的安插點
    y = x;
    x = v > x->key ? x->left : x->right;
    // 以上，遇「大」則往左，遇「小於或等於」則往右
  }
  return __insert(x, y, v);
}

RbtStatus Insert(type& key)
{
	//cout<<"lizhi--+ Insert begin"<<endl;
	 TreeNode<type>* y =header;
	 TreeNode<type>* x =root();		//从根节点开始