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