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

	}

}