Binary search tree: remove: Difference between revisions

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

Revision as of 14:35, 9 May 2015

General Information

Algorithmic Problem: Sorted sequence:remove

Type of algorithm: loop

Auxiliary data: A pointer p of type "pointer to binary search tree node".

Abstract view

Invariant After [math]\displaystyle{ i \geq 0 }[/math] interations:

  1. The pointer p points to a tree node v on height level i.
  2. The key K is in range of p, but [math]\displaystyle{ p.key \neq K }[/math].

Variant: i increased by 1.

Break Condition: One of the following two conditions is fulfilled:

  1. It is [math]\displaystyle{ K \lt p.key }[/math] and either [math]\displaystyle{ p.left = void }[/math] or [math]\displaystyle{ p.left.key = K }[/math].
  2. It is [math]\displaystyle{ K \gt p.key }[/math] and either [math]\displaystyle{ p.right = void }[/math] or [math]\displaystyle{ p.right.key = K }[/math].

Induction basis

Abstract view:

  1. If the root contains K, remove this occurrence of K.
  2. Otherwise, initialize p so as to point to the root.

Implementation:

  1. If [math]\displaystyle{ root.key = K }[/math]:
    1. If [math]\displaystyle{ root.left = void }[/math], set [math]\displaystyle{ root := root.right }[/math]
    2. Otherwise, if [math]\displaystyle{ root.right = void }[/math], set [math]\displaystyle{ root := root.left }[/math].
    3. Otherwise, call method remove node with pointer root.
    4. Terminate the algorithm and return true.
  1. Otherwise set [math]\displaystyle{ p := root }[/math]

Proof: Nothing to show.

Induction step

Abstract View:

  1. 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).
  2. Otherwise, descend to that node.

Implementation:

  1. I [math]\displaystyle{ K \lt p.key }[/math]:
    1. If [math]\displaystyle{ p.left = void }[/math], terminate the algorithm and return false.
    2. Otherwise if [math]\displaystyle{ p.left.key = K }[/math]:
      1. If [math]\displaystyle{ p.left.left = void }[/math], set [math]\displaystyle{ p.left := p.left.right }[/math].
      2. Otherwise, if [math]\displaystyle{ p.left.right = void }[/math], set [math]\displaystyle{ p.left := p.left.left }[/math].
      3. Otherwise, call method remove node with pointer p.left.
      4. Terminate the algorithm and return true.
    3. Otherwise (that is, [math]\displaystyle{ p.left \neq void }[/math] and [math]\displaystyle{ p.left.key \neq K }[/math]), set [math]\displaystyle{ p := p.left }[/math].
  2. Otherwise (that is, [math]\displaystyle{ K \gt p.key }[/math]):
    1. If [math]\displaystyle{ p.right = void }[/math], terminate the algorithm and return false.
    2. Otherwise, if [math]\displaystyle{ p.right.key = K }[/math]:
      1. If [math]\displaystyle{ p.right.left = void }[/math], set [math]\displaystyle{ p.right = p.right.right }[/math].
      2. Otherwise, if [math]\displaystyle{ p.right.right = void }[/math], set [math]\displaystyle{ p.right = p.right.left }[/math].
      3. Otherwise, call method remove node with pointer p.right.
      4. Terminate the algorithm and return true.
    3. Otherwise (that is, [math]\displaystyle{ p.right \neq void }[/math] and [math]\displaystyle{ p.right.key \neq K }[/math]), set [math]\displaystyle{ p:= p.right }[/math].

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

Worst case binary search tree

Proof: Obvious.