Binary search tree: remove

General Information

Algorithmic Problem: Sorted Sequence:remove

Type of algorithm: loop

Auxiliary data: A pointer p of type "pointer to binary search tree node".

Abstract view

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

1. The pointer p points to a tree node v on height level i.
2. The key K is in range of p, but [math]\displaystyle{ p.key \neq K }[/math].

Variant: i increased by 1.

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

1. It is [math]\displaystyle{ K \lt p.key }[/math] and either [math]\displaystyle{ p.left = void }[/math] or [math]\displaystyle{ p.left.key = K }[/math].
2. It is [math]\displaystyle{ K \gt p.key }[/math] and either [math]\displaystyle{ p.right = void }[/math] or [math]\displaystyle{ p.right.key = K }[/math].

Induction basis

Abstract view:

1. If the root contains K, remove this occurrence of K.
2. Otherwise, initialize p so as to point to the root.

Implementation:

1. If [math]\displaystyle{ root.key = K }[/math]:
   1. If [math]\displaystyle{ root.left = void }[/math], set [math]\displaystyle{ root := root.right }[/math]
   2. Otherwise, if [math]\displaystyle{ root.right = void }[/math], set [math]\displaystyle{ root := root.left }[/math].
   3. Otherwise, call method remove node with pointer root.
   4. Terminate the algorithm and return true.

1. Otherwise set [math]\displaystyle{ p := root }[/math]

Proof: Nothing to show.

Complexity

Statement: Linear in the length of the sequence in the worst case (more precisely, linear in the height of the tree).

Proof: Obvious.

Implementation

TREE-DELETE(T,z)

if left[z] = NULL or right[z] = NULL

then y = z

else y = TREE-SUCCESSOR(z)

if left[y] ≠ NULL

then x = left[y]

else x = right[y]

if x ≠ NULL

then p[x] = p [y]

if p[y] = NULL

then root[T] = x

else if y = left[p[y]]

then left[p[y]] = x

else right[p[y]] = x

if y ≠ z

then key[z] = key[y]

copy y's satellite data into z

return y