Löschen in den sortierten binären Baum II

SortedBinaryTrees.om

PROCEDURE DeleteNode(VAR node: Node); VAR parent, lowest: Node; BEGIN IF node.left = NIL THEN node := node.right; ELSIF node.right = NIL THEN node := node.left; ELSE (* find lowest node on right branch ... *) lowest := node.right; parent := node; WHILE lowest.left # NIL DO parent := lowest; lowest := lowest.left; END; (* ... and move that upwards *) node.object := lowest.object; IF lowest = node.right THEN DeleteNode(node.right); ELSE DeleteNode(parent.left); END; END; END DeleteNode;