1 介绍
2 总体设计
3 详细设计
1 介绍
2-3-4 树是像红黑树一样的自平衡树。2-3-4 树效率比红黑树低，但代码实现比红黑树容易。2-3-4 树常用语介绍B数的例子。下图（图1）是一棵2-3-4树：
图1
什么是B树？B树是一个节点可以拥有多于2个子节点的多叉树。B树常用于外部存储器的数据结构。
什么是2-3-4 树？2-3-4是指节点的儿子个数。2-3-4 树把数据存储在叫做元素的单独单元中，它们组合成节点，每个节点都是下列之一（性质1）： 2-节点，就是说，它包含1个元素和 2 个儿子，（A node with one data item always has two children） 3-节点，就是说，它包含2个元素和 3 个儿子，(A node with two data items always has three children) 4-节点，就是说，它包含3个元素和 4 个儿子 。(A node with three data items always has four children)
图2
节点与子节点按照下图方式组织（性质2）：
图3
2 总体设计
代码的设计可以看做解答数学题，为什么这样说呢？以2-3-4树来说，上面的2-3-4树介绍相当于数学中的已知条件，在已知条件下如何解决问题这个过程可以看做程序设计，所以程序设计其实就是求解问题的过程。数学解题与程序设计可能唯一不同的是，数学解题是用伪代码那样的语言，而程序设计使用编程语言，如java、C++等。
2-3-4树需要节点类来保存元素和其孩子节点的信息（Node）。元素有时候是一个包括很多信息的对象模型，例如人口普查中，人的信息包括年龄、性别、地址等等，所以元素也需要一个类DataItem。对节点的操作的类Tree234,和使用Tree234的例子的一个类Tree234App。
DataItem设计如下，为了简单，只包含一个属性dData。
public class DataItem
{
public long dData;
public DataItem(long dd)
{
this.dData=dd;
}
//dispaly item, format "/27"
public void displayItem()
{
System.out.println("/"+dData);
}
}
2.1 查找
问题：给定一个2-3-4树，如何查找给定元素？
求解：根据1中2-3-4树的介绍，可以利用2-3-4树的节点与子节点之间有图3的关系，这一特性求解该问题。
类似二叉查找树，从跟节点开始查找，根据查找元素和节点元素比较，如果在当前节点查到元素则返回该元素在所在节点的位置，如果当前节点没有改元素，则根据查找元素和当前节点元素比较结果来决定查找元素在哪个子节点。如果查找到叶子节点还没有查到元素，则返回没有查找到的标志。如图1，查找元素64。从根节点开始（50<64），然后找到子节点1（节点从0开始计数），在当前节点也没有找到64，而60<64<70,所以找到当前节点的子节点1作为当前节点，在当前节点元素中找到64。
伪代码设计如下
public int find(long key)
{
int childNumber; //record the result
Node curNode=root; //record current search node
while(true)
{
//if find within the node, return
if((childNumber=curNode.findItem(key))!=-1)
return childNumber;
//esle if node not find, node is leaf, not found
else if(curNode.isLeaf())
return -1;
else
curNode=getNextChild(curNode,key); //search deeper
}
} //end find()
下面讨论Tree234的设计
2.2 增加
问题：给定一个2-3-4树，如何插入元素后该树仍是2-3-4树？
求解：我们可以从结果中得到信息，即结果仍是一棵2-3-4树，所以结果仍要保证2-3-4树的2个特性（性质1和性质2）。增加元素总是插入叶子节点中。叶子节点 的3个元素分2种情况，一种是满元素（即已经有3个元素），另外一种是元素为满（即叶子节点的元素没有达到3个）。下面讨论这2种情况。
我们先来讨论简单的情况。
（1）叶子节点元素未满
这种情况比较简单，因为是在叶子节点插入元素，而叶子节点元素未满也没有子节点，插入的元素作为叶子节点的元素即可，也不会给变2-3-4树的结构，唯一需要给变的是按照升序排序叶子节点的元素可能需要移动其元素，所以主要的操作是插入元素。如下图插入元素18：
（2）叶子节点元素已满
如果叶子节点已满，怎么办？解决办法是拆分（split）该节点，这样可以保证2-3-4树的平衡性(即性质1)。不妨将满元素的节点元素记为A,B,C。按下列原则拆分该节点：
- 新建一个空节点，作为被拆分节点的兄弟节点，并放在被拆分节点的右边。
- 将元素C放到新建的空节点中。
- 将元素B放到被拆分节点的父亲节点中
- A保持原位置不变。
- 被拆分节点的最右端2个子节点（如下图中Z、W）从原来节点中分离出来，重新连接到新建的那个空节点作为该节点的子节点。（如下图）
（•A new, empty node is created. It’s a sibling of the node being split, and is placed to its right.
• Data item C is moved into the new node.
• Data item B is moved into the parent of the node being split.
• Data item A remains where it is.
• The rightmost two children are disconnected from the node being split and connected to the new node.）
在上述拆分原则中B移到拆分节点的父节点中，但是如果B已经是根节点，或者B有父节点但是父节点已经满元素怎么办？所以还需要分2种情况讨论。
- B是根节点
与上述介绍的拆分原则唯一不同的是拆分原则中的3，这里没有父亲节点我们需要新建一个节点，然后把B放入新建的节点中。如下图：
- B不是根节点，但是B的父节点满元素（如果B的父节点已满需要递归这一过程）
安装上述一般的拆分原则即可。下图是一个具体的例子（将99插入2-3-4树中）：
这一拆分过程主要的操作是：拆分节点(split)，重新建立孩子节点与父节点的连接关系（connect），在B插入父亲节点中的插入操作。
回想增加节点的整个过程，可以用下图概括：
增加元素时从叶子节点开始，如果需要拆分节点而B的父亲节点也是满元素，需要先拆分父亲节点，如此往复。这种从下自上（down-to-top）的拆分使问题变的复杂，我们逆向思维想一下。插入元素主要有2步骤：首先是查找元素，其次是插入元素。那么我们在从根节点到查找元素的这条路径中，将满元素的节点拆分就会方便后面插入元素，因为这样保证了从跟节点到插入元素位置的这条路径上的节点都不是满元素的。我们称这种拆分为自上而下的（top-to-down）。
程序伪代码设计如下：
public void insert(long dValue)
{
DataItem tempItem=new DataItem(dValue); //insert DataItem
Node curNode=root; //record current node
//find where to insert
while(true)
{
//node is full, split it
if(curNode.isFull())
{
split(curNode);
curNode=curNode.getParent();
curNode=getNextChild(curNode, dValue); //search once
}
//node is not full and is leaf
else if(curNode.isLeaf())
break;
//node is not full, not a leaf; so go to lower level
else
curNode=getNextChild(curNode, dValue);
} //end while
//insert item
curNode.insertItem(tempItem);
} //end isnert()
现在设计 Node节点，看到上述Tree234的伪代码中的涉及到Node的一些方法，这构成了对Node的需求，可见Node有以下方法：
curNode.findItem(key) // find the key item within the node curNode.isLeaf() // decide whether the node is leaf curNode.isFull() //decide whether the node is full, in other the node has three items curNode.getParent() // get the node's parent node curNode.insertItem(tempItem) //insert item in the node
3 详细设计
3.1 Node详细设计如下
public class Node {
//----------------------------------------------------------------------
// private property
//----------------------------------------------------------------------
//节点最大孩子数目
private static final int ORDER=4;
//节点中非空元素数目
private int numItems;
//节点的父亲节点
private Node parent;
//孩子节点
private Node childArray[] =new Node[ORDER];
//节点中所含最大非空元素数目
private DataItem itemArray[]=new DataItem[ORDER-1];
//----------------------------------------------------------------------
// constructor
//----------------------------------------------------------------------
//connect child to this node
public void connectChild(int childNum,Node child)
{
childArray[childNum] =child;
if(child!=null)
child.parent=this;
}
//----------------------------------------------------------------------
// APP
//----------------------------------------------------------------------
//disconnect child from this node, return it
public Node disconnectChild(int childNum)
{
Node tempNode=childArray[childNum];
childArray[childNum]=null;
return tempNode;
}
public Node getChild(int childNum)
{
return childArray[childNum];
}
public Node getParent()
{ return parent;}
public boolean isLeaf()
{
return (childArray[0]==null) ? true: false;
}
public int getNumItems()
{return numItems;}
public DataItem getItem(int index)
{return itemArray[index]; }
public boolean isFull()
{ return (numItems==ORDER-1) ? true: false; }
//return index of item(within node) if found, otherwise return -1
public int findItem(long key)
{
for(int j=0;j<ORDER-1;j++)
{
if(itemArray[j]==null)
break;
else if(itemArray[j].dData==key)
return j;
}
return -1;
}
public int insertItem(DataItem newItem)
{
//将设节点元素为满，即可能有1个或2个元素
numItems++;
for(int i=ORDER-2;i>=0;i--) //start on right
{
if(itemArray[i]==null) //examine items, if item null, go left one cell
continue;
else //if not null, compare items
{
if(newItem.dData<itemArray[i].dData) //if item within the Node is bigger
{
itemArray[i+1]=itemArray[i]; //shift it right
}
else
itemArray[i+1]=newItem; //insert new item
return i+1;
} //end else
} //end for
itemArray[0]=newItem; //shifted all items, insert new item
return 0;
}
//remove largest item
public DataItem removeItem()
{
//assume node not empty
DataItem temp=itemArray[numItems-1]; //save item
itemArray[numItems-1]=null; //disconnect it
numItems--; //one less item
return temp;
}
//format "/24/56/"
public void displayNode()
{
for(int j=0;j<numItems;j++)
itemArray[j].displayItem();
System.out.println("/");
}
}
3.2 Tree234详细设计如下
package zyang.tree.tree234;
/**
* @author yangzhong E-mail:yangzhonglive@gmail.com
* @version 1.0
* @date 2013-1-2 上午9:12:43
* @fuction 2-3-5 tree
*/
public class Tree234
{
//----------------------------------------------------------------------
// private property
//----------------------------------------------------------------------
//make root node
private Node root=new Node();
//----------------------------------------------------------------------
// APP
//----------------------------------------------------------------------
/**
* search the node with the key
* @param key
*
*
* @return item index within the node, if not found return -1
*/
public int find(long key)
{
Node curNode=root;
int childNumber;
while(true)
{
//if find within the node, return
if((childNumber=curNode.findItem(key))!=-1)
return childNumber;
//esle if node not find, node is leaf, not found
else if(curNode.isLeaf())
return -1;
else
curNode=getNextChild(curNode,key); //search deeper
} //end while
}
public void insert(long dValue)
{
DataItem tempItem=new DataItem(dValue);
Node curNode=root;
//find where to insert
while(true)
{
//if node is full, split it
if(curNode.isFull())
{
split(curNode);
curNode=curNode.getParent();
curNode=getNextChild(curNode, dValue); //search once
} //end if(node is full)
//if node is leaf and not full, insert item
else if (curNode.isLeaf())
break;
//if node is not full, not a leaf; so go to lower level
else
curNode=getNextChild(curNode, dValue);
} //end while
//insert new DataItem
curNode.insertItem(tempItem);
} //end insert()
public void dispalyTree()
{
recDisplayTree(root,0,0);
}
public void recDisplayTree(Node thisNode,int level,int childNumber)
{
System.out.println("level="+level+" child="+childNumber+" ");
thisNode.displayNode();
//call ourselves for each child of this node
int numItems=thisNode.getNumItems();
for(int j=0;j<numItems+1;j++)
{
Node nextNode=thisNode.getChild(j);
if(nextNode!=null)
recDisplayTree(nextNode,level+1,j);
else
return;
} //end for
} //end recDisplayTree()
//----------------------------------------------------------------------
// private method
//----------------------------------------------------------------------
//gets appropriate child of node during search for value
private Node getNextChild(Node node,long key)
{
//assumes node is not empty, not full,not a leaf
int numItems=node.getNumItems();
for(int i=0;i<numItems;i++)
{
if(key<node.getItem(i).dData)
return node.getChild(i);
} //end for
return node.getChild(numItems-1);
}
private void split(Node thisNode)
{
//assume node is full
DataItem itemB, itemC;
Node parent, child2, child3;
int itemIndex;
//remove items from this node
itemC=thisNode.removeItem();
itemB=thisNode.removeItem();
//remove children from this node
child2=thisNode.disconnectChild(2);
child3=thisNode.disconnectChild(3);
Node newRight=new Node(); //make new node
//if this node is the root
if (thisNode==root)
{
root=new Node(); //make new root
parent=root; //root is our parent
root.connectChild(0, thisNode); //connect to parent
}
else ///this node not the root
parent=thisNode.getParent();
//deal with parent
itemIndex=parent.insertItem(itemB); //item B to parent
int n=parent.getNumItems();
for(int j=n-1;j>itemIndex;j--) //move parent's connections after itemB one child to the right
{
Node temp=parent.disconnectChild(j);
parent.connectChild(j+1, temp);
} //end for
parent.connectChild(itemIndex+1, newRight); //connect newRight to parent
//deal with newRight
newRight.insertItem(itemC);
newRight.connectChild(0, child2);
newRight.connectChild(1, child3);
} //end split()
}
References
Data structure & algorithm in JAVA, Robert Lafore