Binary search tree: insert
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:
- The pointer [math]\displaystyle{ p }[/math] points to a tree node [math]\displaystyle{ v }[/math] on height level [math]\displaystyle{ i }[/math].
- 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:
- It is [math]\displaystyle{ p }[/math].key [math]\displaystyle{ \geq K }[/math] and [math]\displaystyle{ p }[/math].left [math]\displaystyle{ = }[/math]void.
- 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:
- If root = void:
- Create a new binary search tree node and let root point to it.
- Set root.key[math]\displaystyle{ := K }[/math], root.left [math]\displaystyle{ := }[/math] void, and root.right [math]\displaystyle{ := }[/math] void.
- 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:
- If [math]\displaystyle{ p }[/math].key [math]\displaystyle{ = K }[/math]:
- If [math]\displaystyle{ p }[/math].left = void:
- Create a new node and let [math]\displaystyle{ p }[/math].left point to it.
- 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.
- Terminate the algorithm.
- Otherwise, if [math]\displaystyle{ p }[/math].right = void:
- Create a new node and let [math]\displaystyle{ p }[/math].right point to it.
- 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.
- Terminate the algorithm.
- Otherwise, set [math]\displaystyle{ p := p }[/math].left.
- If [math]\displaystyle{ p }[/math].left = void:
- Otherwise, if [math]\displaystyle{ p }[/math].key [math]\displaystyle{ \gt K }[/math]:
- If [math]\displaystyle{ p }[/math].left = void:
- Create a new node and let [math]\displaystyle{ p }[/math].left point to it.
- 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.
- Terminate the algorithm.
- Otherwise, set [math]\displaystyle{ p := p }[/math].left.
- If [math]\displaystyle{ p }[/math].left = void:
- Otherwise (that is, [math]\displaystyle{ p }[/math].key [math]\displaystyle{ \lt K }[/math]):
- If [math]\displaystyle{ p }[/math].right = void:
- Create a new node and let [math]\displaystyle{ p }[/math].right point to it.
- 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.
- Terminate the algorithm.
- Otherwise, set [math]\displaystyle{ p := p }[/math].right.
- If [math]\displaystyle{ p }[/math].right = void:
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