2-3树实现分析

在2-3树中，每个内部节点（非叶子节点）有两个或三个孩子，而且所有叶子都在同一级别上。例如，图1显示高度为3的2-3树。包含两个孩子的节点称为2-节点，二叉树中的节点都是2-节点；包含三个孩子的节点称为3-节点。

图1：高度为3的2-3树
2-3树不是二叉树，其节点可拥有3个孩子。不过，2-3树与满二叉树相似。若某棵2-3树不包含3-节点，则看上去像满二叉树，其所有内部节点都可有两个孩子，所有的叶子都在同一级别。另一方面，2-3树的一个内部节点确实有3个孩子，故比相同高度的满二叉树的节点更多。高为h的2-3树包含的节点数大于等于高度为h的满二叉树的节点数，即至少有2^h-1个节点。换一个角度分析，包含n的节点的2-3树的高度不大于[log2(n+1)](即包含n个节点的二叉树的最小高度)。
由此可知，2-3树可用于ADT列表的实现。若2-3树排序节点，使之成为一棵查找树，就可以用来实现ADT表。下面是2-3树的递归定义，它指定了节点的顺序。
如果满足下面的条件之一，T就是一棵2-3树：
（1）T为空，即高为0的2-3树。
或者
（2）T的形式：

其中r是包含一个数据项的节点，TL和TR各是高为h-1的2-3树。此时，r中的查找关键字必须大于子树TL中的查找关键字，并小于TR中的查找关键字。
或者
（3）T的形式为：

其中，r是包含两个数据项的节点，而TM、TL和TR各是高为h-1的2-3树。此时，r中的较小查找关键字必须大于左子树TL中的各个查找关键字，并小于种子数TM中的各个查找关键字。r中的较大查找关键字必须大于中子树TM中的各个查找关键字，并小于右子树TR中的各个查找关键字。
由此定义，可推出将数据项放入2-3树节点中的规则：
（1）2-节点有两个孩子，必含一个数据项，其查找关键字大于左孩子的查找关键字，而小于右孩子的查找关键字，如图2-a所示：
（2）3-节点有三个孩子 ，必含两个数据项，其查找关键字S和L满足下列关系：S大于左孩子的查找关键字，而小于中孩子的查找关键字；L大于中孩子的查找关键字，而小于右孩子的查找关键字。如图2-b所示：
（3）叶子可以包含一个或两个数据项。

（a）2-节点（b） 3-节点

图2 ：2-3树的节点；

图3：一棵2-3树
这样，2-3树的项按查找关键字排序。例如，图3是一棵2-3树。
可用下面的c++语句表示2-3树的任何节点：

class TreeNode
{
	private:
		TreeItemType smallItem,largeItem;
		TreeNode *leftChildPtr,middleChildPtr,rightChildPtr;
		
		friend class TwoThreeTree;
};

当节点只包含一个数据项时，可将其入smallItem，并用leftChildPtr和middleChildPtr来指向节点的孩子。为安全起见，可将NULL放入rightChildPtr。
下面分析2-3树的遍历、检索、插入和删除操作。这些操作都是使用递归算法。通过将这些递归算法的基例定义为叶子，而不是空子树，可以避免受到现实细节的干预。但这样，算法必须假设不能将空树作为参数传递给它们。
遍历2-3树
可通过类似于中序遍历的方式。按有序的查找关键字顺序遍历2-3树

