Binary search tree: remove: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 38: Line 38:
## Otherwise, if root.right = void, set root := root.left.
## Otherwise, if root.right = void, set root := root.left.
## Otherwise, call method [[Binary Search Tree:Remove node|remove node]] with pointer root.  
## Otherwise, call method [[Binary Search Tree:Remove node|remove node]] with pointer root.  
## Terminate the algorithm and return '''''true'''''.  
## Terminate the algorithm and return '''true'''.  


# Otherwise set <math>p :=</math> root.
# Otherwise set <math>p :=</math> root.

Revision as of 08:00, 18 May 2015

General Information

Algorithmic Problem: Sorted sequence:remove

Type of algorithm: loop

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

Abstract view

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

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

Variant: [math]\displaystyle{ i }[/math] increased by [math]\displaystyle{ 1 }[/math].

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

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

Induction basis

Abstract view:

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

Implementation:

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

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]\displaystyle{ \mathcal{O}(T\cdot h)\subseteq\mathcal{O}(T\cdot n) }[/math] in the worst case, where [math]\displaystyle{ n }[/math] is the length of the sequence, [math]\displaystyle{ h }[/math] the height of the tree, and [math]\displaystyle{ T }[/math] the complexity of the comparison.

Proof: Obvious.