数据结构 -- 二叉树(BST, AVLTree, RBTree, SplayTree)

evasiu

浏览: 171454 次
性别:
来自: 广州

最近访客更多访客>>

redky

toilet22

ilotuo

金武飞扬

博主相关

博客

微博

相册

留言

关于我

博客专栏

: TCP/IP详解卷一>阅读...
浏览量：12649

文章分类

社区版块

存档分类

博客分类：

阅读
编程

在《基于树的索引结构介绍》（http://philoscience.iteye.com/admin/blogs/1112759）中提到了二分查找树及其改进版本AVL树（平衡二叉树）。二分查找树比较简单，但是很容易产生不平衡的问题而丧失了二分查找树的优势，AVL树规定了左右孩子树的高度差超过1则为不平衡，为了维持平衡，在插入和删除子节点后，必须进行相应的旋转。还有一种著名的红黑树，红黑树放宽了平衡的要求，从而减少了操作的次数。最后还有伸展树（splay tree，好像也有叫自组织树的），它与我们前面介绍过的自组织链表中的moveToFront策略是一样的，不过用的数据结构不再是链表，而是二叉树。这几天通过亲身实现了这几种二叉树以及调试，了解了其中的很多细节，对其思想也算是有所掌握了。

因为打算后面还要实现多种树，所以先写了一个树的虚类，要实现的功能包括有insert，remove，search以及print，当然还有析构函数。

template<class Elem, class Key, class KEComp, class EEComp> class Tree{
	protected:
		int count;
		Tree( int c=0 ){
			count = c;
		}
		virtual ~Tree(){};
	public:
		virtual bool insert( const Elem& )=0;
		//search本来应该是const成员函数的，可是后面的splaytree在search过后
		//还要进行翻转，没办法是const的，不知道在设计上应该怎么做比较好。
		virtual bool search( const Key&, Elem& ) =0;
		virtual bool remove( const Key&, Elem& ) =0;
		virtual void print() const =0;
		int size(){	return count; }
	};

二分查找树的实现：

//BSTTree.h
#ifndef BSTTREE_H
#define BSTTREE_H

template<class Elem, class Key, class KEComp, class EEComp>
class BST : public Tree<Elem, Key, KEComp, EEComp>{
	protected:
		struct BinNode{
			Elem e;
			BinNode* left;
			BinNode* right;
			BinNode( Elem ee, BinNode* l=0, BinNode* r=0 ){
				e = ee; left = l; right = r;
			}
		};
		using Tree<Elem, Key, KEComp, EEComp>::count;		
		BinNode* root;
	private:
		void printHelp( BinNode* subroot, int level ) const;
		void clear( BinNode* subroot );
	
	public:
		BST(){	root = 0; }
		~BST(){
			clear( root );
		}
		
		virtual bool search( const Key& k, Elem& e );	
		virtual bool insert( const Elem& e );		
		virtual bool remove( const Key& k, Elem& e );
				
		//it's hard to print it non recursively....
		virtual void print() const{
			if( root == 0 )
				cout<<"empty tree"<<endl;
			else	printHelp( root, 0 );
			}
	};

#include "BSTTree.cpp"
#endif

//BSTTree.cpp
template<class Elem, class Key, class KEComp, class EEComp>
void BST<Elem, Key, KEComp, EEComp>::
	printHelp( BinNode* subroot, int level ) const{
		if( subroot == 0 ){
			return;
		}
		printHelp( subroot->left, level+1 );
		for( int i=0; i<level; i++ )
			cout<<"___";
		cout<<subroot->e<<endl;
		printHelp( subroot->right, level+1 );
	}

template<class Elem, class Key, class KEComp, class EEComp>
void BST<Elem, Key, KEComp, EEComp>::
	clear( BinNode* subroot ){
		if( subroot == 0 )
			return;
		clear( subroot->left );
		clear( subroot->right );
		delete subroot;
	}

//non recursive implementation
template<class Elem, class Key, class KEComp, class EEComp>
bool BST<Elem, Key, KEComp, EEComp>::
	search( const Key& k, Elem& e ) {
		BinNode* p = root;
		while( p != 0 ){
			if( KEComp::eq( k, p->e ) ){
				e = p->e;
				return true;
			}
			if( KEComp::lt( k, p->e ) )	
				p = p->left;
			else
				p = p->right;
			}
		return false;
	}

