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);}}?