btree.java

数据结构B-TREE的java实现



public class BTree<T>
{
	private Entry<T> root = null;
	private int degree;

	public BTree(int t)
	{
		degree = t;
	}

	public <T extends Comparable<? super T>> Entry<T> search(Entry<T> x, T k)
	{
		int i = 1;
		while (i <= x.keyNum && k.compareTo((x.key)[i - 1]) > 0)
			i++;
		if (i <= x.keyNum && k.compareTo((x.key)[i - 1]) == 0)
			return x;
		if (x.isLeaf)
			return null;
		else if ((x.child)[i - 1] != null)
			return search((x.child)[i - 1], k);
		else
			return null;
	}

	private void splitChild(Entry<T> x, int i, Entry<T> y)
	{
		Entry<T> z = new Entry<T>(degree);
		z.isLeaf = y.isLeaf;
		z.keyNum = degree - 1;
		for (int j = 0; j < degree - 1; j++)
		{
			(z.key)[j] = (y.key)[degree + j];
			(y.key)[degree + j] = null;
		}
		if (!y.isLeaf)
		{
			for (int j = 0; j <= degree - 1; j++)
			{
				(z.child)[j] = (y.child)[degree + j];
				(y.child)[degree + j] = null;
			}
		}
		y.keyNum = degree - 1;
		for (int j = x.keyNum; j > i; j--)
			(x.child)[j + 1] = (x.child)[j];
		(x.child)[i + 1] = z;
		for (int j = x.keyNum; j > i; j--)
			(x.key)[j] = (x.key)[j - 1];
		(x.key)[i] = (y.key)[degree - 1];
		(y.key)[degree - 1] = null;
		x.keyNum++;
	}

	public void insert(T k)
	{
		if (root == null)
			root = new Entry<T>(degree);
		Entry<T> r = root;
		if (r.keyNum == 2 * degree - 1)
		{
			Entry<T> z = new Entry<T>(degree);
			z.isLeaf = false;
			root = z;
			z.child[0] = r;
			splitChild(z, 0, r);
			insertNonFull(z, k);
		}
		else
			insertNonFull(r, k);
	}

	private void insertNonFull(Entry<T> x, T k)
	{
		int i = x.keyNum;
		Comparable<T> key = (Comparable<T>) k;
		if (x.isLeaf)
		{
			while (i >= 1 && key.compareTo((x.key)[i - 1]) < 0)
			{
				(x.key)[i] = (x.key)[i - 1];
				i--;
			}
			(x.key)[i] = k;
			x.keyNum++;
		}
		else
		{
			while (i >= 1 && key.compareTo((x.key)[i - 1]) < 0)
				i--;
			if ((x.child)[i].keyNum == 2 * degree - 1)
			{
				splitChild(x, i, (x.child)[i]);
				if (key.compareTo((x.key)[i]) > 0)
					i++;
			}
			insertNonFull((x.child)[i], k);
		}
	}

