# 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 of type $\mathcal{K}$."

## Abstract view

Invariant After $i \geq 0$ 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 $p.key \neq K$.

Variant: $i$ increased by $1$.

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

1. It is $K \lt p$.key and either $p$.left = void or $p$.left.key $= K$.
2. It is $K \gt p$.key and either $p$.right = void or $p$.right.key = $K$.

Remark: For example, the height of the subtree rooted at the node to which $p$ 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 $K$, remove this occurrence of $K$.
2. Otherwise, initialize $p$ so as to point to the root.

Implementation:

1. If root.key $= K$:
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 $p :=$ root.

Proof: Obvious.

## 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. If $K \lt p$.key:
1. If $p$.left = void, terminate the algorithm and return false.
2. Otherwise if $p$.left.key $= K$:
1. If $p$.left.left = void, set $p$.left := p.left.right.
2. Otherwise, if $p$.left.right = void, set $p$.left := p.left.left.
3. Otherwise, call method remove node with pointer $p$.left.
4. Terminate the algorithm and return true.
3. Otherwise (that is, $p$.left $\neq$ void and $p$.left.key $\neq K$), set $p := p$.left.
2. Otherwise (that is, $K \gt p$.key):
1. If $p$.right = void, terminate the algorithm and return false.
2. Otherwise, if $p$.right.key $= K$:
1. If $p$.right.left = void, set $p$.right $=p$.right.right.
2. Otherwise, if $p$.right.right = void, set $p$.right $= p$.right.left.
3. Otherwise, call method remove node with pointer $p$.right.
4. Terminate the algorithm and return true.
3. Otherwise (that is, $p$.right $\neq$ void and $p$.right.key $\neq K$), set $p:= p$.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 $\mathcal{O}(T\cdot h)\subseteq\mathcal{O}(T\cdot n)$ in the worst case, where $n$ is the length of the sequence, $h$ the height of the tree, and $T$ the complexity of the comparison.

Proof: Obvious.