template<class Elem, class Key, class KEComp, class EEComp>
bool BST<Elem, Key, KEComp, EEComp>::
	insert( const Elem& e ){
		BinNode* p = root, *i=0;
		while( p!=0 ){
			i = p;
			if( EEComp::lt( e, p->e ) )
				p = p->left;
			else
				p = p->right;
		}
		p = new BinNode( e );
		if( i == 0 )
			root = p;
		else{
			if( EEComp::lt( e, i->e ) )
				i->left = p;
			else i->right = p;
			}
		count++;
		return true;
	}
	
template<class Elem, class Key, class KEComp, class EEComp>
bool BST<Elem, Key, KEComp, EEComp>::
	remove( const Key& k, Elem& e ){
		BinNode* p = root, *i=0;
		while( p!=0 ){
			if( KEComp::eq( k, p->e ) )
				break;
			i = p;
			if( KEComp::lt( k, p->e ) )
				p = p->left;
			else
				p = p->right;
		}
		if( p == 0 )
			return false;
		e = p->e;
		BinNode* removeP = p;
		if( p->right != 0 ){
			removeP = p->right;
			i = p;
			while( removeP->left != 0 ){
				i = removeP;
				removeP = removeP->left;
			}
			p->e = removeP->e;
		}
		if( i == 0 )
			root = removeP->left;
		else{
			if( i->left == removeP )
				i->left = (removeP->left==0 ? removeP->right : removeP->left);
			else
				i->right = (removeP->right==0 ? removeP->left :removeP->right);
		}
		delete removeP;
		count--;
		return true;
	}

AVL树比BST在插入和删除元素的时候多了一个旋转的操作。一开始的时候说什么时候只需要旋转一次，什么时候需要旋转两次的，后来想明白了，其实大致可以用下图来表示：

因此第二种情况下必须先把C转到B的位置使祖孙三人成一条直线，然后再做一次旋转。

AVL树的结点将比BST树的结点多一个记录高度的信息，以便在插入删除的时候确定是否需要进行旋转。因为没有记录爷结点的信息，所以是用递归实现的。

//AVLTree.h
#ifndef AVLTREE_H
#define AVLTREE_H

template<class Elem, class Key, class KEComp, class EEComp>
class AVLTree : public BST<Elem, Key, KEComp, EEComp>{
	protected:
		typedef typename BST<Elem, Key, KEComp, EEComp>::BinNode BSTNode;
		using BST<Elem, Key, KEComp, EEComp>::count;
		using BST<Elem, Key, KEComp, EEComp>::root;
		struct HeightBinNode : public BSTNode{
			int height;
			HeightBinNode( Elem ee, HeightBinNode* l=NULL, HeightBinNode* r=NULL, int h=1 ):BSTNode(ee, l, r){
				height = h;
			}
		};
	private:
		//return the height of a subtree, if the subroot is null, return 0;
		int Height( HeightBinNode* t ){
			if( t == NULL )
				return 0;
			return t->height;
		}
		Key (*getKey)(const Elem& e );
		
		//insert into the left subtree of subroot's left child
		HeightBinNode* rotateL( HeightBinNode* subroot );
		//insert into the right subtree of subroot's right child
		HeightBinNode* rotateR( HeightBinNode* subroot );
		
		//return a subroot which is modified by an inserted/removed element
		HeightBinNode* insertHelp( const Elem& e, HeightBinNode* subroot );		
		HeightBinNode* removeHelp( HeightBinNode* subroot, const Key& k, HeightBinNode*& t );
						
	public:
		AVLTree( Key (*g)(const Elem& e) ):BST<Elem, Key, KEComp, EEComp>(){
			getKey = g;
		}
			
		//since it's really hard to implement insert without recursion, 
		//I decide to realize it recursively
		bool insert( const Elem& e ){
			(HeightBinNode*)root = insertHelp( e, (HeightBinNode*)root );
			if( root == NULL )
				return false;
			count++;
			return true;
		}
		
