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].

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