数据结构 若一 avl树的二叉树叶子结点个数数是21，则该树的高度至多是多少
点击联系发帖人
时间：2017-07-09 05:16
数据结构 -- 二叉树(BST, AVLTree, RBTree, SplayTree) - 茅屋 - ITeye技术网站
博客分类：
本文章已收录于：
在《基于树的索引结构介绍》（）中提到了二分查找树及其改进版本AVL树（平衡二叉树）。二分查找树比较简单，但是很容易产生不平衡的问题而丧失了二分查找树的优势，AVL树规定了左右孩子树的高度差超过1则为不平衡，为了维持平衡，在插入和删除子节点后，必须进行相应的旋转。还有一种著名的红黑树，红黑树放宽了平衡的要求，从而减少了操作的次数。最后还有伸展树（splay tree，好像也有叫自组织树的），它与我们前面介绍过的自组织链表中的moveToFront策略是一样的，不过用的数据结构不再是链表，而是二叉树。这几天通过亲身实现了这几种二叉树以及调试，了解了其中的很多细节，对其思想也算是有所掌握了。
因为打算后面还要实现多种树，所以先写了一个树的虚类，要实现的功能包括有insert，remove，search以及print，当然还有析构函数。
template&class Elem, class Key, class KEComp, class EEComp& class Tree{
protected:
Tree( int c=0 ){
virtual ~Tree(){};
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(){
二分查找树的实现：
//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{
BinNode( Elem ee, BinNode* l=0, BinNode* r=0 ){
e = left = right =
using Tree&Elem, Key, KEComp, EEComp&::
void printHelp( BinNode* subroot, int level )
void clear( BinNode* subroot );
BST(){ root = 0; }
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"&&
else printHelp( root, 0 );
#include "BSTTree.cpp"
//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 ){
printHelp( subroot-&left, level+1 );
for( int i=0; i& i++ )
cout&&"___";
cout&&subroot-&e&&
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 )
clear( subroot-&left );
clear( subroot-&right );
//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 =
while( p != 0 ){
if( KEComp::eq( k, p-&e ) ){
if( KEComp::lt( k, p-&e ) )
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 ){
if( EEComp::lt( e, p-&e ) )
p = new BinNode( e );
if( i == 0 )
if( EEComp::lt( e, i-&e ) )
else i-&right =
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 ) )
if( KEComp::lt( k, p-&e ) )
if( p == 0 )
BinNode* removeP =
if( p-&right != 0 ){
removeP = p-&
while( removeP-&left != 0 ){
i = removeP;
removeP = removeP-&
p-&e = removeP-&e;
if( i == 0 )
root = removeP-&
if( i-&left == removeP )
i-&left = (removeP-&left==0 ? removeP-&right : removeP-&left);
i-&right = (removeP-&right==0 ? removeP-&left :removeP-&right);
delete removeP;
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 BSTN
using BST&Elem, Key, KEComp, EEComp&::
using BST&Elem, Key, KEComp, EEComp&::
struct HeightBinNode : public BSTNode{
HeightBinNode( Elem ee, HeightBinNode* l=NULL, HeightBinNode* r=NULL, int h=1 ):BSTNode(ee, l, r){
//return the height of a subtree, if the subroot is null, return 0;
int Height( HeightBinNode* t ){
if( t == NULL )
return t-&
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 );
AVLTree( Key (*g)(const Elem& e) ):BST&Elem, Key, KEComp, EEComp&(){
//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 )
bool remove( const Key& k, Elem& e ){
HeightBinNode* t=0;
root = removeHelp( (HeightBinNode*)root, k, t );
if( t == NULL )
#include "AVLTree.cpp"
//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-&
HeightBinNode* leftChild = (HeightBinNode* )alter_root-&left, *rightChild = (HeightBinNode*) alter_root-&
if( Height(leftChild)-Height(rightChild) == -1 )
alter_root = rotateR( alter_root );
subroot-&left = (HeightBinNode*)alter_root-&
alter_root-&right =
leftChild = (HeightBinNode*)subroot-& rightChild = (HeightBinNode*)subroot-&
subroot-&height = (Height(leftChild) & Height(rightChild) ? Height(leftChild):Height(rightChild))+1;
leftChild = (HeightBinNode*)alter_root-& rightChild = (HeightBinNode*)alter_root-&
alter_root-&height = (Height(leftChild) & Height(rightChild) ? Height(leftChild):Height(rightChild))+1;
return alter_
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-&
HeightBinNode* leftChild, *rightC
leftChild = (HeightBinNode*) alter_root-&
rightChild=(HeightBinNode*)alter_root-&
if( Height(leftChild)-Height(rightChild) == 1 )
alter_root = rotateL( alter_root );
subroot-&right = alter_root-&
alter_root-&left =
leftChild = (HeightBinNode*)subroot-&left, rightChild=(HeightBinNode*)subroot-&
subroot-&height = (Height(leftChild)&Height(rightChild) ? Height(leftChild) : Height(rightChild))+1;
leftChild = (HeightBinNode*)alter_root-&left, rightChild = (HeightBinNode*)alter_root-&
alter_root-&height = (Height(leftChild)&Height(rightChild) ? Height(leftChild) : Height(rightChild))+1;
return alter_
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);
HeightBinNode* leftChild, *rightC
leftChild = (HeightBinNode*)subroot-&
rightChild = (HeightBinNode*)subroot-&
if( EEComp::lt( e, subroot-&e ) ){
leftChild = insertHelp( e, leftChild );
subroot-&left = leftC
if( Height(leftChild)-Height(rightChild) == 2 )
subroot = rotateL( subroot );
rightChild = insertHelp( e, rightChild );
subroot-&right = rightC
if( Height(leftChild)-Height(rightChild) == -2 )
subroot = rotateR( subroot );
subroot-&height = (Height(leftChild)&Height(rightChild) ? Height(leftChild) : Height(rightChild))+1;
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, *rightC
if( KEComp::eq( k, subroot-&e ) ){
if( subroot-&right == NULL ){
subroot = (HeightBinNode*)subroot-&
BSTNode* temp = subroot-&
while( temp-&left != NULL ) temp = temp-&
te = subroot-&e;
subroot-&e = temp-&e;
subroot-&right = removeHelp( (HeightBinNode*)subroot-&right, getKey(temp-&e), t );
leftChild = (HeightBinNode*)subroot-& rightChild = (HeightBinNode*)subroot-&
subroot-&height =( Height(leftChild)&Height(rightChild) ? Height(leftChild):Height(rightChild))+1;
if( KEComp::lt( k, subroot-&e ) ){
subroot-&left = removeHelp( (HeightBinNode*)subroot-&left, k, t );
leftChild = (HeightBinNode*)subroot-& rightChild = (HeightBinNode*)subroot-&
if( Height(leftChild)-Height(rightChild) == -2 )
subroot = rotateR( subroot );
subroot-&right = removeHelp( (HeightBinNode*)subroot-&right, k, t );
leftChild = (HeightBinNode*)subroot-& rightChild = (HeightBinNode*)subroot-&
if( Height(leftChild)-Height(rightChild) == 2 )
subroot = rotateL( subroot );
leftChild = (HeightBinNode*)subroot-& rightChild = (HeightBinNode*)subroot-&
subroot-&height = (Height(leftChild)&Height(rightChild) ? Height(leftChild) : Height(rightChild))+1;
AVL树用高度来识别树的平衡程度，而红黑树则是用颜色来识别树的平衡。红黑树使用红色或者黑色来标识一个结点，一棵合法的树必须满足如下规则：
（1）树根是黑色的；
（2）空结点是黑色的；
（3）红色的父节点不能有红色的孩子结点
（4）从树根到所有叶子（空结点）的黑色结点的数目必须是相等的，从树根到叶子结点的黑色结点的数目称为树的黑高度（所有的子树也同样是一棵红黑树）。
对于插入一个结点，除了根结点外，结点必须是红色的，不然的话根到经过该结点到达空叶子结点的数目必然会比其他路径的增加一，这将违反规则4；但是如果这个时候插入结点的地方的父节点也是红色的，又会违反规则3.解决的办法是重新着父结点的颜色，将不平衡点往上推，直到最后到了根结点，根结点一定为黑；或者通过旋转降低子树的高度以同时降低子树的黑高度。具体要视叔结点的颜色而定。如下图：删除一个结点时，我们知道，如果删除的结点左右孩子都不为空的话，我们不会直接删除该结点，而是从其孩子结点中找到大于它的最小结点（或小于它的最大结点），根据这种思想递归下去，对于物理上将被删除的结点，我们可能断定，它最多只有一个不为空的孩子，而根据结黑树的特点，如果它有一个不为空的孩子，该孩子一定为红色。总结起来，删除的结点有如下的特点：
（1）该结点没有孩子结点或只有一个红色的孩子结点
（2）如果被删除的结点是红色的，它一定是一个叶子结点。
因此，根据被删除结点的情况，删除完结点后相应的调整如下：
（1）如果被删除的结点是红色的，无须做任何调整，因为它没有影响树的黑高度。
（2）如果被删除的结点是黑色的，且其有一个孩子结点。我们知道此时该孩子结点一定为红色，因此，我们可以直接将该孩子结点染成黑色的，整体的黑高度也没有发生变化。
（3）如果被删除的结点是黑色的，其孩子结点均为空（即黑色结点）。删除该结点使经过该结点的路径的黑高度减少了一，接替该结点的位置的也将是一个黑色的新结点，这个时候，跟插入一个新的结点一样，我们要通过改变着色将冲突往上移，或者通过旋转来改变高度从而改变黑高度，因此下面的讨论就不再局限于新插入的结点。
我觉得关于红黑树这篇文章讲得很详细。
下面是我的代码：
//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 } C
typedef typename BST&Elem, Key, KEComp, EEComp&::BinNode BSTN
using BST&Elem, Key, KEComp, EEComp&::
using BST&Elem, Key, KEComp, EEComp&::
struct RBNode : public BSTNode{
RBNode( Elem ee, RBNode* l=0, RBNode* r=0, RBNode* p=0, Color cc=RED ):BSTNode( ee, l, r ){
void rotateL( RBNode* );
void rotateR( RBNode* );
void insertFixUp( RBNode* );
void removeFixUp( RBNode* );
void printHelp( RBNode* subroot, int level ) const{
if( subroot == 0 )
printHelp( (RBNode*)subroot-&left, level+1);
for( int i=0; i& i++ )
cout&&"___";
if( subroot-&color == BLACK )
cout&&"("&&subroot-&e&&")"&&
cout&&"|"&&subroot-&e&&"|"&&
printHelp( (RBNode*)subroot-&right, level+1 );
//很多实现都利用了一个nilNode来做哨兵，为了利用BST的打印和删除，
//这里没有进行这样的实现
nilNode = new RBNode();
root = nilN
~RBTree(){
delete nilN
bool insert( const Elem& e );
bool remove( const Key& k, Elem& e );
/*void print() const{
printHelp( (RBNode*)root, 0 );
#include "RBTree.cpp"
//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;
RBNode *current=(RBNode*)root, *insertP;
while( current != 0 ){
if( EEComp::lt( e, current-&e ) )
current = (RBNode*)current-&
current = (RBNode*)current-&
RBNode* insertNode = new RBNode( e );
insertNode-&parent = insertP;
if( EEComp::lt( e, insertP-&e ) )
insertP-&left = insertN
insertP-&right = insertN
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 )
RBNode* leftChild = (RBNode*)subroot-&
RBNode *rightChild = (RBNode*)leftChild-&
leftChild-&parent = subroot-&
if( subroot-&parent == 0 )
root = leftC
if( subroot-&parent-&left == subroot )
subroot-&parent-&left = leftC
else subroot-&parent-&right = leftC
leftChild-&right =
subroot-&parent=leftC
subroot-&left = rightC
if( rightChild != 0 )
rightChild-&parent =
template&class Elem, class Key, class KEComp, class EEComp&
void RBTree&Elem, Key, KEComp, EEComp&::
rotateR( RBNode* subroot ){
if( subroot == 0 || subroot-&right == 0 )
RBNode* rightChild = (RBNode*)subroot-&
RBNode* leftChild = (RBNode*)rightChild-&
rightChild-&parent = subroot-&
if( subroot-&parent == 0 )
root = rightC
if( subroot-&parent-&left == subroot )
subroot-&parent-&left = rightC
subroot-&parent-&right = rightC
rightChild-&left =
subroot-&parent = rightC
subroot-&right = leftC
if( leftChild != 0 )
leftChild-&parent =
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 ){
if( current-&parent == current-&parent-&parent-&left ){
uncle = (RBNode*)current-&parent-&parent-&
if( uncle !=0 && uncle-&color == RED ){
current-&parent-&color = BLACK;
uncle-&color = BLACK;
current = current-&parent-&
current-&color = RED;
if( current == current-&parent-&right ){
current = current-&
rotateR( current );
current-&parent-&color = BLACK;
current-&parent-&parent-&color = RED;
rotateL( current-&parent-&parent );
uncle = (RBNode*)current-&parent-&parent-&
if( uncle != 0 && uncle-&color == RED ){
current-&parent-&color = BLACK;
uncle-&color = BLACK;
current = current-&parent-&
current-&color = RED;
if( current == current-&parent-&left ){
current = current-&
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 =
BSTNode* temp = index-&
while( temp-&left != 0 )
temp = temp-&
removeNode = (RBNode*)
index-&e = temp-&e;
if( KEComp::lt( k, index-&e ) )
index = (RBNode*)index-&
index = (RBNode*)index-&
if( removeNode == 0 )
//没有使用哨兵的结果还是挺严重的，代码写得很不简洁。
if( removeNode-&color == RED ){
//red child is a leaf
if( removeNode-&parent-&left == removeNode )
removeNode-&parent-&left = 0;
removeNode-&parent-&right = 0;
if( removeNode == root ){
root = removeNode-&
if( root != 0 )
((RBNode*)root)-&color = BLACK;
RBNode* child=0;
if( removeNode-&left != 0 )
child = (RBNode*)removeNode-&
child = (RBNode*)removeNode-&
RBNode* temp=0;
if ( child == 0 ){
temp = new RBNode(e);
child-&color = BLACK;
child-&parent = removeNode-&
if( removeNode == removeNode-&parent-&left ){
removeNode-&parent-&left =
removeNode-&parent-&right =
removeFixUp( child );
if( temp != 0 ){
if( left )
temp-&parent-&left = 0;
temp-&parent-&right = 0;
delete removeN
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, *rightC
if( current == current-&parent-&left ){
//left child
uncle = (RBNode*)current-&parent-&
//uncle is impossible to be null
if( uncle-&color == RED ){
current-&parent-&color = RED;
uncle-&color = BLACK;
rotateL( current-&parent );
uncle = (RBNode*)current-&parent-&
leftChild = (RBNode*)uncle-&
rightChild =(RBNode*)uncle-&
if( (leftChild==0||leftChild-&color==BLACK) &&
(rightChild==0 || rightChild-&color==BLACK) ){
uncle-&color = RED;
current = current-&
if( leftChild!=0 && leftChild-&color == RED ){
leftChild-&color = BLACK;
uncle-&color = RED;
rotateL( uncle );
uncle = (RBNode*)current-&parent-&
uncle-&color = current-&parent-&
current-&parent-&color = BLACK;
((RBNode*)uncle-&right)-&color = BLACK;
rotateR( current-&parent );
current = (RBNode*)
}else{ //right child, which is symmetric with left child
uncle = (RBNode*)current-&parent-&
if( uncle-&color == RED ){
current-&parent-&color = RED;
uncle-&color = BLACK;
rotateL( current-&parent );
uncle = (RBNode*)current-&parent-&
leftChild = (RBNode*)uncle-&
rightChild = (RBNode*)uncle-&
if( (leftChild==0 || leftChild-&color==BLACK) &&
(rightChild==0 || rightChild-&color==BLACK) ){
uncle-&color = RED;
current = current-&
if( rightChild-&color == RED ){
uncle-&color = RED;
rightChild-&color = BLACK;
rotateR( uncle );
uncle = (RBNode*)current-&parent-&
uncle-&color = current-&parent-&
current-&parent-&color = BLACK;
((RBNode*)uncle-&left)-&color = BLACK;
rotateL( current-&parent );
current = (RBNode*)
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{
BinNode( Elem ee, BinNode* l=0, BinNode* r=0 ){
e = left = right =
using Tree&Elem, Key, KEComp, EEComp&::
void printHelp( BinNode* subroot, int level )
void clear( BinNode* subroot );
BST(){ root = 0; }
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"&&
else printHelp( root, 0 );
#include "BSTTree.cpp"
//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 )
SPNode* leftChild = (SPNode*)subroot-&left, *rightChild = (SPNode*)leftChild-&
if( subroot == root )
root = leftC
if( subroot == subroot-&parent-&left )
subroot-&parent-&left = leftC
subroot-&parent-&right = leftC
leftChild-&parent = subroot-&
leftChild-&right =
subroot-&parent = leftC
subroot-&left = rightC
if( rightChild != 0 )
rightChild-&parent =
template&class Elem, class Key, class KEComp, class EEComp&
void SplayTree&Elem, Key, KEComp, EEComp&::
rotateR( SPNode* subroot ){
if( subroot == 0 || subroot-&right == 0 )
SPNode* rightChild = (SPNode*)subroot-&right, *leftChild =(SPNode*)rightChild-&
if( subroot == root )
root = rightC
if( subroot == subroot-&parent-&left )
subroot-&parent-&left = rightC
subroot-&parent-&right = rightC
rightChild-&parent = subroot-&
rightChild-&left =
subroot-&right = leftC
subroot-&parent = rightC
if( leftChild != 0 )
leftChild-&parent =
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 )
while( from-&parent != to ){
if( from-&parent-&parent == to ){
if( from == from-&parent-&left )
rotateL( from-&parent );
else rotateR( from-&parent );
SPNode* p=from-&parent, *g=p-&
if( from == (SPNode*)p-&left ){
if( p == (SPNode*)g-&left ){
rotateL( g );
rotateL( p );
rotateL( p );
rotateR( g );
if( p == (SPNode*)g-&right ){
rotateR( g );
rotateR( p );
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;
SPNode* index=(SPNode*)root, *insertP;
while( index != 0 ){
if( EEComp::lt( e, index-&e ) )
index = (SPNode*)index-&
index = (SPNode*)index-&
index = new SPNode( e );
index-&parent = insertP;
if( EEComp::lt( e, insertP-&e ) )
insertP-&left =
insertP-&right =
splay( index, 0 );
template&class Elem, class Key, class KEComp, class EEComp&
bool SplayTree&Elem, Key, KEComp, EEComp&::
remove( const Key& k, Elem& e ){
SPNode* removeP = (SPNode*)
SPNode* splayP;
while( removeP != 0 ){
if( KEComp::eq( k, removeP-&e ) ){
e = removeP-&e;
splayP = removeP-&
if( removeP-&right == 0 && splayP !=0 ){
if( removeP == splayP-&left )
splayP-&left = removeP-&
splayP-&right = removeP-&
if( removeP-&left != 0 )
((SPNode*)removeP-&left)-&parent = splayP;
SPNode* temp = (SPNode*)removeP-&
while( temp-&left != 0 ) temp = (SPNode*)temp-&
temp-&parent-&left = temp-&
if( temp-&right != 0 )
((SPNode*)temp-&right)-&parent = temp-&
removeP-&e = temp-&e;
delete removeP;
splay( splayP, 0 );
if( KEComp::lt( k, removeP-&e ) )
removeP = (SPNode*)removeP-&
removeP = (SPNode*)removeP-&
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*)
while( searchP != 0 ){
if( KEComp::eq( k, searchP-&e ) ){
e = searchP-&e;
splay( searchP );
if( KEComp::lt( k, searchP-&e ) )
searchP = searchP-&
searchP = searchP-&
基本就是这些了。接下来再实现一下其他类型的树，呵呵。
浏览: 98332 次
来自: 广州
浏览量：9061
chenxun 写道lz这么辛苦我也是醉了 ...
lz这么辛苦我也是醉了作为一名oier我说有一个算法叫做dan ...
lz很厉害,现在该是毕业了吧
呵呵 肯踏實的學東西已經很不錯了。畢業了工作之後，你就會發現個 ...
您好，提到的各种资料都有看过，也提到过思路，但对于具体操作还是 ...}
博客分类：
本文章已收录于：
在《基于树的索引结构介绍》（）中提到了二分查找树及其改进版本AVL树（平衡二叉树）。二分查找树比较简单，但是很容易产生不平衡的问题而丧失了二分查找树的优势，AVL树规定了左右孩子树的高度差超过1则为不平衡，为了维持平衡，在插入和删除子节点后，必须进行相应的旋转。还有一种著名的红黑树，红黑树放宽了平衡的要求，从而减少了操作的次数。最后还有伸展树（splay tree，好像也有叫自组织树的），它与我们前面介绍过的自组织链表中的moveToFront策略是一样的，不过用的数据结构不再是链表，而是二叉树。这几天通过亲身实现了这几种二叉树以及调试，了解了其中的很多细节，对其思想也算是有所掌握了。
因为打算后面还要实现多种树，所以先写了一个树的虚类，要实现的功能包括有insert，remove，search以及print，当然还有析构函数。
template&class Elem, class Key, class KEComp, class EEComp& class Tree{
protected:
Tree( int c=0 ){
virtual ~Tree(){};
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(){
二分查找树的实现：
//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{
BinNode( Elem ee, BinNode* l=0, BinNode* r=0 ){
e = left = right =
using Tree&Elem, Key, KEComp, EEComp&::
void printHelp( BinNode* subroot, int level )
void clear( BinNode* subroot );
BST(){ root = 0; }
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"&&
else printHelp( root, 0 );
#include "BSTTree.cpp"
//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 ){
printHelp( subroot-&left, level+1 );
for( int i=0; i& i++ )
cout&&"___";
cout&&subroot-&e&&
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 )
clear( subroot-&left );
clear( subroot-&right );
//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 =
while( p != 0 ){
if( KEComp::eq( k, p-&e ) ){
if( KEComp::lt( k, p-&e ) )
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 ){
if( EEComp::lt( e, p-&e ) )
p = new BinNode( e );
if( i == 0 )
if( EEComp::lt( e, i-&e ) )
else i-&right =
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 ) )
if( KEComp::lt( k, p-&e ) )
if( p == 0 )
BinNode* removeP =
if( p-&right != 0 ){
removeP = p-&
while( removeP-&left != 0 ){
i = removeP;
removeP = removeP-&
p-&e = removeP-&e;
if( i == 0 )
root = removeP-&
if( i-&left == removeP )
i-&left = (removeP-&left==0 ? removeP-&right : removeP-&left);
i-&right = (removeP-&right==0 ? removeP-&left :removeP-&right);
delete removeP;
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 BSTN
using BST&Elem, Key, KEComp, EEComp&::
using BST&Elem, Key, KEComp, EEComp&::
struct HeightBinNode : public BSTNode{
HeightBinNode( Elem ee, HeightBinNode* l=NULL, HeightBinNode* r=NULL, int h=1 ):BSTNode(ee, l, r){
//return the height of a subtree, if the subroot is null, return 0;
int Height( HeightBinNode* t ){
if( t == NULL )
return t-&
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 );
AVLTree( Key (*g)(const Elem& e) ):BST&Elem, Key, KEComp, EEComp&(){
//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 )
bool remove( const Key& k, Elem& e ){
HeightBinNode* t=0;
root = removeHelp( (HeightBinNode*)root, k, t );
if( t == NULL )
#include "AVLTree.cpp"
//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-&
HeightBinNode* leftChild = (HeightBinNode* )alter_root-&left, *rightChild = (HeightBinNode*) alter_root-&
if( Height(leftChild)-Height(rightChild) == -1 )
alter_root = rotateR( alter_root );
subroot-&left = (HeightBinNode*)alter_root-&
alter_root-&right =
leftChild = (HeightBinNode*)subroot-& rightChild = (HeightBinNode*)subroot-&
subroot-&height = (Height(leftChild) & Height(rightChild) ? Height(leftChild):Height(rightChild))+1;
leftChild = (HeightBinNode*)alter_root-& rightChild = (HeightBinNode*)alter_root-&
alter_root-&height = (Height(leftChild) & Height(rightChild) ? Height(leftChild):Height(rightChild))+1;
return alter_
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-&
HeightBinNode* leftChild, *rightC
leftChild = (HeightBinNode*) alter_root-&
rightChild=(HeightBinNode*)alter_root-&
if( Height(leftChild)-Height(rightChild) == 1 )
alter_root = rotateL( alter_root );
subroot-&right = alter_root-&
alter_root-&left =
leftChild = (HeightBinNode*)subroot-&left, rightChild=(HeightBinNode*)subroot-&
subroot-&height = (Height(leftChild)&Height(rightChild) ? Height(leftChild) : Height(rightChild))+1;
leftChild = (HeightBinNode*)alter_root-&left, rightChild = (HeightBinNode*)alter_root-&
alter_root-&height = (Height(leftChild)&Height(rightChild) ? Height(leftChild) : Height(rightChild))+1;
return alter_
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);
HeightBinNode* leftChild, *rightC
leftChild = (HeightBinNode*)subroot-&
rightChild = (HeightBinNode*)subroot-&
if( EEComp::lt( e, subroot-&e ) ){
leftChild = insertHelp( e, leftChild );
subroot-&left = leftC
if( Height(leftChild)-Height(rightChild) == 2 )
subroot = rotateL( subroot );
rightChild = insertHelp( e, rightChild );
subroot-&right = rightC
if( Height(leftChild)-Height(rightChild) == -2 )
subroot = rotateR( subroot );
subroot-&height = (Height(leftChild)&Height(rightChild) ? Height(leftChild) : Height(rightChild))+1;
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, *rightC
if( KEComp::eq( k, subroot-&e ) ){
if( subroot-&right == NULL ){
subroot = (HeightBinNode*)subroot-&
BSTNode* temp = subroot-&
while( temp-&left != NULL ) temp = temp-&
te = subroot-&e;
subroot-&e = temp-&e;
subroot-&right = removeHelp( (HeightBinNode*)subroot-&right, getKey(temp-&e), t );
leftChild = (HeightBinNode*)subroot-& rightChild = (HeightBinNode*)subroot-&
subroot-&height =( Height(leftChild)&Height(rightChild) ? Height(leftChild):Height(rightChild))+1;
if( KEComp::lt( k, subroot-&e ) ){
subroot-&left = removeHelp( (HeightBinNode*)subroot-&left, k, t );
leftChild = (HeightBinNode*)subroot-& rightChild = (HeightBinNode*)subroot-&
if( Height(leftChild)-Height(rightChild) == -2 )
subroot = rotateR( subroot );
subroot-&right = removeHelp( (HeightBinNode*)subroot-&right, k, t );
leftChild = (HeightBinNode*)subroot-& rightChild = (HeightBinNode*)subroot-&
if( Height(leftChild)-Height(rightChild) == 2 )
subroot = rotateL( subroot );
leftChild = (HeightBinNode*)subroot-& rightChild = (HeightBinNode*)subroot-&
subroot-&height = (Height(leftChild)&Height(rightChild) ? Height(leftChild) : Height(rightChild))+1;
AVL树用高度来识别树的平衡程度，而红黑树则是用颜色来识别树的平衡。红黑树使用红色或者黑色来标识一个结点，一棵合法的树必须满足如下规则：
（1）树根是黑色的；
（2）空结点是黑色的；
（3）红色的父节点不能有红色的孩子结点
（4）从树根到所有叶子（空结点）的黑色结点的数目必须是相等的，从树根到叶子结点的黑色结点的数目称为树的黑高度（所有的子树也同样是一棵红黑树）。
对于插入一个结点，除了根结点外，结点必须是红色的，不然的话根到经过该结点到达空叶子结点的数目必然会比其他路径的增加一，这将违反规则4；但是如果这个时候插入结点的地方的父节点也是红色的，又会违反规则3.解决的办法是重新着父结点的颜色，将不平衡点往上推，直到最后到了根结点，根结点一定为黑；或者通过旋转降低子树的高度以同时降低子树的黑高度。具体要视叔结点的颜色而定。如下图：删除一个结点时，我们知道，如果删除的结点左右孩子都不为空的话，我们不会直接删除该结点，而是从其孩子结点中找到大于它的最小结点（或小于它的最大结点），根据这种思想递归下去，对于物理上将被删除的结点，我们可能断定，它最多只有一个不为空的孩子，而根据结黑树的特点，如果它有一个不为空的孩子，该孩子一定为红色。总结起来，删除的结点有如下的特点：
（1）该结点没有孩子结点或只有一个红色的孩子结点
（2）如果被删除的结点是红色的，它一定是一个叶子结点。
因此，根据被删除结点的情况，删除完结点后相应的调整如下：
（1）如果被删除的结点是红色的，无须做任何调整，因为它没有影响树的黑高度。
（2）如果被删除的结点是黑色的，且其有一个孩子结点。我们知道此时该孩子结点一定为红色，因此，我们可以直接将该孩子结点染成黑色的，整体的黑高度也没有发生变化。
（3）如果被删除的结点是黑色的，其孩子结点均为空（即黑色结点）。删除该结点使经过该结点的路径的黑高度减少了一，接替该结点的位置的也将是一个黑色的新结点，这个时候，跟插入一个新的结点一样，我们要通过改变着色将冲突往上移，或者通过旋转来改变高度从而改变黑高度，因此下面的讨论就不再局限于新插入的结点。
我觉得关于红黑树这篇文章讲得很详细。
下面是我的代码：
//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 } C
typedef typename BST&Elem, Key, KEComp, EEComp&::BinNode BSTN
using BST&Elem, Key, KEComp, EEComp&::
using BST&Elem, Key, KEComp, EEComp&::
struct RBNode : public BSTNode{
RBNode( Elem ee, RBNode* l=0, RBNode* r=0, RBNode* p=0, Color cc=RED ):BSTNode( ee, l, r ){
void rotateL( RBNode* );
void rotateR( RBNode* );
void insertFixUp( RBNode* );
void removeFixUp( RBNode* );
void printHelp( RBNode* subroot, int level ) const{
if( subroot == 0 )
printHelp( (RBNode*)subroot-&left, level+1);
for( int i=0; i& i++ )
cout&&"___";
if( subroot-&color == BLACK )
cout&&"("&&subroot-&e&&")"&&
cout&&"|"&&subroot-&e&&"|"&&
printHelp( (RBNode*)subroot-&right, level+1 );
//很多实现都利用了一个nilNode来做哨兵，为了利用BST的打印和删除，
//这里没有进行这样的实现
nilNode = new RBNode();
root = nilN
~RBTree(){
delete nilN
bool insert( const Elem& e );
bool remove( const Key& k, Elem& e );
/*void print() const{
printHelp( (RBNode*)root, 0 );
#include "RBTree.cpp"
//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;
RBNode *current=(RBNode*)root, *insertP;
while( current != 0 ){
if( EEComp::lt( e, current-&e ) )
current = (RBNode*)current-&
current = (RBNode*)current-&
RBNode* insertNode = new RBNode( e );
insertNode-&parent = insertP;
if( EEComp::lt( e, insertP-&e ) )
insertP-&left = insertN
insertP-&right = insertN
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 )
RBNode* leftChild = (RBNode*)subroot-&
RBNode *rightChild = (RBNode*)leftChild-&
leftChild-&parent = subroot-&
if( subroot-&parent == 0 )
root = leftC
if( subroot-&parent-&left == subroot )
subroot-&parent-&left = leftC
else subroot-&parent-&right = leftC
leftChild-&right =
subroot-&parent=leftC
subroot-&left = rightC
if( rightChild != 0 )
rightChild-&parent =
template&class Elem, class Key, class KEComp, class EEComp&
void RBTree&Elem, Key, KEComp, EEComp&::
rotateR( RBNode* subroot ){
if( subroot == 0 || subroot-&right == 0 )
RBNode* rightChild = (RBNode*)subroot-&
RBNode* leftChild = (RBNode*)rightChild-&
rightChild-&parent = subroot-&
if( subroot-&parent == 0 )
root = rightC
if( subroot-&parent-&left == subroot )
subroot-&parent-&left = rightC
subroot-&parent-&right = rightC
rightChild-&left =
subroot-&parent = rightC
subroot-&right = leftC
if( leftChild != 0 )
leftChild-&parent =
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 ){
if( current-&parent == current-&parent-&parent-&left ){
uncle = (RBNode*)current-&parent-&parent-&
if( uncle !=0 && uncle-&color == RED ){
current-&parent-&color = BLACK;
uncle-&color = BLACK;
current = current-&parent-&
current-&color = RED;
if( current == current-&parent-&right ){
current = current-&
rotateR( current );
current-&parent-&color = BLACK;
current-&parent-&parent-&color = RED;
rotateL( current-&parent-&parent );
uncle = (RBNode*)current-&parent-&parent-&
if( uncle != 0 && uncle-&color == RED ){
current-&parent-&color = BLACK;
uncle-&color = BLACK;
current = current-&parent-&
current-&color = RED;
if( current == current-&parent-&left ){
current = current-&
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 =
BSTNode* temp = index-&
while( temp-&left != 0 )
temp = temp-&
removeNode = (RBNode*)
index-&e = temp-&e;
if( KEComp::lt( k, index-&e ) )
index = (RBNode*)index-&
index = (RBNode*)index-&
if( removeNode == 0 )
//没有使用哨兵的结果还是挺严重的，代码写得很不简洁。
if( removeNode-&color == RED ){
//red child is a leaf
if( removeNode-&parent-&left == removeNode )
removeNode-&parent-&left = 0;
removeNode-&parent-&right = 0;
if( removeNode == root ){
root = removeNode-&
if( root != 0 )
((RBNode*)root)-&color = BLACK;
RBNode* child=0;
if( removeNode-&left != 0 )
child = (RBNode*)removeNode-&
child = (RBNode*)removeNode-&
RBNode* temp=0;
if ( child == 0 ){
temp = new RBNode(e);
child-&color = BLACK;
child-&parent = removeNode-&
if( removeNode == removeNode-&parent-&left ){
removeNode-&parent-&left =
removeNode-&parent-&right =
removeFixUp( child );
if( temp != 0 ){
if( left )
temp-&parent-&left = 0;
temp-&parent-&right = 0;
delete removeN
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, *rightC
if( current == current-&parent-&left ){
//left child
uncle = (RBNode*)current-&parent-&
//uncle is impossible to be null
if( uncle-&color == RED ){
current-&parent-&color = RED;
uncle-&color = BLACK;
rotateL( current-&parent );
uncle = (RBNode*)current-&parent-&
leftChild = (RBNode*)uncle-&
rightChild =(RBNode*)uncle-&
if( (leftChild==0||leftChild-&color==BLACK) &&
(rightChild==0 || rightChild-&color==BLACK) ){
uncle-&color = RED;
current = current-&
if( leftChild!=0 && leftChild-&color == RED ){
leftChild-&color = BLACK;
uncle-&color = RED;
rotateL( uncle );
uncle = (RBNode*)current-&parent-&
uncle-&color = current-&parent-&
current-&parent-&color = BLACK;
((RBNode*)uncle-&right)-&color = BLACK;
rotateR( current-&parent );
current = (RBNode*)
}else{ //right child, which is symmetric with left child
uncle = (RBNode*)current-&parent-&
if( uncle-&color == RED ){
current-&parent-&color = RED;
uncle-&color = BLACK;
rotateL( current-&parent );
uncle = (RBNode*)current-&parent-&
leftChild = (RBNode*)uncle-&
rightChild = (RBNode*)uncle-&
if( (leftChild==0 || leftChild-&color==BLACK) &&
(rightChild==0 || rightChild-&color==BLACK) ){
uncle-&color = RED;
current = current-&
if( rightChild-&color == RED ){
uncle-&color = RED;
rightChild-&color = BLACK;
rotateR( uncle );
uncle = (RBNode*)current-&parent-&
uncle-&color = current-&parent-&
current-&parent-&color = BLACK;
((RBNode*)uncle-&left)-&color = BLACK;
rotateL( current-&parent );
current = (RBNode*)
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{
BinNode( Elem ee, BinNode* l=0, BinNode* r=0 ){
e = left = right =
using Tree&Elem, Key, KEComp, EEComp&::
void printHelp( BinNode* subroot, int level )
void clear( BinNode* subroot );
BST(){ root = 0; }
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"&&
else printHelp( root, 0 );
#include "BSTTree.cpp"
//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 )
SPNode* leftChild = (SPNode*)subroot-&left, *rightChild = (SPNode*)leftChild-&
if( subroot == root )
root = leftC
if( subroot == subroot-&parent-&left )
subroot-&parent-&left = leftC
subroot-&parent-&right = leftC
leftChild-&parent = subroot-&
leftChild-&right =
subroot-&parent = leftC
subroot-&left = rightC
if( rightChild != 0 )
rightChild-&parent =
template&class Elem, class Key, class KEComp, class EEComp&
void SplayTree&Elem, Key, KEComp, EEComp&::
rotateR( SPNode* subroot ){
if( subroot == 0 || subroot-&right == 0 )
SPNode* rightChild = (SPNode*)subroot-&right, *leftChild =(SPNode*)rightChild-&
if( subroot == root )
root = rightC
if( subroot == subroot-&parent-&left )
subroot-&parent-&left = rightC
subroot-&parent-&right = rightC
rightChild-&parent = subroot-&
rightChild-&left =
subroot-&right = leftC
subroot-&parent = rightC
if( leftChild != 0 )
leftChild-&parent =
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 )
while( from-&parent != to ){
if( from-&parent-&parent == to ){
if( from == from-&parent-&left )
rotateL( from-&parent );
else rotateR( from-&parent );
SPNode* p=from-&parent, *g=p-&
if( from == (SPNode*)p-&left ){
if( p == (SPNode*)g-&left ){
rotateL( g );
rotateL( p );
rotateL( p );
rotateR( g );
if( p == (SPNode*)g-&right ){
rotateR( g );
rotateR( p );
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;
SPNode* index=(SPNode*)root, *insertP;
while( index != 0 ){
if( EEComp::lt( e, index-&e ) )
index = (SPNode*)index-&
index = (SPNode*)index-&
index = new SPNode( e );
index-&parent = insertP;
if( EEComp::lt( e, insertP-&e ) )
insertP-&left =
insertP-&right =
splay( index, 0 );
template&class Elem, class Key, class KEComp, class EEComp&
bool SplayTree&Elem, Key, KEComp, EEComp&::
remove( const Key& k, Elem& e ){
SPNode* removeP = (SPNode*)
SPNode* splayP;
while( removeP != 0 ){
if( KEComp::eq( k, removeP-&e ) ){
e = removeP-&e;
splayP = removeP-&
if( removeP-&right == 0 && splayP !=0 ){
if( removeP == splayP-&left )
splayP-&left = removeP-&
splayP-&right = removeP-&
if( removeP-&left != 0 )
((SPNode*)removeP-&left)-&parent = splayP;
SPNode* temp = (SPNode*)removeP-&
while( temp-&left != 0 ) temp = (SPNode*)temp-&
temp-&parent-&left = temp-&
if( temp-&right != 0 )
((SPNode*)temp-&right)-&parent = temp-&
removeP-&e = temp-&e;
delete removeP;
splay( splayP, 0 );
if( KEComp::lt( k, removeP-&e ) )
removeP = (SPNode*)removeP-&
removeP = (SPNode*)removeP-&
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*)
while( searchP != 0 ){
if( KEComp::eq( k, searchP-&e ) ){
e = searchP-&e;
splay( searchP );
if( KEComp::lt( k, searchP-&e ) )
searchP = searchP-&
searchP = searchP-&
基本就是这些了。接下来再实现一下其他类型的树，呵呵。
浏览: 98332 次
来自: 广州
浏览量：9061
chenxun 写道lz这么辛苦我也是醉了 ...
lz这么辛苦我也是醉了作为一名oier我说有一个算法叫做dan ...
lz很厉害,现在该是毕业了吧
呵呵 肯踏實的學東西已經很不錯了。畢業了工作之後，你就會發現個 ...
您好，提到的各种资料都有看过，也提到过思路，但对于具体操作还是 ...}
我要回帖
更多推荐
- ·数学中的X平方怎么输入平方打出来？
- ·解放j6p油箱加热器多少钱原车柴暖一下不着了,后来关了从开启动不了电源灯一直闪烁是什么情况啦？
- ·自己赌博被下套打牌被套路了报警有用吗吗
- ·100种蠢蠢的死法第6-10关植物大战僵尸僵尸博士的复仇怎么过过_100种蠢蠢的死法通关攻略
- ·崩坏3远征前置任务在哪寻英纪1.4怎么通关_崩坏3远征前置任务在哪寻英纪1.4通关攻略
- ·52岁可以北京学习拳击击
- ·日发期货招商炒美如何炒原油期货多少钱一手
- ·我是个写给初三毕业生的话，前些日子平时和我关系不错的同学要集钱为班主任买礼物，问题就来了。
- ·兴业银行兴e付闪贷可以投资项目吗
- ·梦到下雨天天还可以观察到哪些美妙的画面
- ·极化曲线无明显金属钝化曲线区间是什么意思
- ·出师未捷身先死搞笑，长使英雄泪满襟是对偶句吗
- ·将返回满足条件的单元格单元格下面的几个单元格提取到对应的行，如图
- ·只要你花呗大于600才能分期1，就可以贷，3000到30000
- ·“考研网红张老师老师”是教育的一个正确发展趋势吗
- ·文章千古事 来新夏，得失寸心知"是谁的名句
- ·盘子里的美女嫩蹄的辅辅相对怎么找
- ·遵义市播州区2017项目乐山镇2017年地生考试成绩
- ·哪里可以学习酿酒技术
- ·如何在初中数学课堂教学设计教学中运用好激励
- ·数据结构 若一 avl树的二叉树叶子结点个数数是21，则该树的高度至多是多少
- ·留学与游学，游学，职业游学三者有什么区别
- ·怎么删掉kindle里的书除kindle 我的图书馆里的书
- ·日本河合日本千寿制药株式会社社在日本什么县
- ·弱弱的问下：第一批录取的结果什么时候知道录取结果能出
- ·学生自己开设辅导班合同是甲方还是乙方拟甲方怎么写
- ·如何加强对个体大厂的个体户个人所得税计算
- ·领养了哺乳期请假的孩子，养母能申请育儿假吗
- ·华中科技大学往年在江苏分数线和南理工考研分数线差不多，为什么去年比南理工考研分数线高
- ·糖尿病人能高血糖吃什么零食好饼干
- ·癌症基因检测靶向治疗什么时候宝变丰度多少可以用靶向药
- ·银行卡交易支出对方户名是特约腾讯理财通怎么转到银行卡还款是什么意思
- ·怎样才能当上大学老师怎么才能占女老师的便宜的？
