Binary search tree: remove node: Difference between revisions
| Line 9: | Line 9: | ||
</div> | </div> | ||
== General Information == | == General Information == | ||
'''Algorithmic problem:''' See the remark clause of [[Binary Search Tree]]; pointer | '''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.left \neq void</math> | ||
Revision as of 08:32, 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.left \neq void }[/math]
Type of algorithm: loop
Auxiliary data: A pointer [math]\displaystyle{ p' }[/math] of type "pointer to a binary search tree node".
Abstract View
Invariant:
- The immediate predecessor of K is in the range of [math]\displaystyle{ p' }[/math].
- It is [math]\displaystyle{ p'.right = void }[/math].
Variant: The pointer [math]\displaystyle{ p' }[/math] descends one level deeper to [math]\displaystyle{ p'.right }[/math].
Break condition: It is [math]\displaystyle{ p'.right.right = void }[/math].
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:
- If [math]\displaystyle{ p.left.right = void }[/math]:
- Set [math]\displaystyle{ p.key := p.left.key }[/math]
- Set [math]\displaystyle{ p.left := p.left.left }[/math].
- Terminate the algorithm.
- 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:
- If [math]\displaystyle{ p'.right.right = void }[/math]:
- Set [math]\displaystyle{ p.key := p'.right.key }[/math].
- Set [math]\displaystyle{ p'.right := p'.right.left }[/math].
- 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.