最近写了一个类似stl的btree，拿出来与大家共享一下。这个btree的用法与stl中的map非常相似。我在vc7.1和redhat（gcc 3.2）中编译成功。btree未经过严格测试，欢迎大家一起来测试完善他。
如果发现有什么问题，或者有什么建议，可以跟我联系。联系方式：larrin2002@msn.com。
1.btree源码
#ifndef _LARRIN_WORKSHOP_BTREE_H
#define _LARRIN_WORKSHOP_BTREE_H
#include <memory.h>
#define BEGIN_NAMESPACE namespace LarrinDSL {
#define END_NAMESPACE }
#ifndef NULL
#ifdef __cplusplus
#define NULL 0
#else
#define NULL ((void *)0)
#endif
#endif
BEGIN_NAMESPACE
template<class Type>
struct btree_less
{
bool operator()(const Type& _Left, const Type& _Right) const
{
return _Left < _Right ;
}
};
template <class _first_,class _second_>
struct btree_pair
{
/*typename*/ _first_ first ;
/*typename*/ _second_ second ;
btree_pair(){}
btree_pair(/*typename*/ _first_ v1,/*typename*/ _second_ v2)
{
first = v1 ;
second = v2;
}
~btree_pair(){}
};
template <class Key, class Type, unsigned int order , class Traits = btree_less<Key> >
class btree
{
public:
typedef Key key_type ;
typedef Type data_type;
typedef Traits key_compare;
typedef unsigned long size_type;
typedef btree_pair<key_type,data_type> value_type ;
private:
typedef btree<Key,Type,order,Traits> _btree_;
static const unsigned int mid_pos = (int)(order / 2);
static const unsigned int max_val_size = order - 1 ;
static const unsigned int min_vals = ((order + 1) / 2) - 1 ;
struct tree_iterator;
class BTNode
{
friend class _btree_;
friend class _btree_::tree_iterator ;
int keynum ;
BTNode *parent ;
int sub_id ; //i am my parent's sub_id'th sun
value_type *vals[order] ; //value node
BTNode *subTree[order+1] ;
public:
BTNode()
{
memset(this,0,sizeof(BTNode));
}
~BTNode()
{
}
BTNode *left_sibling()
{
if(this->parent && this->sub_id > 0)
{
return this->parent->subTree[sub_id - 1];
}
return NULL ;
}
BTNode *right_sibling()
{
if(this->parent && this->sub_id < this->parent->keynum)
{
return this->parent->subTree[sub_id + 1];
}
return NULL ;
}
void set_parent(BTNode *p,const int sub_id)
{
this->parent = p ;
this->sub_id = sub_id ;
this->parent->subTree[sub_id] = this ;
}
Key & _key_(const int idx){return vals[idx]->first ;}
bool find_in_node(const Key &key,int &pos)
{
if(keynum == 0)
{
pos = 0 ;
return false ;
}
pos = -1 ;
//binary search ...
int top,bottom,mid ;
top = 0 ;
bottom = keynum == 0 ? 0 : keynum -1;
typename _btree_::key_compare less;
for(;;)
{
mid = (top + bottom) / 2 ;
if(less(key , _key_(mid))) //key < _key_(mid)
{
if(top >= bottom -1)
{
pos = mid ;
return false ;
}
bottom = mid - 1 ;
}
else if(less(_key_(mid),key)) //key > _key_(mid)
{
if(top == bottom)
{
pos = mid + 1;
return false ;
}
top = mid + 1 ;
}
else //find it
{
pos = mid ;
return true ;
}
}
}
void move_up(int new_key_pos,BTNode *&node,int &where)
{
BTNode *new_node = new BTNode ;
int k = 0 ;
for(int i = mid_pos + 1 ; i <= max_val_size ; i++,k++)
{
new_node->vals[k] = this->vals[i] ;
if(this->subTree[i])
this->subTree[i]->set_parent(new_node,k);
this->keynum--;
new_node->keynum++;
}
if(this->subTree[max_val_size+1])
this->subTree[max_val_size+1]->set_parent(new_node,k);
if(new_key_pos != -1)
{
if(new_key_pos < mid_pos) // new key will keep it's position
{
new_key_pos = -1 ; //keep it's position
}
else if(new_key_pos > mid_pos) //new key will be move up
{
node = new_node ;
where = where - mid_pos - 1;
new_key_pos = -1 ; //keep new key's position
}
//else{} //new key will be moveup
}
if(this->parent) // have parent's
{
if(new_key_pos != -1) // new key is moved into parent
{
node = this->parent ;
where = this->sub_id;
}
for(int i = this->parent->keynum ; i > this->sub_id ; i--)
{
this->parent->vals[i] = this->parent->vals[i-1];
this->parent->subTree[i]->set_parent(this->parent,i+1);
}
this->parent->vals[this->sub_id] = this->vals[mid_pos] ;
--this->keynum;
new_node->set_parent(this->parent,this->sub_id+1);
if(++this->parent->keynum > max_val_size)
{
this->parent->move_up(new_key_pos,node,where);
}
}
else // i am the current root
{
BTNode *new_root = new BTNode ;
new_root->vals[0] = this->vals[mid_pos];
--this->keynum;
++new_root->keynum ;
if(new_key_pos != -1)
{
node = new_root ;
where = 0 ;
}
this->set_parent(new_root,0);
new_node->set_parent(new_root,1);
}
}
bool insert(const key_type &key,const data_type &data,BTNode *&node,int &where)
{
int pos ;
if(find_in_node(key,pos)) //key exsist in this node already
{
return false ;
}
if(this->subTree[pos] != NULL)
{
return this->subTree[pos]->insert(key,data,node,where);
}
else
{
for(int i = this->keynum ; i > pos; i--)
{
this->vals[i] = this->vals[i-1] ;
}
{//where the new key is inserted
node = this ;
where = pos ;
}
vals[pos] = new value_type ;
vals[pos]->first = key ;
vals[pos]->second = data ;
if(++this->keynum > max_val_size) //slipt this node,new key will be moved up
{
move_up(pos,node,where);
}
return true ;
}
}
bool find(const Key &key,BTNode *&node,int &pos)
{
if(find_in_node(key,pos))
{
node = this ;
return true ;
}
else
{
if(this->subTree[pos])
{
return this->subTree[pos]->find(key,node,pos);
}
else
{
return false ;
}
}
}
BTNode * erase(BTNode *node,int idx)
{
//step1 : delete the key
delete node->vals[idx];
//step2 : find my successor( or former)
BTNode *leaf ;
{
int rIdx ;
if(NULL == node->subTree[idx+1]) //node is a leaf
{
leaf = node ;
rIdx = idx ;
}
else
{
rIdx = 0 ;
leaf = node->subTree[idx+1] ;
while(NULL != leaf->subTree[0])
{
leaf = leaf->subTree[0] ;
}
node->vals[idx] = leaf->vals[0] ; //copy successor to ...
}
//move
for(int i = rIdx ; i < leaf->keynum - 1; i++)
{
leaf->vals[i] = leaf->vals[i+1];
}
leaf->keynum-- ;
}
//now the key is removed,we need makes sure of balance of this tree
//case 1
if(leaf->keynum >= min_vals)
return NULL;
return merge(leaf);
}
BTNode * merge(BTNode *node)
{
//case 2
if(!node->parent) //this is root too
return NULL;
//case 3
{
BTNode *sibling = node->left_sibling();
if(sibling && sibling->keynum > min_vals)
{
for(int i = node->keynum ; i > 0 ; i--)
{
node->vals[i] = node->vals[i-1];
if(node->subTree[i])
node->subTree[i]->set_parent(node,i+1);
}
node->vals[0] = node->parent->vals[node->sub_id-1];
if(sibling->subTree[sibling->keynum])
sibling->subTree[sibling->keynum]->set_parent(node,0);
node->keynum++;
node->parent->vals[node->sub_id-1] = sibling->vals[sibling->keynum-1];
sibling->keynum-- ;
return NULL;
}
sibling = node->right_sibling();
if(sibling && sibling->keynum > min_vals)
{
node->vals[node->keynum] = node->parent->vals[node->sub_id];
if(sibling->subTree[0])
sibling->subTree[0]->set_parent(node,node->keynum + 1) ;
node->keynum++ ;
node->parent->vals[node->sub_id] = sibling->vals[0];
for(int i = 0 ; i < sibling->keynum - 1 ;i++)
{
sibling->vals[i] = sibling->vals[i+1] ; //move ...
if(sibling->subTree[i+1])
sibling->subTree[i+1]->set_parent(sibling,i) ;
}
if(sibling->subTree[sibling->keynum])
sibling->subTree[sibling->keynum]->set_parent(sibling,sibling->keynum - 1) ;
sibling->keynum--;
return NULL;
}
}
//case 4 : do merge now
{
BTNode *left ,*right ;
left = node->left_sibling();
if(left)
{
right = node ;
}
else
{
left = node ;
right = node->right_sibling() ;
}
//now merge left/right/parent
//step1:
{
left->vals[left->keynum] = left->parent->vals[left->sub_id];
if(right->subTree[0])
right->subTree[0]->set_parent(left,left->keynum+1);
left->keynum++;
}
//step2:remove parent's valus
{
for(int i = left->sub_id ; i < left->parent->keynum - 1 ; i++)
{
left->parent->vals[i] = left->parent->vals[i+1];
if(left->parent->subTree[i+2])
left->parent->subTree[i+2]->set_parent(left->parent,i+1) ;
}
left->parent->keynum--;
}
//step3: merge left and right - move right into left
{
for(int i = 0 ; i < right->keynum ; i++)
{
left->vals[left->keynum] = right->vals[i];
left->keynum++;
if(right->subTree[i+1])
right->subTree[i+1]->set_parent(left,left->keynum) ;
}
delete right ;
}
if(left->parent->keynum < min_vals)
{
if(left->parent->keynum == 0 && !left->parent->parent) //this is root,left become new root
{
delete left->parent ;
left->parent = NULL ;
return left ;
}
else
{
return merge(left->parent);
}
}
}
}
void destroy()
{
for(int i = 0 ; i < this->keynum ; i++)
{
delete vals[i];
}
if(this->subTree[0] == NULL) //this is a leaf
{
delete this ;
return ;
}
else
{
for(int i = 0 ; i < this->keynum+1 ; i++)
{
this->subTree[i]->destroy();
}
}
delete this ;
}
};
BTNode *m_Root ; //btree
size_type m_size ;
public:
struct tree_iterator
{
BTNode * curNode ;
int curKey ;
tree_iterator():curNode(NULL),curKey(0){}
tree_iterator(BTNode *node,int key):curNode(node),curKey(key){}
value_type & operator->() const
{
return *(curNode->vals[curKey]);
}
value_type & operator *() const
{
return *(curNode->vals[curKey]);
}
bool operator == (const tree_iterator &it) const
{
return (this->curNode == it.curNode && this->curKey == it.curKey) ;
}
bool operator != (const tree_iterator &it) const
{
return (this->curNode != it.curNode || this->curKey != it.curKey) ;
}
tree_iterator & operator ++()
{
if(curNode->subTree[curKey+1] == NULL)
{
if(++curKey < curNode->keynum)
{
}
else
{
//check if this is end()
BTNode *node = curNode->parent ;
if(node == NULL)
{
return *this ; //end
}
int tmp = curNode->sub_id;
while(node && tmp >= node->keynum)
{
tmp = node->sub_id ;
node = node->parent ;
}
if(node == NULL)
{
return *this ; //end
}
curKey = tmp ;
curNode = node ;
}
}
else
{
curNode = curNode->subTree[curKey+1] ;
while(curNode->subTree[0])
{
curNode = curNode->subTree[0];
}
curKey = 0 ;
}
return *this ;
}
};
struct const_tree_iterator
{
const BTNode *curNode ;
int curKey ;
const_tree_iterator():curNode(NULL),curKey(0){}
const_tree_iterator(const BTNode *node,int key):curNode(node),curKey(key){}
};
public:
typedef tree_iterator iterator ;
typedef const_tree_iterator const_iterator ;
btree():m_Root(NULL),m_size(0)
{
}
~btree()
{
clear();
}
iterator begin( )
{
if(!m_Root) return iterator(NULL,-1);
BTNode *node = m_Root ;
while(node->subTree[0])
{
node = node->subTree[0] ;
}
return tree_iterator(node,0);
}
const_iterator begin( ) const
{
if(!m_Root) return iterator(NULL,-1);
const BTNode *node = m_Root ;
while(node->subTree[0])
{
node = node->subTree[0] ;
}
return const_tree_iterator(node,0);
}
iterator end()
{
if(!m_Root) return iterator(NULL,-1);
BTNode * node = m_Root ;
while(node->subTree[node->keynum-1])
{
node = node->subTree[node->keynum];
}
return tree_iterator(node,node->keynum);
}
btree_pair<iterator,bool> insert(const Key &key,const Type & data)
{
typedef btree_pair<iterator,bool> ret_type ;
BTNode *node ;
int pos ;
if(NULL == m_Root)
{
m_Root = new BTNode();
}
if(m_Root->insert(key,data,node,pos))
{
while(m_Root->parent)
{
m_Root = m_Root->parent ;
}
m_size++ ;
return ret_type(iterator(node,pos),true) ;
}
return ret_type(this->end(),false) ;
}
Type & operator[](const Key &key)
{
if(!this->m_Root)
{
this->m_Root = new BTNode ;
}
iterator it = this->find(key);
if(it != this->end())
{
return (*it).second ;
}
else
{
btree_pair<iterator,bool> res = this->insert(key,data_type());
return (*res.first).second ;
}
}
iterator find(const Key& key)
{
if(!m_Root) return iterator(NULL,-1);
BTNode *node ;
int pos ;
if(m_Root->find(key,node,pos))
{
return iterator(node,pos);
}
else
{
return end();
}
}
size_type erase(const Key &key)
{
iterator it = this->find(key);
erase(it) ;
return m_size ;
}
void erase(iterator where)
{
if(where != this->end())
{
BTNode *root = m_Root->erase(where.curNode,where.curKey);
if(root) m_Root = root ; //wei have new root ;
m_size--;
}
}
size_type size()
{
return m_size ;
}
void clear()
{
if(m_Root)
{
m_Root->destroy();
}
m_Root = NULL ;
m_size = 0 ;
}
bool empty()
{
return m_size == 0 ;
}
};
END_NAMESPACE
#endif //
2.测试程序
#include "btree.h"
#include <stdio.h>
using namespace LarrinDSL ;
int main()
{
typedef btree<char,char,5> testTree ;
testTree a;
char keys[] = "agfbkdhmjesirxclntup" ;
for(char *p = keys ; *p ; p++)
{
//btree_pair<testTree::iterator,bool> k = a.insert(*p,*p);
a[*p] = *p ;
}
a.erase('h');
a.erase('r');
a.erase('p');
a.erase('d');
return 0 ;
}