inorder(in ttTree:TwoThreeTree)	
//Traverse the noneempty 2-3 tree ,ttTree in sorted
//search-key order
{
	if(ttTree's root node r is a leaf)
		visit the data items
	else if(r has two data items)
	{
		inorder(left subtree of ttTree's root);
		visit the first data item
		inorder(middle subtree of ttTree's root);
		visit the last data item
		inorder(right subtree of ttTree's root);
	}
	else
	{
		inorder(left subtree of ttTree's root)
		visit the first data item
		inorder(middle subtree of tttree's root);
	}
}

查找2-3树
2-3树中的节点排序与二叉树中的排序相似，允许在2-3树中有效地查找某一项。实际上，有下面的伪码可以看到，2-3树的检索操作非常类似与二叉树的检索操作。

retrieveItem(in ttTree: TwoThreeTree,in searchKey :keyType,
		out treeItem:TTreeItemType):boollean
//retrieve into treeItem from a noneempty 2-3 tree ttTree
//the item whose search key equals searchkey,the operation fails if no
//such item exists ,the function returns true if the item is found ,
//false otherwise
{
	if(searchKey is in ttTree's root node r)
	{
		treeItem =the data portion of r
		return true;
	}
	else if(r is a leaf)
	{
		return false;
	}
	else if(r has two data items)
	{
		if(searchKey<smaller search key of r)
			return retrieve(r's left subtree,searchkey,treeitem)
		else if(searchKey<larger search key of r)
			return retrieve(r's middle subtree ,searchKey,
					treeItem);
		else
			return retrieve(r's right subtree,searchKey,
					treeItem)
	}
	else
	{
		if(searchKey<r's search key)
			return retrieve(r's left subtree,searchKey,treeItem);
		else
			return retrieve(r's middle subtree,searchKey,treeItem);
	}
}

插入算法
要将项I插入2-3树，首先定位查找I的操作将终止的叶子。将新项I插入叶子，若当前叶子包含两个项目，则任务完成。但若叶子包含三个项，则必须将其分为两个节点n1和n2。如图4所示。将最小项S放在n1，将最大项放在n2，将中间项M上移到叶子的双亲。结果，节点n1和n2成为双亲的孩子。若双亲只有三个孩子，并包含两个项目，则任务完成。但是，若双亲当前有四个孩子，并包含有三项，则需要拆分。

图4：在2-3树中拆分叶子
通过上述叶子操作的过程，拆分包含三个项的内部节点n，但必须考虑n的四个孩子。如图5所示，将n拆分为n1和n2，将n的最小项S放到n1，将n左面的两个孩子关联到n1。将n的最大项L放入n2，将n右边的两个孩子关联到n2，将n的中间项M上移到n的双亲。

图5 ：拆分2-3的内部节点
此后，拆分节点和将项上移到双亲的过程递归地进行，知道遇到这样一个节点：再插入前，它只有一个项，而在接纳新项后，只有两个项。注意，在前面的插入序列中，树的高度保持不变，一直是原始3 。一般情况下，只要在从根到插入新项的叶子的路径上，至少有一个节点只包含一个项，则插入将不会增加树的高度。因此，与基本二叉查找树的策略相比，2-3树的插入策略推迟了树的高度的增长。
当2-3树的高度增长时，则从项的顶部向下完成。如果从根到插入新项的叶子的路径上，每个节点包含两个项，则2-3树的高度将增长。在这种情况下，拆分节点以及将项上移到节点双亲的递归过程最终到达根r。此时，向其他任何内部节点一样，必须为r拆分为r1和r2。不过，必须新建一个包含r的中间项的节点，是这个节点成为n1和n2的双亲的节点。于是，新节点成为树的新项，如图6所示。

图6： 拆分2-3树的根

下面的算法总结整个插入策略：

insertItem(in ttTree::TwoThreeTree,in newitem :TreeItemType)
//insert newitem into a 2-3 tree ttTree whose Items have
//distinct search keys that differ from newitem's search key.
{
	Let's key be the search key of newitem
	Locate the leaf leafNode in which search key belongs
	Add newitem to leafnode

	if(leafNode now has three items)
		split(leafnode);
}
split(inout n:TreeNodek)
//splits node n ,which contains 3 items ,Node :if n
//is not a leaf ,it has 4 children .throws treeException
//if node allocation fails.
{
	if(n is the root)
		create a new nodes P(refine later to throws exception)
		if(allocate failed)
			throw 
	else
		Let P be the parent of the n
	Replaces node n with two node ,n1 and n2,so that p 
	is their parent

	Give n1 the item in n with the smallest search-key value
	Give n2 the item in n with the largest search-key value

	if(n is not a left)
	{
		n1 become the parent of n's two leftmost children
		n2 become the parent of n's two rightmost children
	}
	Move the item in n that has the middle search key value 
		up to p
	if(p now has three items)
		Split(p);
}

删除算法
总之，要从2-3树删除I项，首先定位包含它的节点n。如果n不是叶子，则查找I的中序后继，并交换I与中序后继。在交换后，删除总是从叶子开始。如果叶子包含除I之外的项。则只需删除I即可完成任务。但是，如果叶子只包含I，则删除I将导致I不包含数据项的叶子。此时，必须执行其他的一些操作，才能完成删除。
首先检查空叶子的兄弟。若其一个兄弟有两个项，则在兄弟，空叶子和叶子双亲之间重新分配数据项，如图7所示。若叶子的兄弟没有两个项，则将一个项从叶子的双亲下移到兄弟（之前，他有一个项，所以有放置另一个项的空间），并删除空叶子，以归并叶子与邻接兄弟，如果7-b所示。

如上所述，通过从节点n下移一个项，可能导致节点n不在包含数据项，而且只有一个孩子，若出现这种情况，则为n递归应用删除算法。如果n的一个兄弟包含两个项和三个孩子，则在节点n、兄弟和双亲之间重新分配项。另外，将兄弟的一个孩子给n,如图7-c所示。

若n的兄弟都没有两个项，则归并n与兄弟，如图7-d所示。换言之，从双亲下移一个项，并使兄弟接纳n的一个孩子（之前的兄弟只有一个项和两个孩子），然后删除空叶子。若归并导致n的双亲没有项，则为其递归地应用删除过程。

若继续归并，将导致根没有项并只有一个孩子，此时简单的删除根。执行这个步骤是，树的高度减1，如图7-e。

图7：（a）重新分配值；（b）归并叶子；（c）重新分配值和叶子；（d）归并内部节点；（e）删除根
下面是从2-3树删除项的算法的高级语句：

deleteItem(in ttTree:TwoThreeTree，in searchkey:KeyType)
	throw(Exception)
//Deletes from the 2-3 tree ttTree the item whose search key
//equals searchKey, throws exception if no such item exists
{
	Attempt to locate item theitem whose search key equals
		to searchkey
	if(theItem is not in a leaf)
	{
		Swap item theitem with its inorder successor,
		     which will be in a leaf leafNode
		//the deletion always begins at a leaf
		Delete item theItem from leaf leafNode
		if(theleaf now has no items)
			fix(theleaf);
	}
	else
		Throws Exception;
}
fix(in n :TreeNode)
//Completes the deletion when node n is empty by either
//removing the root ,redistributing values or merging
//nodes .Node :if n is internal ,it has one child
{
	if(n is the root)
		remove the root
	else
	{
		Let p be the parent of n

		if(some sibling of n has two items)
		{
			Distribute items appropriately among n 
			,the sibling and p
			if(n is internal)
				move the appropriate child from sibling
					to n
		}
		else//merge the node
		{
			choose an adjacent sibling s of n
			Bring the appropriate item down from p
			into s
			if(n is internal)
				move n's child to s
			remove node n
			if(n is now empty)
				fix(p);
		}
	}
}