Code-Bin #647 - b-tree

b-tree
Posted by: rhal | May 15, 2010 @ 7:05am

Java Code

package ads1ss10.pa1;

import java.util.ListIterator;

/**
 * B-Baum-Klasse die die fehlende Methode aus {@link AbstractBTree}
 * implementiert.
 * 
 * <p>
 * In dieser Klasse m&uuml;ssen Sie Ihren Code einf&uuml;gen und die Method
 * {@link #insert insert()} implementieren.
 * </p>
 * 
 * <p>
 * Sie k&ouml;nnen beliebige neue Variablen und Methoden in dieser Klasse
 * hinzuf&uuml;gen. Wichtig ist nur, dass die oben genannten Methoden
 * implementiert werden.
 * </p>
 */
public class BTree extends AbstractBTree {

/**
	 * Hier ist die richtige Stelle f&uuml;r Initialisierungen die Sie f&uuml;r
	 * Ihre Implementierung ben&ouml;tigen.
	 * 
	 * @param order
	 *            Ordnung des B-Baumes.
	 */
	public BTree(int order) {
		super(order);
		Helper.println("BTree order: " + order);
	}

/*
	 * (non-Javadoc)
	 * 
	 * @see ads1ss10.pa1.AbstractBTree#insert(int)
	 */
	@Override
	public void insert(int value) {
		Helper.println("insert: " + value);
		
		if(this.root == null) {
			this.root = new BNode(null);
			this.root.key.add(value);
			this.root.child.add(null);
			this.root.child.add(null);
		} else {
			insert_search(this.root, value);
		}
	}
	public void insert_search(BNode node, int value) {
		if(node.child.getFirst() != null) {
			ListIterator<Integer> ikey = node.key.listIterator();
			ListIterator<BNode> ichild = node.child.listIterator();
			int key = 0;
			for(int i=0; i < node.key.size(); i++) {
				key = ikey.next();
				BNode child = ichild.next();
				if(value < key) {
					insert_search(child,value);
					break;
				}
			}
			if(node.key.getLast() < value) {
				insert_search(node.child.getLast(),value);
			}
		} else {
			ListIterator<Integer> ikey = node.key.listIterator();
			int key = 0;
			for(int i=0; i < node.key.size(); i++) {
				key = ikey.next();

if(value < key) {
					node.key.add(i,value);
					node.child.add(null);
					break;
				}
			}
			if(node.key.getLast() < value) {
				node.key.add(node.key.size(),value);
				node.child.add(null);
			}
			if((this.order-1) < node.key.size()) {
				insert_split(node);
			}
		}
	}
	public void insert_split(BNode node) {
		int midindex = (int)(Math.floor(node.key.size()/2));
		int midvalue = node.key.get(midindex);
		if(node.parent == null) {
			BNode newRoot = new BNode(null);
			node.parent = newRoot;
			newRoot.child.add(node);
			this.root = newRoot;
			newRoot.key.add(midvalue);
		} else {
			ListIterator<Integer> ikey = node.parent.key.listIterator();
			int key = 0;
			for(int i=0; i < node.parent.key.size(); i++) {
				key = ikey.next();

if(midvalue < key) {
					node.parent.key.add(i,midvalue);
					break;
				}
			}
			if(node.parent.key.getLast() < midvalue) {
				node.parent.key.add(node.parent.key.size(),midvalue);
			}
		}
		node.key.remove(midindex);
		BNode leftNode = new BNode(null);
		for(int i=0; i < midindex; i++) {
			leftNode.key.add( node.key.getFirst() );
			leftNode.child.add( node.child.getFirst() );
			node.key.removeFirst();
			node.child.removeFirst();
		}
		leftNode.child.add( node.child.getFirst() );
		node.child.removeFirst();
		node.parent.child.add(node.parent.key.indexOf(midvalue),leftNode);
		leftNode.parent = node.parent;
		if((this.order-1) < node.parent.key.size()) {
			insert_split(node.parent);
		}
	}

/*
	 * (non-Javadoc)
	 * 
	 * Diese Methode dient nur als Beispiel und kann entfernt werden, wenn sie
	 * nicht benoetigt wird!
	 * 
	 * @see ads1ss10.pa1.AbstractBTree#traverseTree(ads1ss10.pa1.BNode,
	 * ads1ss10.pa1.BNode, int, int, boolean)
	 */
	@Override
	public void traverseTree(BNode node, BNode parent, int child_index,
			int depth, boolean end) {

if (node == null) {
			return;
		}

for (ListIterator<BNode> child_iterator = node.child.listIterator(); child_iterator
				.hasNext();) {
			BNode child = child_iterator.next();
			traverseTree(child, node, node.child.indexOf(child), depth + 1, end);
		}
	}
}

Syntax Highlighting

[Open in new window]

Author Comments

BTree.java creates a B-Tree consisting of BNodes. Those nodes a) contain a LinkedList of keys and b) a LinkedList of Child-BNodes. The compiler throws an INCONSISTENT Exception related to a node.parent entry, but I have no clue where the problem comes up.

Rating

4.49 / 8
55 Votes