A234Tree.java

Go to the documentation of this file.

package aud;
 
import aud.util.Graphvizable;
 
public class A234Tree<Key extends Comparable<Key>> implements Graphvizable {
 
  KTreeNode<Key> root_;
  boolean        top_down_ = true;
 
  public A234Tree() {
    root_=new KTreeNode<Key>();
  }
  public A234Tree(boolean top_down) {
    this();
    top_down_=top_down;
  }
 
 
  public Key find(Key key) {
    return root_.find(key);
  }
 
  public boolean insert(Key key) {
    if (top_down_)
      return insert_top_down(root_,key);
    else
      return insert_bottom_up(root_,key);
  }
 
  protected void split_bottom_up(KTreeNode<Key> node, int pos) {
    if (node.getK()>4) { // CHEATING: we created and split a 5-node!
 
      onSplit(node);
 
      node.split(2 + (pos<2 ? 1 : 0));
 
      if (node.parent_!=null) {
        int i=node.parent_.getIndexOfChild(node);
        assert (i>=0);
        node.parent_.mergeChild(i);
        node.parent_.checkConsistency();
 
        split_bottom_up(node.parent_,i); // eventually split parent
      }
    }
  }
 
  protected KTreeNode<Key> split_top_down(KTreeNode<Key> node) {
    if (node.getK()>3) {
 
      onSplit(node);
 
      node.split(2);
 
      if (node.parent_!=null) {
        int i=node.parent_.getIndexOfChild(node);
        assert (i>=0);
        node.parent_.mergeChild(i);
        node.parent_.checkConsistency();
 
        assert(node.parent_.getK()<=4) :
        "parent was not a 4-node (top-down split)";
 
        return node.parent_; // split: continue inserting at parent
      }
    }
    return node;             // no split: just continue
  }
 
  protected void onSplit(KTreeNode<Key> node) {
  }
 
  protected boolean insert_bottom_up(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) {
 
          // Note: We pass the insertion index i-1 (and likewise k below)
          //       such that split_bottom_up() can determine correct the index
          //       of the element that is to be "pulled up":
          //       In a classic implementation this happens (recursively) *before*
          //       inserting. Here, we allow a temporary 5-node and merge after
          //       insertion at the price that not always the second element
          //       will be "pulled up".
 
          node.insert(key,i-1);
          split_bottom_up(node,i-1);
          return true;
 
        } else
          return insert_bottom_up(node.getChild(i-1),key); // recursive find
      }
    }
 
    int k=node.getK()-1;
    KTreeNode<Key> right=node.getChild(k);
    if (right!=null)
      return insert_bottom_up(right,key);                 // recursive find
 
    node.insert(key,k);
    split_bottom_up(node,k);
 
    return true;
  }
 
  protected boolean insert_top_down(KTreeNode<Key> node, Key key) {
    node=split_top_down(node);
 
    // 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) {
          // ASSERT
          node.insert(key,i-1);
          return true;
 
        } else {
          return insert_top_down(node.getChild(i-1),key); // recursive find
        }
      }
    }
 
    KTreeNode<Key> right=node.getChild(node.getK()-1);
    if (right!=null)
      return insert_top_down(right,key);                 // recursive find
 
    node.insert(key,node.getK()-1);
 
    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) {
    A234Tree<String> tree=new A234Tree<String>();
 
    tree.insert("b");
    tree.checkConsistency();
    tree.insert("c");
    tree.checkConsistency();
    tree.insert("a");
    tree.checkConsistency();
    tree.insert("d");
    tree.checkConsistency();
    tree.insert("e");
    tree.checkConsistency();
    tree.insert("f");
    tree.checkConsistency();
    tree.insert("g");
    tree.checkConsistency();
 
    aud.util.DotViewer.displayWindow(tree,"234 tree");
    System.out.println(tree.toTikZ());
 
    // aud.util.DotViewer.displayWindow(tree,"234 tree");
  }
}