		bool remove( const Key& k, Elem& e ){
			HeightBinNode* t=0;
			root = removeHelp( (HeightBinNode*)root, k, t );
			if( t == NULL )
				return false;
			e = t->e;
			delete t;
			count--;
			return true;
		}
	};
	
#include "AVLTree.cpp"
#endif

//AVLTree.cpp

template<class Elem, class Key, class KEComp, class EEComp>
typename AVLTree<Elem, Key, KEComp, EEComp>::HeightBinNode* AVLTree<Elem, Key, KEComp, EEComp>::
	rotateL( HeightBinNode* subroot ){
		HeightBinNode* alter_root = (HeightBinNode*)subroot->left;
		HeightBinNode* leftChild = (HeightBinNode* )alter_root->left, *rightChild = (HeightBinNode*) alter_root->right;
		if( Height(leftChild)-Height(rightChild) == -1 )
			alter_root = rotateR( alter_root );
		subroot->left = (HeightBinNode*)alter_root->right;
		alter_root->right = subroot;
		leftChild = (HeightBinNode*)subroot->left; rightChild = (HeightBinNode*)subroot->right;
		subroot->height = (Height(leftChild) > Height(rightChild) ? Height(leftChild):Height(rightChild))+1;
		leftChild = (HeightBinNode*)alter_root->left; rightChild = (HeightBinNode*)alter_root->right;
		alter_root->height = (Height(leftChild) > Height(rightChild) ? Height(leftChild):Height(rightChild))+1;
		return alter_root;
	}

template<class Elem, class Key, class KEComp, class EEComp>
typename AVLTree<Elem, Key, KEComp, EEComp>::HeightBinNode* AVLTree<Elem, Key, KEComp, EEComp>::
	rotateR( HeightBinNode* subroot ){
		HeightBinNode* alter_root = (HeightBinNode*)subroot->right;
		HeightBinNode* leftChild, *rightChild;
		leftChild = (HeightBinNode*) alter_root->left;
		rightChild=(HeightBinNode*)alter_root->right;
		if( Height(leftChild)-Height(rightChild) == 1 )
			alter_root = rotateL( alter_root );
		subroot->right = alter_root->left;
		alter_root->left = subroot;
		leftChild = (HeightBinNode*)subroot->left, rightChild=(HeightBinNode*)subroot->right;
		subroot->height = (Height(leftChild)>Height(rightChild) ? Height(leftChild) : Height(rightChild))+1;
		leftChild = (HeightBinNode*)alter_root->left, rightChild = (HeightBinNode*)alter_root->right;
		alter_root->height = (Height(leftChild)>Height(rightChild) ? Height(leftChild) : Height(rightChild))+1;
		return alter_root;
	}
		
template<class Elem, class Key, class KEComp, class EEComp>
typename AVLTree<Elem, Key, KEComp, EEComp>::HeightBinNode* AVLTree<Elem, Key, KEComp, EEComp>::
	insertHelp( const Elem& e, HeightBinNode* subroot ){
		if( subroot == NULL ){
			subroot = new HeightBinNode(e);
			return subroot;
		}else{
			HeightBinNode* leftChild, *rightChild;
			leftChild = (HeightBinNode*)subroot->left;
			rightChild = (HeightBinNode*)subroot->right;
			if( EEComp::lt( e, subroot->e ) ){
				leftChild = insertHelp( e, leftChild );
				subroot->left = leftChild;
				if( Height(leftChild)-Height(rightChild) == 2 )
					subroot = rotateL( subroot );
				}else{
					rightChild = insertHelp( e, rightChild );
					subroot->right = rightChild;
					if( Height(leftChild)-Height(rightChild) == -2 )
						subroot = rotateR( subroot );
					}
			subroot->height = (Height(leftChild)>Height(rightChild) ? Height(leftChild) : Height(rightChild))+1;
			return subroot;
		}
	}

