Tree 2-3-4 平衡搜索树

2-3-4 平衡树是一种搜索树。每个节点可能会有2,3,4个子节点，对应可能会有1,2,3个数据。子节点数＝数据数 ＋ 1，不可能有空节点。

插入数据时，数据均插入叶子节点，树在向下遍历以得到恰当的叶子节点时，每遇到满的节点，则进行节点分裂，当分裂向上累积致根节点位置，根节点分裂，所有叶子节点的层高都增加一层，以此原理来保证树的平衡。

此树没有实现删除数据的算法，如果需要，可考虑将数据标志为作废的方式，以避免真正的删除时的复杂。

插入的数据为了简便起见，假设均为Integer，且不会重复。

方法ordinal是升序打印，为的是测试。

Tree.main 函数提供一个简短的测试。

Node类为辅助类，管理单个节点的操作。

Tree为2-3-4树，管理节点与节点之间的操作。其他的平衡数可以参见红黑树

关于简单的二叉搜索树，请参见（Tree ）。

class Node {
	private Integer[] values = new Integer[3];	//存放数据
	private Node[] children = new Node[4];	//存放子节点引用
	private int size;	//当前有效数据数量
	private Node parent;	//当前节点的父节点
	Node() {}
	Node(Integer i) {
		values[0] = i;
		size = 1;
	}

	int insert(Integer value) {	//将数据插入有序数组
		assert size < values.length;
		int pos = size;
		while(pos > 0 && values[pos - 1] > value) {
			values[pos] = values[pos - 1];
			pos--;
		}
		values[pos] = value;
		size ++;
		return pos;
	}

	Node getChildByValue(Integer value) {	//根据给定数据的关键字，寻找恰当的子节点
		for(int i=0; i<size; i++) {
			if(values[i] > value) return children[i];
		}
		return children[size];
	}
	
	//根据给定子节点的索引值，得到对应的子节点
	Node getChildByIndex(int index) { return children[index]; }
	
	int find(Integer value) {
		for(int i=0; i<size; i++) {
			if(values[i].equals(value)) return i; 
		}
		return -1;
	}

	Integer removeMax() { return values[--size]; }	//删除当前节点内最大的数据，并返回之
	
	//根据给定子节点的索引值，删除与其的对应节点之间的父子关系
	Node removeChild(int index) {	
		Node result = children[index];
		if(result != null)result.parent = null;
		children[index] = null;
		return result;
	}
	
	//在当前节点中，在指定的索引值之后插入相应的子节点，之后的原有的子节点全部向后平移
	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;
	}
	
	//在当前节点中,在指定的索引值的位置置入相应子节点
	void setChild(int index, Node child) {
		children[index] = child;
		if(child != null) child.parent = this;
	}

	int size() { return size; }
	
	boolean isFull() { return size ==  values.length; }

	boolean isLeaf() { return children[0] == null; }

	Node getParent() { return parent; }

	Integer getValue(int index) { return values[index]; }

}
	

class Tree {
	private Node root = new Node();	//根节点
	public void insert(Integer value) {	//将数据插入树中
		Node current = root;	//从根向下开始寻找恰当的叶子节点
		while(!current.isLeaf()) {
			if(current.isFull()) current = split(current);	//如果下行过程遇到满的节点，分裂之
			current = current.getChildByValue(value);	
		}
	
		if(current.isFull()) {	//如果最终找到的叶子节点是满的，先分裂之
			current = split(current);	
			current = current.getChildByValue(value);	
		}
		current.insert(value);	//在叶子节点插入数据
	}

	public boolean contains(Integer value) {
		Node current  = root;
		while(!current.isLeaf()) {
			if(current.find(value) != -1) return true;
			current = current.getChildByValue(value);
		}
		return current.find(value) != -1;
	}

	public void ordinal() {	//安升序排列输入树中所有的数据
		ordinal(root);
	}

	private void ordinal(Node current) {
		for(int i=0; i<current.size(); i++) {
			if(!current.isLeaf()) ordinal(current.getChildByIndex(i));
			System.out.println(current.getValue(i));
		}
		if(!current.isLeaf()) ordinal(current.getChildByIndex(current.size()));
	}

	private Node split(Node current) {	//分裂算法
		Node parent = current.getParent();	//寻找当前节点的父节点
		if(parent == null) parent = new Node();
		//将当前节点拆分成左节点，右节点，中间的数据，其右节点是个新节点
		Node nodeLeft = current;
		Node nodeRight = new Node(current.removeMax());
		Integer middle = current.removeMax();
		//断开当前节点中的第2，3子节点,并加入右字节中
		Node child1 = nodeLeft.removeChild(2);
		Node child2 = nodeLeft.removeChild(3);
		nodeRight.setChild(0,child1);
		nodeRight.setChild(1,child2);

		int index = parent.insert(middle);	//将中间的数据加入其父节点，并得到插入的位置
		
		if(current == root) {	//如果当前节点是根节点，则在新的父节点中加入左右节点
			parent.setChild(0,nodeLeft);
			parent.setChild(1,nodeRight);
			root = parent; //重置根节点
		} else parent.insertChild(index,nodeRight);	//否则，在父节点中指定位置后插入右节点

		return parent;	//返回父节点
	}

	public static void main(String[] args) {
		Tree t = new Tree();
		t.insert(5);
		t.insert(6);
		t.insert(7);
		t.insert(8);
		t.insert(9);
		t.insert(10);
		t.insert(30);
		t.insert(50);
		t.insert(11);
		t.insert(17);
		t.insert(19);
		t.insert(54);
		t.insert(66);
		t.insert(72);
		t.insert(89);
		t.insert(92);
		t.insert(40);
		t.insert(28);
		t.insert(13);
		t.insert(14);
		t.insert(16);
		t.ordinal();
	}
}

 

评论

3 楼 arust 2008-05-28  

学习一下

2 楼 dboylx 2008-04-29  

支持~~~学习中，希望楼主继续~~

1 楼 桔红糕 2008-04-20  

oh my god一看就觉得有点头晕！！
但是～～
我一定认真研读，有不明白的地方还请shen老师耐心教诲！