Binary search tree: remove: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
(One intermediate revision by the same user not shown)
Line 27: Line 27:
# It is <math>K < p</math>.key and either <math>p</math>.left = void or <math>p</math>.left.key <math>= K</math>.
# It is <math>K < p</math>.key and either <math>p</math>.left = void or <math>p</math>.left.key <math>= K</math>.
# It is <math>K > p</math>.key and either <math>p</math>.right = void or <math>p</math>.right.key = <math>K</math>.
# It is <math>K > 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==
== Induction basis==
Line 57: Line 59:
### Terminate the algorithm and return '''true'''.  
### Terminate the algorithm and return '''true'''.  
## 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.  
## 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.  
# Otherwise (that is, <math>K > p.key</math>):  
# Otherwise (that is, <math>K > p</math>.key):  
## If <math>p</math>.right = void, terminate the algorithm and return '''false'''.  
## If <math>p</math>.right = void, terminate the algorithm and return '''false'''.  
## Otherwise, if <math>p</math>.right.key <math>= K</math>:  
## Otherwise, if <math>p</math>.right.key <math>= K</math>:  

Latest revision as of 13:39, 3 March 2017

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

Remark: For example, the height of the subtree rooted at the node to which [math]\displaystyle{ 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]\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 }[/math] void 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 }[/math].key):
    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.