template<class Elem, class Key, class KEComp, class EEComp>
typename AVLTree<Elem, Key, KEComp, EEComp>::HeightBinNode* AVLTree<Elem, Key, KEComp, EEComp>::
	removeHelp( HeightBinNode* subroot, const Key& k, HeightBinNode*& t ){
		if( subroot == NULL )
			return NULL;
		HeightBinNode* leftChild, *rightChild;
		if( KEComp::eq( k, subroot->e ) ){
			t = subroot;
			if( subroot->right == NULL ){	
				subroot = (HeightBinNode*)subroot->left;
			}else{
				BSTNode* temp = subroot->right;
				while( temp->left != NULL )	temp = temp->left;
				Elem te;
				te = subroot->e;
				subroot->e = temp->e;
				temp->e = te;				
				subroot->right = removeHelp( (HeightBinNode*)subroot->right, getKey(temp->e), t );
				leftChild = (HeightBinNode*)subroot->left; rightChild = (HeightBinNode*)subroot->right;
				subroot->height =( Height(leftChild)>Height(rightChild) ? Height(leftChild):Height(rightChild))+1;
				}
			return subroot;
		}else{
			if( KEComp::lt( k, subroot->e ) ){
				subroot->left = removeHelp( (HeightBinNode*)subroot->left, k, t );
				leftChild = (HeightBinNode*)subroot->left; rightChild = (HeightBinNode*)subroot->right;
				if( Height(leftChild)-Height(rightChild) == -2 )
					subroot = rotateR( subroot );
				}else{
					subroot->right = removeHelp( (HeightBinNode*)subroot->right, k, t );
					leftChild = (HeightBinNode*)subroot->left; rightChild = (HeightBinNode*)subroot->right;
					if( Height(leftChild)-Height(rightChild) == 2 )
						subroot = rotateL( subroot );
				}
		}
		leftChild = (HeightBinNode*)subroot->left; rightChild = (HeightBinNode*)subroot->right;
		subroot->height = (Height(leftChild)>Height(rightChild) ? Height(leftChild) : Height(rightChild))+1;
		return subroot;
	}

AVL树用高度来识别树的平衡程度，而红黑树则是用颜色来识别树的平衡。红黑树使用红色或者黑色来标识一个结点，一棵合法的树必须满足如下规则：

（1）树根是黑色的；

（2）空结点是黑色的；

（3）红色的父节点不能有红色的孩子结点

（4）从树根到所有叶子（空结点）的黑色结点的数目必须是相等的，从树根到叶子结点的黑色结点的数目称为树的黑高度（所有的子树也同样是一棵红黑树）。

对于插入一个结点，除了根结点外，结点必须是红色的，不然的话根到经过该结点到达空叶子结点的数目必然会比其他路径的增加一，这将违反规则4；但是如果这个时候插入结点的地方的父节点也是红色的，又会违反规则3.解决的办法是重新着父结点的颜色，将不平衡点往上推，直到最后到了根结点，根结点一定为黑；或者通过旋转降低子树的高度以同时降低子树的黑高度。具体要视叔结点的颜色而定。如下图：

删除一个结点时，我们知道，如果删除的结点左右孩子都不为空的话，我们不会直接删除该结点，而是从其孩子结点中找到大于它的最小结点（或小于它的最大结点），根据这种思想递归下去，对于物理上将被删除的结点，我们可能断定，它最多只有一个不为空的孩子，而根据结黑树的特点，如果它有一个不为空的孩子，该孩子一定为红色。总结起来，删除的结点有如下的特点：

（1）该结点没有孩子结点或只有一个红色的孩子结点

（2）如果被删除的结点是红色的，它一定是一个叶子结点。

因此，根据被删除结点的情况，删除完结点后相应的调整如下：

（1）如果被删除的结点是红色的，无须做任何调整，因为它没有影响树的黑高度。

（2）如果被删除的结点是黑色的，且其有一个孩子结点。我们知道此时该孩子结点一定为红色，因此，我们可以直接将该孩子结点染成黑色的，整体的黑高度也没有发生变化。

（3）如果被删除的结点是黑色的，其孩子结点均为空（即黑色结点）。删除该结点使经过该结点的路径的黑高度减少了一，接替该结点的位置的也将是一个黑色的新结点，这个时候，跟插入一个新的结点一样，我们要通过改变着色将冲突往上移，或者通过旋转来改变高度从而改变黑高度，因此下面的讨论就不再局限于新插入的结点。

