データ構造-Bツリー-Javaコード

8539 ワード

このBツリーJavaコードは完全に本人が手で打つことを実現します.
このコードの実現は『アルゴリズム導論』における擬似コード実現構想を参照した.
皆さんのご指摘を歓迎します.
PS:実はこのコードをアップロードした后にまた2回の修正を経て、とても知的障害の2 aと2 bの情况を理解して间违って、テストのデータの高さが足りなくて、テストしていません.Bツリーの削除ルールを復習していると、前の理解が通じないことに気づき、急いで修正し、2行のコードだけを変更しました.  ここでみんなに謝罪して、はっきりしないで伝わってきました.
コード:
package datastructure;

//        ,        ,   Integer  
//           k == key         ,         k == key    
public class BTree {

	private final static int T = 2;

	private final void READ(Entry e) {
		System.out.println("Read");
	}

	private final void WRITE(Entry e) {
		System.out.println("Write");
	}

	private final Entry ALLOCATE() {
		return new Entry();
	}

	private final void CLEAR(Entry e) {
		System.out.println("Clear");
	}

	private class Entry {
		public Integer[] key;
		public Entry[] child;
		public int num;
		public boolean leaf;

		public Entry() {
			key = new Integer[2 * T];
			child = new Entry[2 * T + 1];
			num = 0;
			leaf = false;
		}
	}

	private class EntryPosition {
		public Entry entry;
		public int position;

		public EntryPosition(Entry entry, int position) {
			this.entry = entry;
			this.position = position;
		}
	}

	Entry root;

	public BTree() {
		root = ALLOCATE();
		root.leaf = true;
	}

	public EntryPosition search(Integer k) {
		return doSearch(k);
	}

	private EntryPosition doSearch(Integer k) {
		Entry e = root;
		while (true) {
			int i = 1;
			while (i <= e.num && k < e.key[i]) {
				i++;
			}
			if (k == e.key[i]) {
				return new EntryPosition(e, i);
			} else if (i > e.num && e.leaf) {
				return null;
			} else {
				READ(e.child[i]);
				e = e.child[i];
			}
		}
	}

	public void insert(Integer k) {
		doInsert(k);
	}

	private void doInsert(Integer k) {
		Entry e = root;
		if (e.num == 2 * T - 1) {
			Entry entry = ALLOCATE();
			root = entry;
			entry.child[1] = e;
			doSplit(entry, 1);
			doInsertNotFull(entry, k);
		} else {
			doInsertNotFull(e, k);
		}
	}

	private void doInsertNotFull(Entry e, Integer k) {
		while (true) {
			int i = 1;
			while (i <= e.num && k > e.key[i]) {
				i++;
			}
			if (e.leaf) {
				for (int j = e.num; j >= i; j--) {
					e.key[j + 1] = e.key[j];
				}
				e.key[i] = k;
				e.num++;
				WRITE(e);
				System.out.println("insert complete!");
				return;
			} else {
				READ(e.child[i]);
				if (e.child[i].num == 2 * T - 1) {
					doSplit(e, i);
					if (k > e.key[i]) {
						i++;
					}
				}
				e = e.child[i];
			}
		}
	}

	private void doSplit(Entry e, int i) {
		Entry eLeft = e.child[i];
		Entry eRight = ALLOCATE();
		eRight.leaf = eLeft.leaf;
		for (int j = 1; j < T; j++) {
			eRight.key[j] = eLeft.key[j + T];
		}
		for (int j = 1; j <= T; j++) {
			eRight.child[j] = eLeft.child[j + T];
		}
		eRight.num = T - 1;
		eLeft.num = T - 1;
		for (int j = e.num; j >= i; j--) {
			e.key[j + 1] = e.key[j];
		}
		e.key[i] = eLeft.key[T];
		for (int j = e.num + 1; j >= i + 1; j--) {
			e.child[j + 1] = e.child[j];
		}
		e.child[i + 1] = eRight;
		e.num++;
		WRITE(e);
		WRITE(eLeft);
		WRITE(eRight);
	}

	public void delete(Integer k) {
		doDeleteStart(k);
	}

	private void doDeleteStart(Integer k) {
		Entry e = root;
		if (e.num == 0) {
			return;
		}
		doDelete(e, k);
		if (e.num == 0) {
			System.out.println("high down");
			READ(e.child[1]);
			root = e.child[1];
		}
		CLEAR(e);
		System.out.println("Delete complete");
	}

