Binary search tree: insert

From Algowiki
Jump to: navigation, search

General Information

Algorithmic problem: Sorted sequence: insert

Type of algorithm: loop

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

Abstract View

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

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

Variant: [math]i[/math] is increased by 1.

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

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

Remark: For example, the height of the subtree rooted at the node to which [math]p[/math] points may be chosen as the induction parameter. For conciseness, the induction parameter is omitted in the following.

Induction Basis

Abstract view: If the tree is empty, a new root with key [math]K[/math] is created; otherwise, [math]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]:= K[/math], root.left [math]:=[/math] void, and root.right [math]:=[/math] void.
  2. Otherwise, set [math]p := root[/math].

Proof: Obvious.

Induction Step

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

Implementation:

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

Complexity

Statement: The complexity is in [math]\mathcal{O}(T\cdot h)\subseteq\mathcal{O}(T\cdot n)[/math] in the worst case, where [math]n[/math] is the length of the sequence, [math]h[/math] the height of the tree, and [math]T[/math] the complexity of the comparison.

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