数据结构——二-3树

数据结构——2-3树

年前实现了一个2-3树，后来就玩儿去了，再后来看书去了，所以就耽搁了。基本上网上找不到什么2-3树的实现，大概是因为这东西基本真正被用过吧。基于它的思想而发明的B树，B+树才是真正的大头，不过2-3树的模型比较简单，对我们理解B树和B+树的实现有很大的帮助，所以最终我还是通过自己的努力，实现了一个2-3树。

下面是2-3树的基本介绍：

2-3树不是一种二叉树，但他的形状满足以下性质：
（1）一个节点包含一个或两个键值
（2）每个内部节点有两个子节点（如果它有一个键值）或三个子节点（如果它有两个键值）
（3）所有叶节点都在树结构的同一层，因此树的高度总是平衡的。

对于每个结点, 左子树中所有后继结点的值都小于第一个键的值, 而其中间子树中所有结点的值都大于或等于第一个键的值。如果结点有右子树的话( 相应地, 结点存储两个键值) , 那么其中间子树中所有后继结点的值都小于第二个键的值, 而其右子树中所有后继结点的值都大于或等于第二个键的值。同时，同一层的键值从左到右增大。

2-3树的查找方法与二分查找树相似，从根节点出发，如果在根节点找到查找值则查找成功返回，否则根据节点键的规则递归地查找下去，直到找到或返回失败。

在2-3树中插入新值时并不为其开辟一个新的叶子节点来存储，也就是说，2-3树不是向下生长的。插入算法首先找到一个合适的叶子节点来存放该值，使树的性质不被破坏。如果该叶子节点只包含一个值（每个节点都最多有两个值），则简单将该值放入叶子节点即可。如果叶子结点本身已经包含两个值了，则需要为前加入的叶子开辟新的空间。设节点L为插入节点，但是已经满了，也就是，这个节点因为包含了三个值，所以必须进行分裂，设新分裂出来的节点为L’，则L将存储这三个值中最小的那个值，而L’则存储这三个值中最大的那个。处于中间的值将得到提升，作为插入值晋升到父节点去。如果父节点只包含一个键值，该值直接放入节点即可，否则，同样的“分裂-晋升”过程将在该父节点进行，一直递归到根节点为止。2-3的插入实现中利用了一个函数splitNode，它接收被插入节点的指针和插入的数据，并将指向L'指针和被往上传的值通过引用传回来。当插入结点已满时便启用这个函数。

从2-3树删除一个节点，有三种可能情况需要考虑：最简单的情况是，如果删除的值存储在有两个键值的节点上，直接删除该值并不影响树的性质与结构。如果被删除的值所在的节点只有它一个键值，被删除后该节点将为空，因此通过向兄弟节点借一个记录，并修改父节点来解决。如果兄弟节点不够借，则需要合并相邻节点，并影响双亲，可能导致树的高度下降。如果被删除的值是树的内部节点，则将被删除记录用右边子树中的最小键值代替，然后再根据第一、二种情况将该值删除。第一种情况的实现相当简单，只需要考虑如果删除的是左键值，那么要把右键值移过来而已。被借的情况由borrowLeft和borrowRight来实现，合并的情况由mergeLeft和mergeRight来实现。具体代码如下：

//TTTree.h#ifndef TTTREE_H#define TTTREE_H#include<iostream>#include<queue>using namespace std;template<class Elem, class Key, class KEComp, class EEComp>class TTTree : public Tree<Elem, Key, KEComp, EEComp>{protected:using Tree<Elem, Key, KEComp, EEComp>::count;struct TTNode{Elem elems[2];TTNode* ptrs[3];TTNode(){ptrs[0] = ptrs[1] = ptrs[2] = 0;}TTNode( Elem empty ){ptrs[0] = ptrs[1] = ptrs[2] = 0;elems[0] = elems[1] = empty;} };TTNode* root;Elem EMPTY;int height;void splitNode( TTNode* subroot, TTNode* inPtr, Elem inVal, TTNode*& retPtr, Elem& retVal );bool insertHelp( TTNode* subroot, const Elem& e, TTNode*& retPtr, Elem& retVal );void clear( TTNode* subroot );void borrowLeft( TTNode* subroot, int ptrIndex );void borrowRight( TTNode* subroot, int ptrIndex );void mergeLeft( TTNode* subroot, int ptrIndex );void mergeRight( TTNode* subroot, int ptrIndex );void removeHelp( TTNode* subroot, const Key& k, Elem& e );public:TTTree( const Elem& em ){root = 0;height = 0;EMPTY = em;}~TTTree(){clear( root );}bool insert( const Elem& e);bool remove( const Key& k ,Elem& e );bool search( const Key& k, Elem& e );void print() const;};#include "TTTree.cpp"#endif

