# Binary search tree: remove node

## General Information

Algorithmic problem: See the remark clause of Binary Search Tree; pointer $p$ as defined there is the input.

Prerequisites: $p$.left $\neq$ void.

Type of algorithm: loop

Auxiliary data: A pointer $p'$ of type "pointer to a binary search tree node of type $\mathcal{K}$."

## Abstract View

Invariant:

1. The immediate predecessor of K is in the range of $p'$.
2. It is $p'$.right $\neq$ void.

Variant: The pointer $p'$ descends one level deeper, namely to $p$'.right.

Break condition: It is $p'$.right.right = void.

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: If $p.left$ is the immediate predecessor of K, overwrite K by its immediate predecessor and terminate; otherwise, initialize $p'$.

Implementation:

1. If $p$.left.right = void:
1. Set $p$.key := p.left.key.
2. Set $p$.left := p.left.left.
3. Terminate the algorithm.
2. Otherwise, set $p'$ := p.left.

Proof: Obvious.

## Induction Step

Abstract view: If $p'$.right.key is the immediate predecessor of $K$, overwrite $K$ by its immediate predecessor and terminate; otherwise, let $p'$ descend one level deeper.

Implementation:

1. If $p'$.right.right = void:
1. Set $p$.key := $p'$.right.key.
2. Set $p'$.right := $p'$.right.left.
3. Terminate the algorithm.
2. Set $p':=p'$.right.

Correctness: Obvious.

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