数据结构——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.cpp


template<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];
					else
						current = 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<<"__|";
					else
						cout<<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 ){	//leaf
			if( EEComp::eq( EMPTY, subroot->elems[1] ) ){
				if( EEComp::lt( e, subroot->elems[0] ) ){
					subroot->elems[1] = subroot->elems[0];
					subroot->elems[0] = e;
				}else
					subroot->elems[1] = e;
			}else
				splitNode( 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 );
			else
				insertHelp( 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;
				}
			}else
				splitNode( 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 node
				if( !EEComp::eq( EMPTY, subroot->elems[1] ) ){
					 subroot->elems[0]=subroot->elems[1];
					 subroot->elems[1]= EMPTY;
					}else
						subroot->elems[0] = EMPTY;
					return ;
			}else{		//if not leaf node, find a leaf node to take place of it
				TTNode* 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;
	}