Einfügen

insert (Knoten t, Key k) {
  if t ist kein Blatt { 
    if ( k < t.key ) { 
      insert (t.left, k);
    } else {
      insert (t.right, k);
    } 
  } else {
    if ( k < t.key ) {
      t.left = new Blatt (k);
    } else {
      t.right = new Blatt (k);
    } 
} }