	public void delete(Entry<T> x, T k)
	{
		Comparable<T> key = (Comparable<T>) k;
		if (isInside(x, k))
		{
			int i = x.keyNum;
			while (i >= 1 && key.compareTo((x.key)[i - 1]) < 0)
				i--;
			if (x.isLeaf)
			{
				for (int j = i - 1; j < x.keyNum - 1; j++)
					(x.key)[j] = (x.key)[j + 1];
				(x.key)[x.keyNum - 1] = null;
				x.keyNum--;
			}
			else
			{
				if ((x.child)[i - 1].keyNum >= degree)
				{
					Entry<T> r = (x.child)[i - 1];
					while (!r.isLeaf)
					{
						r = (r.child)[r.keyNum];
					}
					T predecessor = (r.key)[r.keyNum - 1];
					(x.key)[i - 1] = predecessor;
					delete(r, predecessor);
				}
				else
				{
					if ((x.child)[i].keyNum >= degree)
					{
						Entry<T> r = (x.child)[i];
						while (!r.isLeaf)
						{
							r = (r.child)[0];
						}
						T predecessor = (r.key)[0];
						(x.key)[i] = predecessor;
						delete(r, predecessor);
					}
					else
					{
						mergeChild(x, i - 1, (x.child)[i - 1]);
						delete((x.child)[i - 1], k);
					}
				}
			}
		}
		else
		{
			Entry<T> rootK = findRootContainsK(x, k);
			Entry<T> r = null;
			if (!rootK.isLeaf)
			{
				for (int i = 0; i <= rootK.keyNum; i++)
				{
					if (isInside((rootK.child)[i], k))
					{
						r = (rootK.child)[i];
						break;
					}
				}
			}
			else
				r = rootK;
			if (rootK == x)
				rootK = r;
			if (rootK.keyNum >= degree)
				delete(r, k);
			else
			{
				int i = r.keyNum;
				while (i >= 1 && key.compareTo((r.key)[i - 1]) < 0)
					i--;
				Entry<T> p = findParentIn(x, rootK);
				int v = degree;
				for (int j = 0; j <= p.keyNum; j++)
				{
					if ((p.child)[j] == rootK)
					{
						v = j;
						break;
					}
				}
				if (v > 0 && (p.child)[v - 1].keyNum >= degree)
				{
					(r.key)[i - 1] = (p.key)[v];
					(p.key)[v] = (T) ((p.child)[v]).key[(p.child)[v].keyNum - 1];
					delete((p.child)[v], (p.key)[v]);
				}
				else
				{
					if (v < p.keyNum && (p.child)[v+1].keyNum >= degree)
					{
						(r.key)[i - 1] = (p.key)[v];
						(p.key)[v] = (T) (((p.child)[v + 1]).key)[0];
						delete((p.child)[v + 1], (p.key)[v]);
					}
					else
					{
						mergeChild(p, v, rootK);
						if(p.keyNum==0)
							root=p.child[v];
						delete(rootK, k);
					}
				}
			}
		}
	}

	private Entry<T> findParentIn(Entry<T> x, Entry<T> y)
	{
		if (x != null && y != null)
		{
			for (int i = 0; i <= x.keyNum; i++)
			{
				if (y == (x.child)[i])
				{
					return x;
				}
				return findParentIn((x.child)[i], y);
			}
		}
		return null;
	}

	private Entry<T> findRootContainsK(Entry<T> x, T k)
	{
		for (int i = 0; i <= x.keyNum; i++)
		{
			if (isInside(x.child[i], k))
			{
				return x;
			}
			if (!x.child[i].isLeaf)
				return findRootContainsK(x.child[i], k);
		}
		return null;
	}

	private boolean isInside(Entry<T> x, T k)
	{
		Comparable<T> key = (Comparable<T>) k;
		for (int i = 0; i < x.keyNum; i++)
		{
			if (key.compareTo(x.key[i]) == 0)
				return true;
		}
		return false;
	}

	private void mergeChild(Entry<T> x, int i, Entry<T> y)
	{
		Entry<T> z = (x.child)[i + 1];
		(y.key)[degree - 1] = (x.key)[i];
		for (int j = 0; j < degree - 1; j++)
		{
			(y.key)[degree + j] = (z.key)[j];
		}
		if (!z.isLeaf)
		{
			for (int j = 0; j < degree; j++)
			{
				(y.child)[degree + j] = (z.child)[j];
			}
		}
		(x.child)[i + 1] = null;
		for(int j=i+1;j<x.keyNum;j++)
			(x.child)[j]=(x.child)[j+1];
		(x.child)[x.keyNum]=null;
		y.keyNum = 2 * degree - 1;
		for (int j = i; j < x.keyNum; j++)
		{
			(x.key)[i] = (x.key)[i + 1];
		}
		(x.key)[x.keyNum - 1] = null;
		x.keyNum--;
	}

	static final class Entry<T>
	{
		int keyNum;
		boolean isLeaf;
		T[] key;
		Entry[] child;
		Entry parent;

		Entry(int t)
		{
			keyNum = 0;
			isLeaf = true;
			key = (T[]) (new Object[2 * t - 1]);
			child = new Entry[2 * t];
			parent = null;
		}
	}

}