Binary search tree: insert

From Algowiki
Jump to navigation Jump to search

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{ \mathcal{K} }[/math]."

Abstract View

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

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

Variant: [math]\displaystyle{ i }[/math] increased by 1.

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

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

Induction Basis

Abstract view: If the tree is empty, a new root with key [math]\displaystyle{ K }[/math] is created; otherwise, [math]\displaystyle{ p }[/math] is initialized so as to point to the root.

Implementation:

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

Proof: Obvious.

Induction Step

Abstract view: If the direction where to go next is void, insert K in that empty slot and terminate the algorithm. Otherwise, proceed in that direction.

Implementation:

  1. If [math]\displaystyle{ p.key = K }[/math]:
    1. If [math]\displaystyle{ p.left = void }[/math]:
      1. Create a new node and let [math]\displaystyle{ p.left }[/math] point to it.
      2. Set [math]\displaystyle{ p.left.key := K }[/math], [math]\displaystyle{ p.left.left := void }[/math], and [math]\displaystyle{ p.left.right := void }[/math].
      3. Terminate the algorithm.
    2. Otherwise, if [math]\displaystyle{ p.right = void }[/math]:
      1. Create a new node and let [math]\displaystyle{ p.right }[/math] point to it.
      2. Set [math]\displaystyle{ p.left.key := K }[/math], [math]\displaystyle{ p.left.left := void }[/math], and [math]\displaystyle{ p.left.right := void }[/math].
      3. Terminate the algorithm.
    3. Otherwise, set [math]\displaystyle{ p := p.left }[/math].
  2. Otherwise, if [math]\displaystyle{ p.key \gt K }[/math]:
    1. If [math]\displaystyle{ p.left = void }[/math]:
      1. Create a new node and let [math]\displaystyle{ p.left }[/math] point to it.
      2. Set [math]\displaystyle{ p.left.key := K }[/math], [math]\displaystyle{ p.left.left := void }[/math], and [math]\displaystyle{ p.left.right := void }[/math].
      3. Terminate the algorithm.
    2. Otherwise, set [math]\displaystyle{ p := p.left }[/math].
  3. Otherwise (that is, [math]\displaystyle{ p.key \lt K }[/math]):
    1. If [math]\displaystyle{ p.right = void }[/math]:
      1. Create a new node and let [math]\displaystyle{ p.right }[/math] point to it.
      2. Set [math]\displaystyle{ p.right.key := K }[/math], [math]\displaystyle{ p.right.left := void }[/math], and [math]\displaystyle{ p.right.right := void }[/math].
      3. Terminate the algorithm.
    2. Otherwise, set [math]\displaystyle{ p := p.right }[/math].

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.

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