Binary search tree: remove: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 49: Line 49:
# Otherwise, descend to that node.
# Otherwise, descend to that node.
'''Implementation:'''
'''Implementation:'''
# If <math>K < p.key</math>:
# If <math>K < p</math>.key:
## If <math>p</math>.left = void, terminate the algorithm and return '''false'''.  
## If <math>p</math>.left = void, terminate the algorithm and return '''false'''.  
## Otherwise if <math>p</math>.left.key <math>= K</math>:
## Otherwise if <math>p</math>.left.key <math>= K</math>:

Revision as of 08:11, 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 [math]\displaystyle{ K }[/math], terminate the algorithm (and in the latter case, remove that node appropriately).
  2. Otherwise, descend to that node.

Implementation:

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