我觉得关于红黑树这篇文章讲得很详细http://www.cppblog.com/goodwin/archive/2011/08/08/152797.html。

下面是我的代码：

//RBTree.h

#ifndef RBTREE_H
#define RBTREE_H

template<class Elem, class Key, class KEComp, class EEComp>
class RBTree : public BST<Elem, Key, KEComp, EEComp>{
	protected:
		typedef enum{ BLACK,RED } Color;
		typedef typename BST<Elem, Key, KEComp, EEComp>::BinNode BSTNode;
		using BST<Elem, Key, KEComp, EEComp>::count;
		using BST<Elem, Key, KEComp, EEComp>::root;
		struct RBNode : public BSTNode{
			Color color;
			RBNode* parent;
			RBNode( Elem ee, RBNode* l=0, RBNode* r=0, RBNode* p=0, Color cc=RED ):BSTNode( ee, l, r ){
				parent = p;
				color = cc;
			}
		};
		
		void rotateL( RBNode* );
		void rotateR( RBNode* );
		void insertFixUp( RBNode* );
		void removeFixUp( RBNode* );
		/*测试用
		void printHelp( RBNode* subroot, int level ) const{
			if( subroot == 0 )
				return;
			printHelp( (RBNode*)subroot->left, level+1);
			for( int i=0; i<level; i++ )
				cout<<"___";
			if( subroot->color == BLACK )
				cout<<"("<<subroot->e<<")"<<endl;
			else
				cout<<"|"<<subroot->e<<"|"<<endl;
			printHelp( (RBNode*)subroot->right, level+1 );
		}*/
		
	public:
		RBTree(){
			//很多实现都利用了一个nilNode来做哨兵，为了利用BST的打印和删除，
			//这里没有进行这样的实现
//			nilNode = new RBNode();
//			root = nilNode;
		}
		~RBTree(){
//			delete nilNode;
		}
		bool insert( const Elem& e );
		bool remove( const Key& k, Elem& e );
		/*void print() const{
			printHelp( (RBNode*)root, 0 );
		}*/
	};

#include "RBTree.cpp"
#endif

//RBTree.cpp
template<class Elem, class Key, class KEComp, class EEComp>
bool RBTree<Elem, Key, KEComp, EEComp>::insert( const Elem& e ){
	if( root == 0 ){
		root = new RBNode( e );
		((RBNode*)root)->color = BLACK;
		count ++;
		return true;
	}
	RBNode *current=(RBNode*)root, *insertP;
	while( current != 0 ){
		insertP = current;
		if( EEComp::lt( e, current->e ) )
			current = (RBNode*)current->left;
		else
			current = (RBNode*)current->right;
		};
	RBNode* insertNode = new RBNode( e );
	insertNode->parent = insertP;
	if( EEComp::lt( e, insertP->e ) )
		insertP->left = insertNode;
	else
		insertP->right = insertNode;
	count ++;
	insertFixUp( insertNode );
}

template<class Elem, class Key, class KEComp, class EEComp>
void RBTree<Elem, Key, KEComp, EEComp>::
rotateL( RBNode* subroot ){
	if( subroot == 0 || subroot->left == 0 )
		return;
	RBNode* leftChild = (RBNode*)subroot->left;
	RBNode *rightChild = (RBNode*)leftChild->right;
	leftChild->parent = subroot->parent;
	if( subroot->parent == 0 )
		root = leftChild;
	else{
		if( subroot->parent->left == subroot )
			subroot->parent->left = leftChild;
		else subroot->parent->right = leftChild;
		}	
	leftChild->right = subroot;
	subroot->parent=leftChild;
	subroot->left = rightChild;
	if( rightChild != 0 )
		rightChild->parent = subroot;
}

