Insertion

To insert a new value "value" into a binary search tree T, we use the procedure TREE_INSERT. This procedure receives the value to insert and the tree pointer T. It traverses the tree recursively until it finds the right place of insertion, and updates the tree structure accordingly.

The pseudo-code shown below illustrates how TREE_INSERT works. The procedure starts at the root of the tree and traces a recursive path downward. The if statement at line 3 tests if the value to be inserted is less than the actual value in the node pointed by T. If this condition is true, the procedure calls itself recursively, but this time it passes the left subtree of T as a parameter. The reason for that follows straight from the Binary Search Tree property, which states that smaller values should always be left-descendents of their respective ancestors. Conversely, if value is greater than the value of T, it passes the right subtree of T as a parameter for the next recursive call in line 5. TREE_INSERT terminates after it finds a NIL child (a new leaf is always created as a result of this procedure) and it backtracks from its recursive calls, updating the tree structure.


Pseudo-Code

TREE_INSERT (T, value)
begin
1. if (T = NIL) then
2.     T = alloc_node(NIL);
3. else if (val < T->value) then
4.        TREE_INSERT (T->left, val);
5.      else TREE_INSERT(T->right, val);
6. end.

Example

The following images were created for the application using Macromedia Director 4.0.


Previous Page
Next Page
Return to Main Page