Binary search tree: insert

General Information

Algorithmic problem: Sorted sequence: insert

Type of algorithm: loop

Auxiliary data: A pointer p of type "pointer to binary search tree node of type [math]\displaystyle{ \kappa }[/math]".

Abstract View

Invariant: After [math]\displaystyle{ i \geq 0 }[/math] iterations:

1. The pointer p points to a tree node v on height level i.
2. The Key K is in the range of v.

Variant: i increased by 1.

Break condition: One of the following two conditions is fulfilled:

1. It is [math]\displaystyle{ p.key \geq K }[/math] and [math]\displaystyle{ p.left = void }[/math].
2. It is [math]\displaystyle{ p.key \leq K }[/math] and [math]\displaystyle{ p.right = void }[/math].

Pseudocode

TREE-INSERT(T, z)

y = Null

x = root(T)

while x ≠ NULL

y = x

if key[z] < key[x]

then x = left[x]

then x = right[x]

p[z] = y

if y = NULL

then root[T] = z //Tree was empty

else if key[z] < key[y]

then left[y] = z

else right[y] = z