Im linken Unterbaum liegen nur Datenelemente mit kleinerem Suchschlüssel, im rechten Unterbaum nur Elemente mit größerem Schlüsselwert als im Knoten selbst.Mit den Datentypen
TYPE stree = POINTER TO sknoten;
TYPE sknoten = RECORD key: keytype;
wert: atom;
left, right: stree;
END;
kann man nun das Eintragen eines Datenwertes x unter dem Schlüssel k
wie folgt realisieren:
PROCEDURE insert(k: keytype; x: atom; VAR b: stree);
BEGIN IF b = NIL
THEN NEW(b); b^.left := NIL; b^.right := NIL;
b^.key := k; b^.wert := x;
ELSIF k < b^.key THEN insert (k, x, b^.left)
ELSIF k > b^.key THEN insert (k, x, b^.right)
ELSE (* k = b^.key *) b^.wert := x;
END;
END insert;
Beim Eintragen in einen noch leeren Baum wird der Baum neu erzeugt;
und wenn der Schlüssel im Baum noch nicht vorkommt,
so landen wir beim Absteigen in die Teilbäume irgendwann
bei einem Blatt, an welches dann ein neues Datenelement
als Unterbaum angehängt wird.
Wir haben hier vorausgesetzt, daß ein Datenwert, dessen Schlüssel bereits belegt ist, durch einen neuen Wert überschrieben werden soll; ist das nicht erwünscht, so wäre im ELSE-Zweig stattdessen eine geeignete Fehlermeldung zu erzeugen, oder die Tatsache anderweitig, etwa über einen Ergebnisparameter, zurückzumelden.