Binary search tree: remove

From Algowiki
Revision as of 20:22, 23 September 2014 by Jhohmann (talk | contribs) (→‎Complexity)
Jump to navigation Jump to search

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

Complexity

Statement: Linear in the length of the sequence in the worst case (more precisely, linear in the height of the tree).

Proof: Obvious.

Implementation

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