BTree.java

Go to the documentation of this file.

package aud;
 
import aud.util.Graphvizable;
 
public class BTree<Key extends Comparable<Key>> implements Graphvizable {
 
  KTreeNode<Key> root_;
  int            m_;
 
  public BTree(int m) {
    root_=new KTreeNode<Key>();
    m_=m;
    assert(m_>0);
  }
 
  public  KTreeNode<Key> root() { return root_; }
 
  public int getOrder() { return 2*m_+1; }
 
  public Key find(Key key) {
    return root_.find(key);
  }
 
  public boolean insert(Key key) {
    return insert(root_,key);
  }
 
  protected void split(KTreeNode<Key> node) {
    if (node.getK()>2*m_+1) { // CHEATING: we created and split a (2*m+2)-node!
 
      onSplit(node);
 
      node.split(m_+1);
 
      if (node.parent_!=null) {
        int i=node.parent_.getIndexOfChild(node);
        assert (i>=0);
        node.parent_.mergeChild(i);
        node.parent_.checkConsistency();
 
        split(node.parent_); // eventually split parent
      }
    }
  }
 
  protected void onSplit(KTreeNode<Key> node) {
  }
 
  protected boolean insert(KTreeNode<Key> node, Key key) {
    // recursive find/insert (similar to KTreeNode#find)
    for (int i=1; i<node.getK(); ++i) {
      int cmp=node.compareKeys(key,node.getKey(i));
      if (cmp==0)
        return false; // key exists in tree
      else if (cmp<0) {
        if (node.getChild(i-1)==null) {
 
          node.insert(key,i-1);
          split(node);
          return true;
 
        } else
          return insert(node.getChild(i-1),key); // recursive find
      }
    }
 
    KTreeNode<Key> right=node.getChild(node.getK()-1);
    if (right!=null)
      return insert(right,key);                 // recursive find
 
    node.insert(key,node.getK()-1);
    split(node);
 
    return true;
  }
 
  @Override
  public String toDot() {
    return root_.toDot();
  }
 
  public String toTikZ() {
    return root_.toTikZ();
  }
 
  @Override public String toString() {
    return root_.toString();
  }
 
  public void checkConsistency() {
    // missing: check particular properties of 2-3-4-tree!
    root_.checkConsistency();
  }
 
  public static void main(String[] args) {
    BTree<Integer> tree=new BTree<Integer>(1);
 
    int data[]={1,5,2,6,7,4,8,3};
 
    for (int i : data) {
      tree.insert(i);
      System.out.println(tree.toTikZ()+"\n");
    }
 
    aud.util.DotViewer.displayWindow(tree,"B-tree");
  }
}