template<class Elem, class Key, class KEComp, class EEComp>
void RBTree<Elem, Key, KEComp, EEComp>::
rotateR( RBNode* subroot ){
	if( subroot == 0 || subroot->right == 0 )
		return;
	RBNode* rightChild = (RBNode*)subroot->right;
	RBNode* leftChild = (RBNode*)rightChild->left;
	rightChild->parent = subroot->parent;
	if( subroot->parent == 0 )
		root = rightChild;
	else{
		if( subroot->parent->left == subroot )
			subroot->parent->left = rightChild;
		else
			subroot->parent->right = rightChild;
		}
	rightChild->left = subroot;
	subroot->parent = rightChild;
	subroot->right = leftChild;
	if( leftChild != 0 )
		leftChild->parent = subroot;
}

template<class Elem, class Key, class KEComp, class EEComp>
void RBTree<Elem, Key, KEComp, EEComp>::	
insertFixUp( RBNode* current ){
	while( current->parent != 0 && current->parent->color == RED ){
		RBNode* uncle;
		if( current->parent == current->parent->parent->left ){
			uncle = (RBNode*)current->parent->parent->right;
			if( uncle !=0 && uncle->color == RED ){
				current->parent->color = BLACK;
				uncle->color = BLACK;
				current = current->parent->parent;
				current->color = RED;
			}else{
				if( current == current->parent->right ){
					current = current->parent;
					rotateR( current );
				}
				current->parent->color = BLACK;
				current->parent->parent->color = RED;
				rotateL( current->parent->parent );
			}
		}else{
			uncle = (RBNode*)current->parent->parent->left;
			if( uncle != 0 && uncle->color == RED ){
				current->parent->color = BLACK;
				uncle->color = BLACK;
				current = current->parent->parent;
				current->color = RED;
			}else{
				if( current == current->parent->left ){
					current = current->parent;
					rotateL( current );
				}
				current->parent->color = BLACK;
				current->parent->parent->color = RED;
				rotateR( current->parent->parent );
			}
		}
	}
	((RBNode*)root)->color = BLACK;
}

template<class Elem, class Key, class KEComp, class EEComp>
bool RBTree<Elem, Key, KEComp, EEComp>::
remove( const Key& k, Elem& e ){
	RBNode* index=(RBNode*)root, *removeNode=0;
	//get the node to be removed
	while( index != 0 ){
		if( KEComp::eq( k, index->e ) ){
			e = index->e;
			if( index->right == 0 ){
				removeNode = index;
				break;
			}else{
				BSTNode* temp = index->right;
				while( temp->left != 0 )
					temp = temp->left;
				removeNode = (RBNode*)temp;
				index->e = temp->e;
				break;
			}
		}
		if( KEComp::lt( k, index->e ) )
			index = (RBNode*)index->left;
		else
			index = (RBNode*)index->right;
		}
	if( removeNode == 0 )
		return false;
	
	//没有使用哨兵的结果还是挺严重的，代码写得很不简洁。
	if( removeNode->color == RED ){		//red child is a leaf
		if( removeNode->parent->left == removeNode )
			removeNode->parent->left = 0;
		else
			removeNode->parent->right = 0;
		}else{
			if( removeNode == root ){
				root = removeNode->left;
				if( root != 0 )
					((RBNode*)root)->color = BLACK;
				}
			else{
				RBNode* child=0;
				if( removeNode->left != 0 )
					child = (RBNode*)removeNode->left;
				else
					child = (RBNode*)removeNode->right;
				RBNode* temp=0;
				if ( child == 0 ){
					temp = new RBNode(e);
					child = temp;
					child->color = BLACK;
					child->parent = removeNode->parent;
				}
				bool left;
				if( removeNode == removeNode->parent->left ){
					left = true;
					removeNode->parent->left = child;
				}
				else{
					removeNode->parent->right = child;
					left = false;
				}
				removeFixUp( child );
				if( temp != 0 ){
					if( left )
						temp->parent->left = 0;
					else
						temp->parent->right = 0;
					delete temp;
				}
			}
		}
	delete removeNode;
	count --;
	return true;
}

