Binary search tree: remove node: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 20: Line 20:
'''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 = 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.


== Induction Basis ==
== Induction Basis ==

Revision as of 14:17, 18 May 2015

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

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.left.right = void }[/math]:
    1. Set [math]\displaystyle{ p.key := p.left.key }[/math]
    2. Set [math]\displaystyle{ p.left := p.left.left }[/math].
    3. Terminate the algorithm.
  2. Otherwise, set [math]\displaystyle{ p' := p.left }[/math].

Proof: Obvious.

Induction Step

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

Implementation:

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

Correctness: Obvoius.

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.