?

//TTTree.cpptemplate<class Elem, class Key, class KEComp, class EEComp>bool TTTree<Elem, Key, KEComp, EEComp>::search( const Key& k, Elem& e ){TTNode* current=root;while( current != 0 ){if( KEComp::eq( k, current->elems[0] ) ){e = current->elems[0];return true;}if( !EEComp::eq( EMPTY, current->elems[1] ) && KEComp::eq( k, current->elems[1] ) ){e = current->elems[1];return true;}if( KEComp::lt( k, current->elems[0] ) )current = current->ptrs[0];else if( EEComp::eq( EMPTY, current->elems[1] ) || KEComp::lt( k, current->elems[1] ) )current = current->ptrs[1];elsecurrent = current->ptrs[2];}return false;}template<class Elem, class Key, class KEComp, class EEComp>void TTTree<Elem, Key, KEComp, EEComp>::clear( TTNode* subroot ){if( subroot == 0 )return;for( int i=0; i<3; i++ )clear( subroot->ptrs[i] );delete subroot;}template<class Elem, class Key, class KEComp, class EEComp>void TTTree<Elem, Key, KEComp, EEComp>::print() const{if( root == 0 ){cout<<"empty tree"<<endl;return;}queue<TTNode*> nodeQueue;nodeQueue.push(root);TTNode* current;int h = height;int intent=1;string BLANK="       ";for( int i=1; i<height; i++ )intent *= 3;int num = 1;while( h>0 && !nodeQueue.empty() ){for( int i=0; i<num; i++ ){current = nodeQueue.front();nodeQueue.pop();if( current != 0 ){for( int j=0; j<3; j++ )nodeQueue.push( current->ptrs[j] );for( int j=0; j<intent/2; j++ )cout<<BLANK;cout<<"|"<<current->elems[0]<<"|";if( EEComp::eq( EMPTY, current->elems[1] ) )cout<<"__|";elsecout<<current->elems[1]<<"|";for( int j=0; j<intent/2; j++ )cout<<BLANK;}else{for( int j=0; j<3; j++ )nodeQueue.push( 0 );for( int j=0; j<intent; j++ )cout<<BLANK;}}cout<<endl;intent /= 3;num *= 3;h--;}}template<class Elem, class Key, class KEComp, class EEComp>void TTTree<Elem, Key, KEComp, EEComp>::splitNode( TTNode* subroot, TTNode* inPtr, Elem inVal, TTNode*& retPtr, Elem& retVal ){retPtr = new TTNode( EMPTY );if( EEComp::lt( inVal, subroot->elems[0] ) ){retVal = subroot->elems[0];subroot->elems[0] = inVal;retPtr->elems[0] = subroot->elems[1];retPtr->ptrs[0] = subroot->ptrs[1];retPtr->ptrs[1] = subroot->ptrs[2];subroot->ptrs[1] = inPtr;}else{if( EEComp::lt( inVal, subroot->elems[1] ) ){retVal = inVal;retPtr->elems[0] = subroot->elems[1];retPtr->ptrs[0] = inPtr;retPtr->ptrs[1] = subroot->ptrs[2];}else{retVal = subroot->elems[1];retPtr->elems[0]=inVal;retPtr->ptrs[0] = subroot->ptrs[2];retPtr->ptrs[1] = inPtr;}}subroot->ptrs[2] = 0;subroot->elems[1] = EMPTY;}template<class Elem, class Key, class KEComp, class EEComp>bool TTTree<Elem, Key, KEComp, EEComp>::insertHelp( TTNode* subroot, const Elem& e, TTNode*& retPtr, Elem& retVal ){Elem tempRetVal; TTNode* tempRetPtr=0;if( subroot->ptrs[0] == 0 ){//leafif( EEComp::eq( EMPTY, subroot->elems[1] ) ){if( EEComp::lt( e, subroot->elems[0] ) ){subroot->elems[1] = subroot->elems[0];subroot->elems[0] = e;}elsesubroot->elems[1] = e;}elsesplitNode( subroot, 0, e, retPtr, retVal );}else if( EEComp::lt( e, subroot->elems[0] ) )insertHelp( subroot->ptrs[0], e, tempRetPtr, tempRetVal );else if( EEComp::eq( EMPTY, subroot->elems[1] ) || EEComp::lt( e, subroot->elems[1] ) )insertHelp( subroot->ptrs[1], e, tempRetPtr, tempRetVal );elseinsertHelp( subroot->ptrs[2], e, tempRetPtr, tempRetVal );if( tempRetPtr != 0 ){if( EEComp::eq( EMPTY, subroot->elems[1] ) ){if( EEComp::lt( tempRetVal, subroot->elems[0] ) ){subroot->elems[1] = subroot->elems[0];subroot->elems[0] = tempRetVal;subroot->ptrs[2] = subroot->ptrs[1];subroot->ptrs[1] = tempRetPtr;}else{subroot->elems[1] = tempRetVal;subroot->ptrs[2] = tempRetPtr;}}elsesplitNode( subroot, tempRetPtr, tempRetVal, retPtr, retVal );}return true;}template<class Elem, class Key, class KEComp, class EEComp>bool TTTree<Elem, Key, KEComp, EEComp>::insert( const Elem& e ){if( root == 0 ){root = new TTNode( EMPTY );root->elems[0] = e;height++;count++;return true;}Elem myRetVal;TTNode* myRetPtr = 0;if( insertHelp( root, e, myRetPtr, myRetVal ) ){count++;if( myRetPtr != 0 ){TTNode* temp = new TTNode(EMPTY);temp->elems[0] = myRetVal;temp->ptrs[0] = root;temp->ptrs[1] = myRetPtr;root = temp;height ++;}return true;}return false;}template<class Elem, class Key, class KEComp, class EEComp>void TTTree<Elem, Key, KEComp, EEComp>::removeHelp( TTNode* subroot, const Key& k, Elem& e ){if( subroot == 0 ){e = EMPTY;return ;}e = EMPTY;Elem tempElem = EMPTY;int ptrIndex = -1;if( KEComp::eq( k, subroot->elems[0] ) ){e = subroot->elems[0];if( subroot->ptrs[0] == 0 ){//leaf nodeif( !EEComp::eq( EMPTY, subroot->elems[1] ) ){ subroot->elems[0]=subroot->elems[1]; subroot->elems[1]= EMPTY;}elsesubroot->elems[0] = EMPTY;return ;}else{//if not leaf node, find a leaf node to take place of itTTNode* replace=subroot->ptrs[1];while( replace->ptrs[0] != 0 )replace = replace->ptrs[0];subroot->elems[0]=replace->elems[0];ptrIndex = 1;removeHelp( subroot->ptrs[1], getKey(replace->elems[0]), tempElem );tempElem = e;}}else if( !EEComp::eq( EMPTY, subroot->elems[1] ) && KEComp::eq( k, subroot->elems[1] ) ){e = subroot->elems[1];if( subroot->ptrs[0] == 0 ){subroot->elems[1] = EMPTY;return;}else{TTNode* replace=subroot->ptrs[2];while( replace->ptrs[0] != 0 )replace = replace->ptrs[0];subroot->elems[1] = replace->elems[0];ptrIndex = 2;removeHelp( subroot->ptrs[2], getKey( replace->elems[0] ), tempElem );tempElem = e;}}else if( KEComp::lt( k, subroot->elems[0] ) ){ptrIndex = 0;removeHelp( subroot->ptrs[0], k, tempElem );}else if( EEComp::eq( EMPTY, subroot->elems[1] ) || KEComp::lt( k, subroot->elems[1] ) ){ptrIndex = 1;removeHelp( subroot->ptrs[1], k, tempElem );}else{ptrIndex = 2;removeHelp( subroot->ptrs[2], k, tempElem );}if( ptrIndex>=0 && !EEComp::eq( EMPTY, tempElem ) ){e = tempElem;if( EEComp::eq( EMPTY, subroot->ptrs[ptrIndex]->elems[0]) ){if( ptrIndex == 0 ){if( !EEComp::eq( EMPTY, subroot->ptrs[1]->elems[1] ) ){borrowRight( subroot, 0 );}else if( EEComp::eq( EMPTY, subroot->elems[1] ) ){mergeRight( subroot, 0 );}else if( !EEComp::eq( EMPTY, subroot->ptrs[2]->elems[1] ) ){borrowRight( subroot, 0 );borrowRight( subroot, 1 );}else{borrowRight( subroot, 0 );mergeRight( subroot, 1 );}}else if( ptrIndex == 1 ){if( !EEComp::eq( EMPTY, subroot->ptrs[0]->elems[1] ) ){borrowLeft( subroot, 1 );}else if( EEComp::eq( EMPTY, subroot->elems[1] ) ){mergeLeft( subroot, 1 );}else if( !EEComp::eq( EMPTY, subroot->ptrs[2]->elems[1] ) ){borrowRight( subroot, 1 );}else{mergeRight( subroot, 1 );}}else if( ptrIndex == 2 ){if( !EEComp::eq( EMPTY, subroot->ptrs[1]->elems[1] ) ){borrowLeft( subroot, 2 );}else if( !EEComp::eq( EMPTY, subroot->ptrs[0]->elems[1] ) ){borrowLeft( subroot, 1 );borrowLeft( subroot, 2 );}else{mergeLeft( subroot, 2 );}}}}}template<class Elem, class Key, class KEComp, class EEComp>void TTTree<Elem, Key, KEComp, EEComp>::borrowRight( TTNode* subroot, int ptrIndex ){if( ptrIndex<0 || ptrIndex>1 )return;subroot->ptrs[ptrIndex]->elems[0] = subroot->elems[ptrIndex];subroot->elems[ptrIndex] = subroot->ptrs[ptrIndex+1]->elems[0];subroot->ptrs[ptrIndex+1]->elems[0] = subroot->ptrs[ptrIndex+1]->elems[1];subroot->ptrs[ptrIndex+1]->elems[1] = EMPTY;subroot->ptrs[ptrIndex]->ptrs[1] = subroot->ptrs[ptrIndex+1]->ptrs[0];subroot->ptrs[ptrIndex+1]->ptrs[0] = subroot->ptrs[ptrIndex+1]->ptrs[1];subroot->ptrs[ptrIndex+1]->ptrs[1]= subroot->ptrs[ptrIndex+1]->ptrs[2];subroot->ptrs[ptrIndex+1]->ptrs[2] = 0;}template<class Elem, class Key, class KEComp, class EEComp>void TTTree<Elem, Key, KEComp, EEComp>::borrowLeft( TTNode* subroot, int ptrIndex ){if( ptrIndex>2 || ptrIndex<1 )return;subroot->ptrs[ptrIndex]->elems[1] = subroot->ptrs[ptrIndex]->elems[0];subroot->ptrs[ptrIndex]->elems[0] = subroot->elems[ptrIndex-1];subroot->elems[ptrIndex-1] = subroot->ptrs[ptrIndex-1]->elems[1];subroot->ptrs[ptrIndex-1]->elems[1] = EMPTY;subroot->ptrs[ptrIndex]->ptrs[1] = subroot->ptrs[ptrIndex]->ptrs[0];subroot->ptrs[ptrIndex]->ptrs[0] = subroot->ptrs[ptrIndex-1]->ptrs[2];subroot->ptrs[ptrIndex-1]->ptrs[2] = 0;}template<class Elem, class Key, class KEComp, class EEComp>void TTTree<Elem, Key, KEComp, EEComp>::mergeRight( TTNode* subroot, int ptrIndex ){if( ptrIndex<0 || ptrIndex>1 )return;subroot->ptrs[ptrIndex]->elems[0] = subroot->elems[ptrIndex];subroot->elems[ptrIndex] = EMPTY;subroot->ptrs[ptrIndex]->elems[1] = subroot->ptrs[ptrIndex+1]->elems[0];subroot->ptrs[ptrIndex]->ptrs[1] = subroot->ptrs[ptrIndex+1]->ptrs[0];subroot->ptrs[ptrIndex]->ptrs[2] = subroot->ptrs[ptrIndex+1]->ptrs[1];delete subroot->ptrs[ptrIndex+1];subroot->ptrs[ptrIndex+1] = 0;}template<class Elem, class Key, class KEComp, class EEComp>void TTTree<Elem, Key, KEComp, EEComp>::mergeLeft( TTNode* subroot, int ptrIndex ){if( ptrIndex<1 || ptrIndex>2 )return;subroot->ptrs[ptrIndex-1]->elems[1] = subroot->elems[ptrIndex-1];subroot->elems[ptrIndex-1] = EMPTY;subroot->ptrs[ptrIndex-1]->ptrs[2] = subroot->ptrs[ptrIndex]->ptrs[0];delete subroot->ptrs[ptrIndex];subroot->ptrs[ptrIndex] = 0;}template<class Elem, class Key, class KEComp, class EEComp>bool TTTree<Elem, Key, KEComp, EEComp>::remove( const Key& k, Elem& e ){ e = EMPTY; removeHelp( root, k, e ); if( e == EMPTY ) return false; if( EEComp::eq( EMPTY, root->elems[0] ) ){ TTNode* temp = root; root = root->ptrs[0]; height --;}return true;}

?