Binary search tree: remove

From Algowiki
Jump to: navigation, search

General Information

Algorithmic Problem: Sorted sequence:remove

Type of algorithm: loop

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

Abstract view

Invariant After [math]i \geq 0[/math] interations:

  1. The pointer [math]p[/math] points to a tree node [math]v[/math] on height level [math]i[/math].
  2. The key [math]K[/math] is in range of [math]p[/math], but [math]p.key \neq K[/math].

Variant: [math]i[/math] increased by [math]1[/math].

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

  1. It is [math]K \lt p[/math].key and either [math]p[/math].left = void or [math]p[/math].left.key [math]= K[/math].
  2. It is [math]K \gt p[/math].key and either [math]p[/math].right = void or [math]p[/math].right.key = [math]K[/math].

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:

  1. If the root contains [math]K[/math], remove this occurrence of [math]K[/math].
  2. Otherwise, initialize [math]p[/math] so as to point to the root.

Implementation:

  1. If root.key [math]= K[/math]:
    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 [math]p :=[/math] root.

Proof: Obvious.

Induction step

Abstract View:

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

Implementation:

  1. If [math]K \lt p[/math].key:
    1. If [math]p[/math].left = void, terminate the algorithm and return false.
    2. Otherwise if [math]p[/math].left.key [math]= K[/math]:
      1. If [math]p[/math].left.left = void, set [math]p[/math].left := p.left.right.
      2. Otherwise, if [math]p[/math].left.right = void, set [math]p[/math].left := p.left.left.
      3. Otherwise, call method remove node with pointer [math]p[/math].left.
      4. Terminate the algorithm and return true.
    3. Otherwise (that is, [math]p[/math].left [math]\neq[/math] void and [math]p[/math].left.key [math]\neq K[/math]), set [math]p := p[/math].left.
  2. Otherwise (that is, [math]K \gt p[/math].key):
    1. If [math]p[/math].right = void, terminate the algorithm and return false.
    2. Otherwise, if [math]p[/math].right.key [math]= K[/math]:
      1. If [math]p[/math].right.left = void, set [math]p[/math].right [math]=p[/math].right.right.
      2. Otherwise, if [math]p[/math].right.right = void, set [math]p[/math].right [math]= p[/math].right.left.
      3. Otherwise, call method remove node with pointer [math]p[/math].right.
      4. Terminate the algorithm and return true.
    3. Otherwise (that is, [math]p[/math].right [math]\neq[/math] void and [math]p[/math].right.key [math]\neq K[/math]), set [math]p:= p[/math].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 [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.