	private void doDelete(Entry e, Integer k) {
		System.out.println("start delete");
		while (true) {
			int i = 1;
			while (i <= e.num && k > e.key[i]) {
				i++;
			}
			if(e.leaf && k != e.key[i]){
				return ;
			}
			EntryPosition epn = new EntryPosition(e, i);
			if (i <= e.num && k == e.key[i]) {
				if (e.leaf) {// 1
					System.out.println("delete leaf");
					for (int j = i; j <= e.num - 1; j++) {
						e.key[j] = e.key[j + 1];
					}
					e.num--;
					return ;
				} else {// 2
					READ(e.child[i]);
					if (e.child[i].num >= T) {// 2a
						EntryPosition ep = getPrecuesor(epn);
						e.key[i] = k = ep.entry.key[ep.position];
						e = e.child[i];
					} else {
						READ(e.child[i + 1]);
						if (e.child[i + 1].num >= T) {// 2b
							EntryPosition ep = getSubsequent(epn);
							e.key[i] = k = ep.entry.key[ep.position];
							e = e.child[i+1];
						} else {// 2c
							Entry y = e.child[i];
							Entry z = e.child[i + 1];
							y.key[T] = e.key[i];
							for (int j = 1; j <= T - 1; j++) {
								y.key[T + j] = z.key[j];
							}
							for (int j = 1; j <= T; j++) {
								y.child[T + j] = z.child[j];
							}
							for (int j = i; j <= e.num - 1; j++) {
								e.key[j] = e.key[j + 1];
							}
							for (int j = i + 1; j <= e.num; j++) {
								e.child[j] = e.child[j + 1];
							}
							e.num--;
							y.num = 2 * T - 1;
							e = y;
							CLEAR(z);
						}
					}
				}
			} else {// 3
				READ(e.child[i]);
				if (e.child[i].num == T - 1) {
					boolean sign = false;
					if (i != 1) {// 3a
						READ(e.child[i - 1]);
						if (e.child[i - 1].num >= T) {
							Entry y = e.child[i];
							Entry z = e.child[i - 1];
							for (int j = y.num; j >= 1; j--) {
								y.key[j + 1] = y.key[j];
							}
							for (int j = y.num + 1; j >= 1; j--) {
								y.child[j + 1] = y.child[j];
							}
							y.key[1] = e.key[i - 1];
							y.child[1] = z.child[z.num + 1];
							e.key[i - 1] = z.key[z.num];
							y.num++;
							z.num--;
							e = e.child[i];
							sign = true;
						}
					}
					if (!sign && i != e.num + 1) {// 3a
						READ(e.child[i + 1]);
						if (e.child[i + 1].num >= T) {
							Entry y = e.child[i];
							Entry z = e.child[i + 1];
							y.key[y.num + 1] = e.key[i];
							y.child[y.num + 2] = e.child[1];
							e.key[i] = z.key[1];
							for (int j = 1; j <= z.num - 1; j++) {
								z.key[j] = z.key[j + 1];
							}
							for (int j = 1; j <= z.num; j++) {
								z.child[j] = z.child[j + 1];
							}
							y.num++;
							z.num--;
							e = e.child[i];
							sign = true;
						}
					}
					if (!sign) {// 3b
						if (i != 1) {
							READ(e.child[i - 1]);
							Entry y = e.child[i - 1];
							Entry z = e.child[i];
							y.key[T] = e.key[i - 1];
							for (int j = i - 1; j <= e.num - 1; j++) {
								e.key[j] = e.key[j + 1];
							}
							for (int j = 1; j <= z.num; j++) {
								y.key[T + j] = z.key[j];
							}
							for (int j = 1; j <= z.num + 1; j++) {
								y.child[T + j] = z.child[j];
							}
							e.num--;
							y.num = 2 * T - 1;
							CLEAR(z);
						} else {
							READ(e.child[i + 1]);
							Entry y = e.child[i];
							Entry z = e.child[i + 1];
							y.key[T] = e.key[i];
							for (int j = i; j <= e.num - 1; j++) {
								e.key[j] = e.key[j + 1];
							}
							for (int j = 1; j <= z.num; j++) {
								y.key[T + j] = z.key[j];
							}
							for (int j = 1; j <= z.num + 1; j++) {
								y.child[T + j] = z.child[j];
							}
							e.num--;
							y.num = 2 * T - 1;
							CLEAR(z);
						}
					}
				} else {
					e = e.child[i];
				}
			}
		}
	}

	private EntryPosition getPrecuesor(EntryPosition ep) {
		Entry e = ep.entry.child[ep.position];
		while (!e.leaf) {
			READ(e.child[e.num + 1]);
			e = e.child[e.num + 1];
		}
		return new EntryPosition(e, e.num);
	}

	private EntryPosition getSubsequent(EntryPosition ep) {
		Entry e = ep.entry.child[ep.position + 1];
		while (!e.leaf) {
			READ(e.child[1]);
			e = e.child[1];
		}
		return new EntryPosition(e, 1);
	}

	public void printInorderTraversal() {
		doPrintInorderTraversal(root);
		System.out.println("  comeplete!");
	}

	private void doPrintInorderTraversal(Entry e) {
		
		System.out.println(e.num);

		for (int i = 1; i <= e.num; i++) {
			if (!e.leaf) {
				READ(e.child[i]);
				doPrintInorderTraversal(e.child[i]);
			}
			System.out.print(e.key[i] + " ");
		}
		if (!e.leaf) {
			READ(e.child[e.num + 1]);
			doPrintInorderTraversal(e.child[e.num + 1]);
		}
	}

	public static void main(String[] args) {
		BTree bt = new BTree();
		bt.insert(7);
		bt.insert(13);
		bt.insert(16);
		bt.insert(24);
		bt.insert(1);
		bt.insert(3);
		bt.insert(4);
		bt.insert(5);
		bt.insert(10);
		bt.insert(11);
		bt.insert(14);
		bt.insert(15);
		bt.insert(18);
		bt.insert(19);
		bt.insert(20);
		bt.insert(21);
		bt.insert(22);
		bt.insert(25);
		bt.insert(26);
		bt.delete(16);
		bt.printInorderTraversal();
	}
}