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.

Induction step

Abstract View:

1. If the next node where to go does not exist or contains K, terminate the algorithm (and in the latter case, remove that node appropriately).
2. Otherwise, descend to that node.

Implementation:

1. I [math]\displaystyle{ K \lt p.key }[/math]:
   1. If [math]\displaystyle{ p.left = void }[/math], terminate the algorithm and return false.
   2. Otherwise if [math]\displaystyle{ p.left.key = K }[/math]:
      1. If [math]\displaystyle{ p.left.left = void }[/math], set [math]\displaystyle{ p.left := p.left.right }[/math].
      2. Otherwise, if [math]\displaystyle{ p.left.right = void }[/math], set [math]\displaystyle{ p.left := p.left.left }[/math].
      3. Otherwise, call method remove node with pointer p.left.
      4. Terminate the algorithm and return true.
   3. Otherwise (that is, [math]\displaystyle{ p.left \neq void }[/math] and [math]\displaystyle{ p.left.key \neq K }[/math]), set [math]\displaystyle{ p := p.left }[/math].
2. Otherwise (that is, [math]\displaystyle{ K \gt p.key }[/math]):
   1. If [math]\displaystyle{ p.right = void }[/math], terminate the algorithm and return false.
   2. Otherwise, if [math]\displaystyle{ p.right.key = K }[/math]:
      1. If [math]\displaystyle{ p.right.left = void }[/math], set [math]\displaystyle{ p.right = p.right.right }[/math].
      2. Otherwise, if [math]\displaystyle{ p.right.right = void }[/math], set [math]\displaystyle{ p.right = p.right.left }[/math].
      3. Otherwise, call method remove node with pointer p.right.
      4. Terminate the algorithm and return true.
   3. Otherwise (that is, [math]\displaystyle{ p.right \neq void }[/math] and [math]\displaystyle{ p.right.key \neq K }[/math]), set [math]\displaystyle{ p:= p.right }[/math].

Correctness: 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.

Pseudocode

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