# Binary search tree: remove

## General Information

Algorithmic Problem: Sorted sequence:remove

Type of algorithm: loop

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

## Abstract view

Invariant After  interations:

1. The pointer  points to a tree node  on height level .
2. The key  is in range of , but .

Variant:  increased by .

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

1. It is .key and either .left = void or .left.key .
2. It is .key and either .right = void or .right.key = .

Remark: For example, the height of the subtree rooted at the node to which  points may be chosen as the induction parameter. For conciseness, the induction parameter is omitted in the following.

## Induction basis

Abstract view:

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

Implementation:

1. If root.key :
1. If root.left = void, set root := root.right.
2. Otherwise, if root.right = void, set root := root.left.
3. Otherwise, call method remove node with pointer root.
4. Terminate the algorithm and return true.
1. Otherwise set  root.

Proof: Obvious.

## Induction step

Abstract View:

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

Implementation:

1. If .key:
1. If .left = void, terminate the algorithm and return false.
2. Otherwise if .left.key :
1. If .left.left = void, set .left := p.left.right.
2. Otherwise, if .left.right = void, set .left := p.left.left.
3. Otherwise, call method remove node with pointer .left.
4. Terminate the algorithm and return true.
3. Otherwise (that is, .left  void and .left.key ), set .left.
2. Otherwise (that is, .key):
1. If .right = void, terminate the algorithm and return false.
2. Otherwise, if .right.key :
1. If .right.left = void, set .right .right.right.
2. Otherwise, if .right.right = void, set .right .right.left.
3. Otherwise, call method remove node with pointer .right.
4. Terminate the algorithm and return true.
3. Otherwise (that is, .right  void and .right.key ), set .right.

Correctness: Nothing to show.

## 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

## Complexity

Statement: The complexity is in  in the worst case, where  is the length of the sequence,  the height of the tree, and  the complexity of the comparison.

Proof: Obvious.