Binary search tree: remove node: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
 
(13 intermediate revisions by 2 users not shown)
Line 2: Line 2:
[[Category:Binary Search Tree]]
[[Category:Binary Search Tree]]
<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 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</div>
<div style="font-size: 1.8em;font-weight:bold;text-align: center;margin:0.2em 0 1em 0">Binary Search Tree<br>Remove node</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 1em 0; text-align:center">[[Sorted sequence]]</div>
Line 9: Line 9:
</div>
</div>
== General Information ==
== General Information ==
'''Algorithmic problem:''' See the remark clause of [[Binary Search Tree]]; pointer '''p''' as defined there is the input.
'''Algorithmic problem:''' See the [[Binary Search Tree#Remark|remark clause]] of [[Binary Search Tree]]; pointer <math>p</math> as defined there is the input.


'''Prerequisites:''' <math>p.left \neq void</math>
'''Prerequisites:''' <math>p</math>.left <math>\neq</math> void.


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


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


== Abstract View ==
== Abstract View ==
'''Invariant:'''
'''Invariant:'''
# The [[Directed Tree#Immediate Predecessor and Successor|immediate predecessor]] of '''''K''''' is in the [[Directed Tree#Ranges of Search Tree Nodes|range]] of <math>p'</math>.
# The [[Directed Tree#Immediate Predecessor and Successor|immediate predecessor]] of '''''K''''' is in the [[Directed Tree#Ranges of Search Tree Nodes|range]] of <math>p'</math>.
# It is <math>p'.right = void</math>.
# It is <math>p'</math>.right <math>\neq</math> void.


'''Variant:''' The pointer <math>p'</math> descends one level deeper to <math>p'.right</math>.
'''Variant:''' The pointer <math>p'</math> descends one level deeper, namely to <math>p</math>'.right.


'''Break condition:''' It is <math>p'.right.right = void</math>.
'''Break condition:''' It is <math>p'</math>.right.right = void.
 
'''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 31: Line 33:


'''Implementation:'''
'''Implementation:'''
# If <math>p.left.right = void</math>:
# If <math>p</math>.left.right = void:
## Set <math>p.key := p.left.key</math>
## Set <math>p</math>.key := p.left.key.
## Set <math>p.left := p.left.left</math>.
## Set <math>p</math>.left := p.left.left.
## Terminate the algorithm.
## Terminate the algorithm.
#Otherwise, set <math>p' := p.left</math>.
#Otherwise, set <math>p'</math> := p.left.


'''Proof:''' Obvious.
'''Proof:''' Obvious.


== Induction Step ==
== Induction Step ==
'''Abstract view:''' If <math>p'.right</math> is the immediate predecessor of '''''K''''', overwrite '''''K''''' by its immediate predecessor and terminate; otherwise, let '''''p'''''' descend one level deeper.
'''Abstract view:''' If <math>p'</math>.right.key is the immediate predecessor of <math>K</math>, overwrite <math>K</math> by its immediate predecessor and terminate; otherwise, let <math>p'</math> descend one level deeper.


'''Implementation:'''
'''Implementation:'''
# If <math>p'.right.right = void</math>:
# If <math>p'</math>.right.right = void:
## Set <math>p.key := p'.right.key</math>.
## Set <math>p</math>.key := <math>p'</math>.right.key.
## Set <math>p'.right := p'.right.left</math>.
## Set <math>p'</math>.right := <math>p'</math>.right.left.
# Terminate the algorithm.
## Terminate the algorithm.
# Set <math>p':=p'</math>.right.


'''Correctness:''' Obvoius.
'''Correctness:''' Obvious.


== 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: See the remark clause of Binary Search Tree; pointer [math]\displaystyle{ p }[/math] as defined there is the input.

Prerequisites: [math]\displaystyle{ p }[/math].left [math]\displaystyle{ \neq }[/math] void.

Type of algorithm: loop

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

Abstract View

Invariant:

  1. The immediate predecessor of K is in the range of [math]\displaystyle{ p' }[/math].
  2. It is [math]\displaystyle{ p' }[/math].right [math]\displaystyle{ \neq }[/math] void.

Variant: The pointer [math]\displaystyle{ p' }[/math] descends one level deeper, namely to [math]\displaystyle{ p }[/math]'.right.

Break condition: It is [math]\displaystyle{ p' }[/math].right.right = void.

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: If [math]\displaystyle{ p.left }[/math] is the immediate predecessor of K, overwrite K by its immediate predecessor and terminate; otherwise, initialize [math]\displaystyle{ p' }[/math].

Implementation:

  1. If [math]\displaystyle{ p }[/math].left.right = void:
    1. Set [math]\displaystyle{ p }[/math].key := p.left.key.
    2. Set [math]\displaystyle{ p }[/math].left := p.left.left.
    3. Terminate the algorithm.
  2. Otherwise, set [math]\displaystyle{ p' }[/math] := p.left.

Proof: Obvious.

Induction Step

Abstract view: If [math]\displaystyle{ p' }[/math].right.key is the immediate predecessor of [math]\displaystyle{ K }[/math], overwrite [math]\displaystyle{ K }[/math] by its immediate predecessor and terminate; otherwise, let [math]\displaystyle{ p' }[/math] descend one level deeper.

Implementation:

  1. If [math]\displaystyle{ p' }[/math].right.right = void:
    1. Set [math]\displaystyle{ p }[/math].key := [math]\displaystyle{ p' }[/math].right.key.
    2. Set [math]\displaystyle{ p' }[/math].right := [math]\displaystyle{ p' }[/math].right.left.
    3. Terminate the algorithm.
  2. Set [math]\displaystyle{ p':=p' }[/math].right.

Correctness: Obvious.

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.