Binary search tree: insert: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 19: Line 19:


== Induction Basis ==
== Induction Basis ==
'''Abstract view:''' If the tree is empty, a new root with key '''''K''''' is created; otherwise, '''''p''''' is initialized so as to point to the root.
'''Implementation:'''
# If <math>root = void</math>
## Create a new binary search tree node and let '''''root''''' point to it.
## Set <math>root.key := K, root.left := void</math>. and <math>root.right := void</math>.
# Otherwise, set <math>p := root<math>.
'''Proof:''' Obvious.


== Induction Step ==
== Induction Step ==

Revision as of 19:38, 25 September 2014

General Information

Algorithmic problem: Sorted sequence: insert

Type of algorithm: loop

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

Abstract View

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

  1. The pointer p points to a tree node v on height level i.
  2. The Key K is in the range of v.

Variant: i increased by 1.

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

  1. It is [math]\displaystyle{ p.key \geq K }[/math] and [math]\displaystyle{ p.left = void }[/math].
  2. It is [math]\displaystyle{ p.key \leq K }[/math] and [math]\displaystyle{ p.right = void }[/math].

Induction Basis

Abstract view: If the tree is empty, a new root with key K is created; otherwise, p is initialized so as to point to the root.

Implementation:

  1. If [math]\displaystyle{ root = void }[/math]
    1. Create a new binary search tree node and let root point to it.
    2. Set [math]\displaystyle{ root.key := K, root.left := void }[/math]. and [math]\displaystyle{ root.right := void }[/math].
  2. Otherwise, set <math>p := root<math>.

Proof: Obvious.

Induction Step

Copmplexity

Pseudocode

TREE-INSERT(T, z)

y = Null
x = root(T)
while x ≠ NULL
y = x
if key[z] < key[x]
then x = left[x]
then x = right[x]
p[z] = y
if y = NULL
then root[T] = z //Tree was empty
else if key[z] < key[y]
then left[y] = z
else right[y] = z