Binary search tree: remove node

From Algowiki
Jump to: navigation, search

General Information

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

Prerequisites: [math]p[/math].left [math]\neq[/math] void.

Type of algorithm: loop

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

Abstract View

Invariant:

  1. The immediate predecessor of K is in the range of [math]p'[/math].
  2. It is [math]p'[/math].right [math]\neq[/math] void.

Variant: The pointer [math]p'[/math] descends one level deeper, namely to [math]p[/math]'.right.

Break condition: It is [math]p'[/math].right.right = void.

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

Induction Basis

Abstract view: If [math]p.left[/math] is the immediate predecessor of K, overwrite K by its immediate predecessor and terminate; otherwise, initialize [math]p'[/math].

Implementation:

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

Proof: Obvious.

Induction Step

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

Implementation:

  1. If [math]p'[/math].right.right = void:
    1. Set [math]p[/math].key := [math]p'[/math].right.key.
    2. Set [math]p'[/math].right := [math]p'[/math].right.left.
    3. Terminate the algorithm.
  2. Set [math]p':=p'[/math].right.

Correctness: Obvious.

Complexity

Statement: The complexity is in [math]\mathcal{O}(T\cdot h)\subseteq\mathcal{O}(T\cdot n)[/math] in the worst case, where [math]n[/math] is the length of the sequence, [math]h[/math] the height of the tree, and [math]T[/math] the complexity of the comparison.

Proof: Obvious.