template<class Elem, class Key, class KEComp, class EEComp>
void RBTree<Elem, Key, KEComp, EEComp>::
removeFixUp( RBNode* current ){
	while( current != root && current->color == BLACK ){
		RBNode* uncle, *leftChild, *rightChild;
		if( current == current->parent->left ){		//left child
			uncle = (RBNode*)current->parent->right;
			//uncle is impossible to be null
			if( uncle->color == RED ){
				current->parent->color = RED;
				uncle->color = BLACK;
				rotateL( current->parent );
				uncle = (RBNode*)current->parent->right;
			}
			leftChild = (RBNode*)uncle->left;
			rightChild =(RBNode*)uncle->right;
			if( (leftChild==0||leftChild->color==BLACK) && 
				(rightChild==0 || rightChild->color==BLACK) ){
				uncle->color = RED;
				current = current->parent;
			}else{
				if( leftChild!=0 && leftChild->color == RED ){
					leftChild->color = BLACK;
					uncle->color = RED;
					rotateL( uncle );
					uncle = (RBNode*)current->parent->right;
				}
				uncle->color = current->parent->color;
				current->parent->color = BLACK;
				((RBNode*)uncle->right)->color = BLACK;
				rotateR( current->parent );
				current = (RBNode*)root;
			}
		}else{	//right child, which is symmetric with left child
			uncle = (RBNode*)current->parent->left;
			if( uncle->color == RED ){
				current->parent->color = RED;
				uncle->color = BLACK;
				rotateL( current->parent );
				uncle = (RBNode*)current->parent->left;
			}
			leftChild = (RBNode*)uncle->left;
			rightChild = (RBNode*)uncle->right;
			if( (leftChild==0 || leftChild->color==BLACK) &&
				(rightChild==0 || rightChild->color==BLACK) ){
					uncle->color = RED;
					current = current->parent;
				}else{
					if( rightChild->color == RED ){
						uncle->color = RED;
						rightChild->color = BLACK;
						rotateR( uncle );
						uncle = (RBNode*)current->parent->left;
					}
					uncle->color = current->parent->color;
					current->parent->color = BLACK;
					((RBNode*)uncle->left)->color = BLACK;
					rotateL( current->parent );
					current = (RBNode*)root;
				}
			}
		}
		current->color = BLACK;
	}

最后一种是splay树。Splay树是一种自组织树，跟MoveToFront的自组织链表一样，刚被搜索到的元素被转到树根，转的方法如下：

代码如下：

//BSTTree.h
#ifndef BSTTREE_H
#define BSTTREE_H

template<class Elem, class Key, class KEComp, class EEComp>
class BST : public Tree<Elem, Key, KEComp, EEComp>{
	protected:
		struct BinNode{
			Elem e;
			BinNode* left;
			BinNode* right;
			BinNode( Elem ee, BinNode* l=0, BinNode* r=0 ){
				e = ee; left = l; right = r;
			}
		};
		using Tree<Elem, Key, KEComp, EEComp>::count;		
		BinNode* root;
	private:
		void printHelp( BinNode* subroot, int level ) const;
		void clear( BinNode* subroot );
	
	public:
		BST(){	root = 0; }
		~BST(){
			clear( root );
		}
		
		virtual bool search( const Key& k, Elem& e );	
		virtual bool insert( const Elem& e );		
		virtual bool remove( const Key& k, Elem& e );
				
		//it's hard to print it non recursively....
		virtual void print() const{
			if( root == 0 )
				cout<<"empty tree"<<endl;
			else	printHelp( root, 0 );
			}
	};

#include "BSTTree.cpp"
#endif

//SplayTree.cpp

template<class Elem, class Key, class KEComp, class EEComp>
void SplayTree<Elem, Key, KEComp, EEComp>::
rotateL( SPNode* subroot ){
	if( subroot == 0 || subroot->left == 0 )
		return;
	SPNode* leftChild = (SPNode*)subroot->left, *rightChild = (SPNode*)leftChild->right;
	if( subroot == root )
		root = leftChild;
	else{
		if( subroot == subroot->parent->left )
			subroot->parent->left = leftChild;
		else
			subroot->parent->right = leftChild;
		}
	leftChild->parent = subroot->parent;
	leftChild->right = subroot;
	subroot->parent = leftChild;
	subroot->left = rightChild;
	if( rightChild != 0 )
		rightChild->parent = subroot;
}

