Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/Binäre Suchbäume Einfügen

Einfügen

Das Finden der Einfügeposition erfolgt durch Suchen des Knotens, dessen Schlüsselwert größer als der einzufügende Schlüssel ist und der keinen linken Nachfolger hat oder durch Suchen des Knotens, dessen Schlüsselwert kleiner als der einzufügende Schlüssel ist und der keinen rechten Nachfolger hat. Das Einfügen erfolgt prinzipiell in 2 Schritten. Im ersten Schritt wird die Einfügeposition gesucht, sprich der Blattknoten mit dem nächstkleineren oder nächstgrößerem Schlüssel. Im zweiten Schritt wird ein neuer Knoten erzeugt und als Kindknoten des Knotens aus Schritt eins verlinkt. Wenn in Schritt eins der Schlüssel bereits existiert, dann wird nicht erneut eingefügt.

Programm in Java

 /* Einfügeposition suchen */
public boolean  insert(K k){ 
          TreeNode<K> parent = head;
          TreeNode<K> child = head.getRight();
          while (child != nullNode) {
              parent = child;
              int cmp = child.compareKeyTo(k);
              //Schlüssel bereits vorhanden
              if (cmp == 0)
                  return false;
              else if (cmp > 0)
                  child = child.getLeft();
              else
                  child = child.getRight();
           }
/* Neuen Knoten verlinken */  
  TreeNode<K> node = new TreeNode<K>(k);
            node.setLeft(nullNode);
            node.setRight(nullNode);
            if (parent.compareKeyTo(k) > 0)
                  parent.setLeft(node);
            else
                  parent.setRight(node);
            return true;

Literatur

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 14.3.2 zu finden.