Binary search tree: remove: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
(21 intermediate revisions by 2 users not shown)
Line 3: Line 3:
[[Category:Binary Search Tree]]
[[Category:Binary Search Tree]]
[[Category:Algorithm]]
[[Category:Algorithm]]
<div class="plainlinks" style="float:right;margin:0 0 5px 5px; border:1px solid #AAAAAA; width:auto; padding:1em; margin: 0px 0px 1em 1em;">
<div style="font-size: 1.8em;font-weight:bold;text-align: center;margin:0.2em 0 1em 0">Binary Search Tree<br>Remove</div>
<div style="font-size: 1.2em; margin:.5em 0 1em 0; text-align:center">[[Sorted sequence]]</div>
<div style="font-size: 1.2em; margin:.5em 0 .5em 0;text-align:center">[[File:olw_logo1.png|20px]][https://openlearnware.tu-darmstadt.de/#!/resource/binary-search-tree-1938 Openlearnware]<br>See Chapter 5</div>
</div>
== General Information ==
== General Information ==


'''Algorithmic Problem:''' [[Sorted Sequence:remove]]
'''Algorithmic Problem:''' [[Sorted sequence#Remove|Sorted sequence:remove]]


'''Type of algorithm:''' loop
'''Type of algorithm:''' loop


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


== Abstract view ==
== Abstract view ==
'''Invariant''' After <math>i \geq 0</math> interations:
'''Invariant''' After <math>i \geq 0</math> interations:
# The pointer '''''p''''' points to a tree node '''''v''''' on height level '''''i'''''.
# The pointer <math>p</math> points to a tree node <math>v</math> on height level <math>i</math>.
# The key '''''K''''' is in [[Directed Tree#Ranges of Search Tree Nodes|range]] of '''''p''''', but <math>p.key \neq K</math>.
# The key <math>K</math> is in [[Directed Tree#Ranges of Search Tree Nodes|range]] of <math>p</math>, but <math>p.key \neq K</math>.
'''Variant:''' '''''i''''' increased by '''''1'''''.
'''Variant:''' <math>i</math> increased by <math>1</math>.


'''Break Condition:''' One of the following two conditions is fulfilled:
'''Break Condition:''' One of the following two conditions is fulfilled:
# It is <math>K < p.key</math> and either <math>p.left = void</math> or <math>p.left.key = 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.key</math> and either <math>p.right = void</math> or <math>p.right.key = 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==
'''Abstract view:'''
'''Abstract view:'''
# If the root contains '''''K''''', remove this occurrence of '''''K'''''.  
# If the root contains <math>K</math>, remove this occurrence of <math>K</math>.  
# Otherwise, initialize '''''p''''' so as to point to the root.
# Otherwise, initialize <math>p</math> so as to point to the root.


'''Implementation:'''
'''Implementation:'''
# If <math>root.key = K</math>:
# If root.key <math>= K</math>:
## If <math>root.left = void</math>, set <math>root := root.right</math>
## If root.left = void, set root := root.right.
## Otherwise, if <math>root.right = void</math>, set <math>root := root.left</math>.
## 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 := root</math>
# Otherwise set <math>p :=</math> root.


'''Proof:''' Nothing to show.
'''Proof:''' Obvious.


== Induction step==
== Induction step==
'''Abstract View:'''
'''Abstract View:'''
# 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).  
# 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).  
# Otherwise, descend to that node.
# Otherwise, descend to that node.
'''Implementation:'''
'''Implementation:'''
# I <math>K < p.key</math>:
# If <math>K < p</math>.key:
## If <math>p.left = void</math>, terminate the algorithm and return '''''false'''''.  
## If <math>p</math>.left = void, terminate the algorithm and return '''false'''.  
## Otherwise if <math>p.left.key = K</math>:
## Otherwise if <math>p</math>.left.key <math>= K</math>:
### If <math>p.left.left = void</math>, set <math>p.left := p.left.right</math>.
### If <math>p</math>.left.left = void, set <math>p</math>.left := p.left.right.
### Otherwise, if <math>p.left.right = void</math>, set <math>p.left := p.left.left</math>.
### Otherwise, if <math>p</math>.left.right = void, set <math>p</math>.left := p.left.left.
### Otherwise, call method [[Binary Search Tree:Remove node|remove node]] with pointer '''''p.left'''''.  
### Otherwise, call method [[Binary Search Tree:Remove node|remove node]] with pointer <math>p</math>.left.  
### Terminate the algorithm and return '''''true'''''.  
### Terminate the algorithm and return '''true'''.  
## Otherwise (that is, <math>p.left \neq void</math> and <math>p.left.key \neq K</math>), set <math>p := p.left</math>.  
## 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.right = void</math>, terminate the algorithm and return '''''false'''''.  
## If <math>p</math>.right = void, terminate the algorithm and return '''false'''.  
## Otherwise, if <math>p.right.key = K</math>:  
## Otherwise, if <math>p</math>.right.key <math>= K</math>:  
### If <math>p.right.left = void</math>, set <math>p.right = p.right.right</math>.  
### If <math>p</math>.right.left = void, set <math>p</math>.right <math>=p</math>.right.right.  
### Otherwise, if <math>p.right.right = void</math>, set <math>p.right = p.right.left</math>.  
### Otherwise, if <math>p</math>.right.right = void, set <math>p</math>.right <math>= p</math>.right.left.  
### Otherwise, call method [[Binary Search Tree:Remove node|remove node]] with pointer '''''p.right'''''.  
### Otherwise, call method [[Binary Search Tree:Remove node|remove node]] with pointer <math>p</math>.right.  
### Terminate the algorithm and return '''''true'''''.  
### Terminate the algorithm and return '''true'''.  
## Otherwise (that is, <math>p.right \neq void</math> and <math>p.right.key \neq K</math>), set <math>p:= p.right</math>.
## 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.
'''Correctness:''' Nothing to show.
Line 83: Line 92:


== Complexity==
== Complexity==
'''Statement:''' Linear in the length of the sequence in the worst case (more precisely, linear in the height of the tree).
'''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.
'''Proof:''' Obvious.

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.