template<class Elem, class Key, class KEComp, class EEComp>
void SplayTree<Elem, Key, KEComp, EEComp>::
rotateR( SPNode* subroot ){
	if( subroot == 0 || subroot->right == 0 )
		return;
	SPNode* rightChild = (SPNode*)subroot->right, *leftChild =(SPNode*)rightChild->left;
	if( subroot == root )
		root = rightChild;
	else{
		if( subroot == subroot->parent->left )
			subroot->parent->left = rightChild;
		else
			subroot->parent->right = rightChild;
		}
	rightChild->parent = subroot->parent;
	rightChild->left = subroot;
	subroot->right = leftChild;
	subroot->parent = rightChild;
	if( leftChild != 0 )
		leftChild->parent = subroot;
}

template<class Elem, class Key, class KEComp, class EEComp>
void SplayTree<Elem, Key, KEComp, EEComp>::
	splay( SPNode* from, SPNode* to ){	//rotate from under to
		if( from == 0 )
			return;
		while( from->parent != to ){
			if( from->parent->parent == to ){
				if( from == from->parent->left )
					rotateL( from->parent );
				else	rotateR( from->parent );
				}
			else{
				SPNode* p=from->parent, *g=p->parent;
				if( from == (SPNode*)p->left ){
					
					if( p == (SPNode*)g->left ){
						rotateL( g );
						rotateL( p );
					}else{
						rotateL( p );
						rotateR( g );
					}
				}else{
					if( p == (SPNode*)g->right ){
						rotateR( g );
						rotateR( p );
					}else{
						rotateR( p );
						rotateL( g );
					}
				}
			}
		}
	}

template<class Elem, class Key, class KEComp, class EEComp>
bool SplayTree<Elem, Key, KEComp, EEComp>::
	insert( const Elem& e ){
		if( root == 0 ){
			root = new SPNode( e );
			((SPNode*) root)->parent = 0;
			count ++;
			return true;
		}
		SPNode* index=(SPNode*)root, *insertP;
		while( index != 0 ){
			insertP = index;
			if( EEComp::lt( e, index->e ) )
				index = (SPNode*)index->left;
			else
				index = (SPNode*)index->right;
			}
		index = new SPNode( e );
		index->parent = insertP;
		if( EEComp::lt( e, insertP->e ) )
			insertP->left = index;
		else
			insertP->right = index;
		splay( index, 0 );
		count++;
		return true;
	}

template<class Elem, class Key, class KEComp, class EEComp>
bool SplayTree<Elem, Key, KEComp, EEComp>::
	remove( const Key& k, Elem& e ){
		SPNode* removeP = (SPNode*)root;
		SPNode* splayP;
		while( removeP != 0 ){
			if( KEComp::eq( k, removeP->e ) ){
				e = removeP->e;
				splayP = removeP->parent;
				if( removeP->right == 0 && splayP !=0 ){
					if( removeP == splayP->left )
						splayP->left = removeP->left;
					else
						splayP->right = removeP->left;
					if( removeP->left != 0 )
						((SPNode*)removeP->left)->parent = splayP;
					}else{
					SPNode* temp = (SPNode*)removeP->right;
					while( temp->left != 0 )	temp = (SPNode*)temp->left;
					temp->parent->left = temp->right;
					if( temp->right != 0 )
						((SPNode*)temp->right)->parent = temp->parent;
					removeP->e = temp->e;
					removeP = temp;
				}
			delete removeP;
			splay( splayP, 0 );
			count--;
			return true;
		}else{
			if( KEComp::lt( k, removeP->e ) )
				removeP = (SPNode*)removeP->left;
			else
				removeP = (SPNode*)removeP->right;
			}
		}
		return false;
	}

template<class Elem, class Key, class KEComp, class EEComp>
bool SplayTree<Elem, Key, KEComp, EEComp>::
	search( const Key& k, Elem& e ) const{
		SPNode* searchP = (SPNode*)root;
		while( searchP != 0 ){
			if( KEComp::eq( k, searchP->e ) ){
				e = searchP->e;
				splay( searchP );
				return true;
			}else{
				if( KEComp::lt( k, searchP->e ) )
					searchP = searchP->left;
				else
					searchP = searchP->right;
				}
			}
		return false;
	}

基本就是这些了。接下来再实现一下其他类型的树，呵呵。