Binary search tree: insert

Binary Search Tree
Insert

Sorted sequence

Openlearnware
See Chapter 4

General Information

Algorithmic problem: Sorted sequence: insert

Type of algorithm: loop

Auxiliary data: A pointer [math]\displaystyle{ p }[/math] 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 [math]\displaystyle{ K }[/math] is in the range of v.

Variant: [math]\displaystyle{ i }[/math] is 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.

Remark: For example, the height of the subtree rooted at the node to which [math]\displaystyle{ 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]\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 [math]\displaystyle{ K }[/math] in that empty slot and terminate the algorithm. Otherwise, proceed in that direction.

Implementation:

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

Complexity

Statement: The complexity is in [math]\displaystyle{ \mathcal{O}(T\cdot h)\subseteq\mathcal{O}(T\cdot n) }[/math] in the worst case, where [math]\displaystyle{ n }[/math] is the length of the sequence, [math]\displaystyle{ h }[/math] the height of the tree, and [math]\displaystyle{ 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