Tree 2-3 平衡搜索树
与2-3-4树相似，2-3 平衡树是一种搜索树。
但由于每个节点最多有两个数据，分裂算法需要新插入数据的参与，这导致算法与2-3-4树有一定的差异。
每个节点可能会有2,3,4个子节点，对应可能会有1,2,3个数据。子节点数＝数据数 ＋ 1，不可能有空节点。插入数据时，树向下遍历以得到恰当的叶子节点时，数据均插入叶子节点，如果子节点需要分裂，则进行节点分裂，分裂产生的新数据向父节点插入，如果父节点是满的，则向上递归调用此过程。当根节点分裂，所有叶子节点的层高都增加一层，以此原理来保证树的平衡。因为分裂需要第三个数据，所以是在插入之后分裂节点的，这与2-3-4树的插入算法不同，此处采用添加临时数据，临时子节点的做饭以简化算法。但每个节点需要额外的空间来保存临时数据，临时子节点。
与2-3-4树不同，分裂的主体算法移至Node，这样编程相对简单。其他的平衡数可以参见红黑树
此树没有实现删除数据的算法，如果需要，可考虑将数据标志为作废的方式，以避免真正的删除时的复杂。插入的数据为了简便起见，假设均为Integer，且不会重复。
方法ordinal是升序打印，为的是测试。
Tree.main 函数提供一个简短的测试。
class Node {
private Integer[] values = new Integer[3]; //装数据
private Node[] children = new Node[4]; //装子节点
private Node parent;
private int size; //当前的有效数据的个数
Node() {}
Node(Integer value) {
values[0] = value;
size++;
}
Node getParent() { return parent; }
int find(Integer value) { //得到当前节点下要查找的数据的下标索引
for(int i=0; i<size; i++)
if(values[i].equals(value)) return i;
return -1;
}
Node getNextChild(Integer value) { //在当前的节点下根据关键数值查找合适的子节点
for(int i=0; i<size; i++)
if(value < values[i]) return children[i];
return children[size];
}
Node getChild(int index) {
return children[index];
}
boolean isLeaf() { return children[0] == null; }
boolean needSplit() { return size > 2; } //返回当前节点是否需要分裂
int size() { return size; }
Integer getValue(int index) {
return values[index];
}
int insert(Integer value) { //将数据插入当前节点的恰当位置，以保持数据的升序排序
int pos = size ;
while(pos > 0 && values[pos -1 ] > value) {
values[pos] = values[pos-1];
pos--;
}
values[pos] = value;
size++;
return pos;
}
void insertChild(int index, Node child) { //在指定的位置之后插入子节点，之后的子节点依次向后移动
for(int i=size; i>index + 1; i--) children[i] = children[i-1];
children[index + 1] = child;
if(child != null) child.parent = this;
}
Node disConnect(int index) { //断开指定位置的子节点
Node result = children[index];
if(result != null) result.parent = null;
children[index] = null;
return result;
}
void connect(int index, Node child) { //在指定位置连接子节点
children[index] = child;
if(child != null) child.parent = this;
}
Node split() {
assert needSplit();
Node left = this; //左节点
Integer middle = values[1]; //中间数值，将要提升至父节点
Node right = new Node(values[2]); //右节点
//调整左节点中的数据与有效数据大小
left.values[1] = null;
left.values[2] = null;
left.size = 1;
//如果没有父节点（此时当前节点一定为根节点），则创建新的父节点
if(parent == null) {
parent = new Node(middle);
parent.connect(0,left);
parent.connect(1,right);
} else { //否则在父节点中插入要提升的数值，并将新的子节点放入插入合适的位置
int index = parent.insert(middle);
parent.insertChild(index,right);
}
if(!isLeaf()) { //当前节点有子节点，则将子节点平分至两个分裂后两个新节点中
Node child1 = disConnect(2);
Node child2 = disConnect(3);
right.connect(0,child1);
right.connect(1,child2);
}
return parent;
}
}
class Tree {
private Node root = new Node(); //根节点
void insert(Integer value) {
Node current = root; //从根节点开始寻找恰当的叶子节点
while(!current.isLeaf()) current = current.getNextChild(value);
current.insert(value); //将数值插入叶子节点
if(current.needSplit()) split(current); //如果需要，则分裂叶子节点
}
void ordinal() {
ordinal(root); //打印
}
private void ordinal(Node node) { //按照升序遍历并打印数据
for(int i=0; i<node.size(); i++) {
if(!node.isLeaf()) ordinal(node.getChild(i));
System.out.println(node.getValue(i));
}
if(!node.isLeaf()) ordinal(node.getChild(node.size()));
}
boolean contains(Integer value) { //判断树中是否包含指定的关键值的字段
Node current = root;
while(!current.isLeaf()) {
if(current.find(value) != -1) return true;
else current = current.getNextChild(value);
}
return current.find(value) != -1;
}
private void split(Node node) {
Node parent = node.split(); //分裂当前的节点，并得到其父节点
if(node == root) root = parent; //如果当前节点是根节点，则重置根结点
if(parent.needSplit()) split(parent); //如果父节点需要分裂，则递归调用
}
public static void main(String[] args) {
Tree t = new Tree();
t.insert(50);
t.insert(51);
t.insert(52);
t.insert(53);
t.insert(54);
t.insert(55);
t.insert(56);
t.insert(57);
t.insert(17);
t.insert(87);
t.insert(27);
t.insert(67);
t.insert(97);
t.ordinal();
assert t.contains(67);
assert t.contains(17);
assert !t.contains(100);
}
}