evasiu
- 浏览: 165473 次
- 性别:
- 来自: 广州
-
博客专栏
-
-
TCP/IP详解卷一>阅读...
浏览量：12264
文章分类
最新评论
-
master11：
你好，博主看完你的解释，好厉害啊！！佩服。如果想运行看一下效果 ...
数独人工解法的一些技巧及其python实现 -
evasiu：
chenxun1012033254 写道lz这么辛苦我也是醉了 ...
数独人工解法的一些技巧及其python实现 -
chenxun1012033254：
lz这么辛苦我也是醉了作为一名oier我说有一个算法叫做dan ...
数独人工解法的一些技巧及其python实现 -
xuyfiei：
lz很厉害,现在该是毕业了吧
恨毕业--读研一年总结 -
nphoenix：
呵呵 肯踏實的學東西已經很不錯了。畢業了工作之後，你就會發現個 ...
恨毕业--读研一年总结
在《基于树的索引结构介绍》（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;
}
基本就是这些了。接下来再实现一下其他类型的树，呵呵。
分享到：
发表评论
-
我对KM算法的理解
2012-12-26 15:47 25449一般对KM算法的描述， ... -
正则表达式的一些笔记
2012-08-16 23:30 01. 文字符号 1.1 特殊字符：[ ] \ ^ $ . | ... -
一个小题目（单词统计）
2012-08-14 23:12 1262今天休息的时候看到一个关于单词统计的小题目： 统计一段由字符 ... -
数独人工解法的一些技巧及其python实现
2012-06-13 16:31 6466这段日子实现了十几种 ... -
Eva'Sudoku-0.1新鲜出炉啦~~
2012-05-27 21:06 1272呵呵，经过将近一个星期的对pygame的了解与熟悉，我终于磕磕 ... -
产生数独迷题
2012-05-24 18:13 1879随着数独解题算法DLX的 ... -
解数独——dancing link X
2012-05-21 22:59 7866折腾了一个星期，发现 ... -
总共有多少个数独？
2012-05-12 15:31 12649憋屈地看了一个星期的 ... -
《算法引论》之算法分析
2012-04-26 14:01 1524上次写博客，已经是半个月之前了。我也不知道我这段日子在干嘛了， ... -
编程之美续
2012-04-06 15:37 1030看完编程之美后看很多题，都会发现原来只是里面一些题目的变种（也 ... -
编程之美
2012-04-02 16:54 1360前段日子又看了编程之美，后来闲着无聊学python去了，想着书 ... -
stl中的几个精美算法
2012-03-17 18:35 1119关于STL中的算法，我印象比较深刻的主要有用于list的sor ... -
STL和内存管理技术
2012-03-17 16:46 9598前段日子读了STL的源码 ... -
数据结构——2-3树
2012-02-10 14:25 7056年前实现了一个2-3树， ... -
编程珠玑--关于查找（二分法、自组织链、哈希）
2011-12-31 19:36 2032查找是我们现实生活中 ... -
编程珠玑 -- 关于堆
2011-12-28 15:31 1097堆是这样一种数据结构，它首先是一棵二叉树，而且还是一棵完全二叉 ... -
编程珠玑 -- 关于排序
2011-12-27 20:12 897《编程珠玑》主要提到 ... -
编程珠玑 -- 数据结构？
2011-12-21 21:15 624又开始看《编程珠玑》，发现之前看的也许不是很认真吧，再看一遍的 ... -
基于树的索引结构介绍
2011-07-01 17:59 2597转眼又七月份了。6月份后来就变成考试月了。因为图论要求写阅读报 ... -
Moment in Peking
2011-06-05 17:01 989"Moment in Peking" wa ...
相关推荐
数据结构-树与二叉树算法汇总,考研面试等很多常见的题型.
数据结构-树和二叉树-PPT
数据结构--二叉树--思维导图.pdf
Java基础复习笔记08数据结构-二叉树和二叉树的遍历。
2015广工数据结构实验--平衡二叉树(包含源码和实验报告
本程序简单实现了《数据结构》课本中二叉树的中序线索化算法，并同时实现了与子对应的中序线索化非递归遍历二叉树的算法
查找算法，平衡二叉树，大话数据结构里面的。
数据结构中的一个c++工程———二叉树的存储与遍历的实现
数据结构二叉树，内含有代码，还不错！！！！！！！
数据结构课设--哈夫曼二叉树.doc
数据结构课件中的二叉树，包含二叉树的几种算法
关于树和二叉树的一个课件，适用于数据结构初学者和选修数据结构课程的本科生
数据结构课程设计-平衡二叉树的操作！本人以前做的就是这个，非常不错的，不过就只有代码哦！
树 二叉树 的相关算法 大程序噢 有树的存储结构 先序遍历 中 后 层次 广度
二叉树的左遍历优先：有详细的说明，希望对你有帮助。
这是一个用C实现的AVL tree，带MFC的测试程序。 在我的机器上(P4 T2050 Duo, 1G memory)列C盘所有文件并组织成AVL tree，一共是70000多个文件和目录，耗时大约是5-7秒
An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is...
算法大全-面试题-链表-栈-二叉树-数据结构，面试利器
算法-树形结构- 树与二叉树- 树的数据生成器.rar