更新时间：2024-06-13 15:59
2-3树是最简单的B-树（或-树）结构，其每个非叶节点都有两个或三个子女，而且所有叶都在统一层上。2-3树不是二叉树，其节点可拥有3个孩子。不过，2-3树与满二叉树相似。高为h的2-3树包含的节点数大于等于高度为h的满二叉树的节点数，即至少有2^h-1个节点。
2-3树是最简单的B-树（或-树）结构，其每个非叶节点都有两个或三个子女，而且所有叶都在统一层上。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个节点的二叉树的最小高度)。
例如，下图显示高度为3的2-3树。包含两个孩子的节点称为2-节点，二叉树中的节点都是2-节点；包含三个孩子的节点称为3-节点。
将数据项放入2-3树节点中的规则是：
（1）2-节点有两个孩子，必含一个数据项，其查找关键字大于左孩子的查找关键字，而小于右孩子的查找关键字。
（2）3-节点有三个孩子 ，必含两个数据项，其查找关键字S和L满足下列关系：S大于左孩子的查找关键字，而小于中孩子的查找关键字；L大于中孩子的查找关键字，而小于右孩子的查找关键字。
（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树的检索操作非常类似与二叉树的检索操作。
代码如下：
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 return retrieve(r's left subtree,searchkey,treeitem) else if(searchKey return retrieve(r's middle subtree ,searchKey, treeItem); else return retrieve(r's right subtree,searchKey, treeItem) } else { if(searchKey return retrieve(r's left subtree,searchKey,treeItem); else return retrieve(r's middle subtree,searchKey,treeItem); } } 要将项I插入2-3树，首先定位查找I的操作将终止的叶子。将新项I插入叶子，若当前叶子包含两个项目，则任务完成。但若叶子包含三个项，则必须将其分为两个节点n1和n2。将最小项S放在n1，将最大项放在n2，将中间项M上移到叶子的双亲。结果，节点n1和n2成为双亲的孩子。若双亲只有三个孩子，并包含两个项目，则任务完成。但是，若双亲当前有四个孩子，并包含有三项，则需要拆分。 上述叶子操作的过程，拆分包含三个项的内部节点n，但必须考虑n的四个孩子。如图5所示，将n拆分为n1和n2，将n的最小项S放到n1，将n左面的两个孩子关联到n1。将n的最大项L放入n2，将n右边的两个孩子关联到n2，将n的中间项M上移到n的双亲。 此后，拆分节点和将项上移到双亲的过程递归地进行，知道遇到这样一个节点：再插入前，它只有一个项，而在接纳新项后，只有两个项。注意，在前面的插入序列中，树的高度保持不变，一直是原始3 。一般情况下，只要在从根到插入新项的叶子的路径上，至少有一个节点只包含一个项，则插入将不会增加树的高度。因此，与基本二叉查找树的策略相比，2-3树的插入策略推迟了树的高度的增长。 当2-3树的高度增长时，则从项的顶部向下完成。如果从根到插入新项的叶子的路径上，每个节点包含两个项，则2-3树的高度将增长。在这种情况下，拆分节点以及将项上移到节点双亲的递归过程最终到达根r。此时，向其他任何内部节点一样，必须为r拆分为r1和r2。不过，必须新建一个包含r的中间项的节点，是这个节点成为n1和n2的双亲的节点。于是，新节点成为树的新项。 代码如下： 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 return retrieve(r's left subtree,searchkey,treeitem) else if(searchKey return retrieve(r's middle subtree ,searchKey, treeItem); else return retrieve(r's right subtree,searchKey, treeItem) } else { if(searchKey return retrieve(r's left subtree,searchKey,treeItem); else return retrieve(r's middle subtree,searchKey,treeItem); } }