Binary search tree: insert: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
(15 intermediate revisions by the same user not shown)
Line 12: Line 12:
'''Type of algorithm:''' loop
'''Type of algorithm:''' loop


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


== Abstract View ==
== Abstract View ==
'''Invariant:''' After <math>i \geq 0</math> iterations:
'''Invariant:''' After <math>i \geq 0</math> iterations:
# The pointer '''''p''''' points to a tree node '''''v''''' on height level '''''i'''''.
# The pointer <math>p</math> points to a tree node <math>v</math> on height level <math>i</math>.
# The Key '''''K''''' is in the [[Directed Tree#Ranges of Search Tree Nodes|range]] of '''''v'''''.
# The Key <math>K</math> is in the [[Directed Tree#Ranges of Search Tree Nodes|range]] of '''''v'''''.


'''Variant:''' '''''i''''' increased by '''''1'''''.
'''Variant:''' <math>i</math> is increased by 1.


'''Break condition:''' One of the following two conditions is fulfilled:
'''Break condition:''' One of the following two conditions is fulfilled:
# It is <math>p.key \geq K</math> and <math>p.left = void</math>.
# It is <math>p</math>.key <math>\geq K</math> and <math>p</math>.left <math>=</math>void.
# It is <math>p.key \leq K</math> and <math>p.right = void</math>.
# 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 ==
== 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.
'''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:'''
'''Implementation:'''
# If <math>root = void</math>:
# If root = void:
## Create a new binary search tree node and let '''''root''''' point to it.
## 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>.
## Set root.key<math>:= K</math>, root.left <math>:=</math> void, and root.right <math>:=</math> void.
# Otherwise, set <math>p := root</math>.
# Otherwise, set <math>p := root</math>.


Line 37: Line 39:


== Induction Step ==
== 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.
'''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:'''
'''Implementation:'''
# If <math>p.key = K</math>:
# If <math>p</math>.key <math>= K</math>:
## If <math>p.left = void</math>:
## If <math>p</math>.left = void:
### Create a new node and let <math>p.left</math> point to it.
### Create a new node and let <math>p</math>.left point to it.
### Set <math>p.left.key := K</math>, <math>p.left.left := void</math>, and <math>p.left.right := void</math>.
### 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.
### Terminate the algorithm.
### Terminate the algorithm.
## Otherwise, if <math>p.right = void</math>:
## Otherwise, if <math>p</math>.right = void:
### Create a new node and let <math>p.right</math> point to it.
### Create a new node and let <math>p</math>.right point to it.
### Set <math>p.left.key := K</math>, <math>p.left.left := void</math>, and <math>p.left.right := void</math>.
### Set <math>p</math>.right.key <math>:= K</math>, <math>p</math>.right.left := void, and <math>p</math>.right.right := void.
### Terminate the algorithm.
### Terminate the algorithm.
## Otherwise, set <math>p := p.left</math>.
## Otherwise, set <math>p := p</math>.left.
# Otherwise, if <math>p.key > K</math>:
# Otherwise, if <math>p</math>.key <math>> K</math>:
## If <math>p.left = void</math>:
## If <math>p</math>.left = void:
### Create a new node and let <math>p.left</math> point to it.
### Create a new node and let <math>p</math>.left point to it.
### Set <math>p.left.key := K</math>, <math>p.left.left := void</math>, and <math>p.left.right := void</math>.
### 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.
### Terminate the algorithm.
### Terminate the algorithm.
## Otherwise, set <math>p := p.left</math>.
## Otherwise, set <math>p := p</math>.left.
# Otherwise (that is, <math>p.key < K</math>):
# Otherwise (that is, <math>p</math>.key <math>< K</math>):
## If <math>p.right = void</math>:
## If <math>p</math>.right = void:
### Create a new node and let <math>p.right</math> point to it.
### Create a new node and let <math>p</math>.right point to it.
### Set <math>p.right.key := K</math>, <math>p.right.left := void</math>, and <math>p.right.right := void</math>.
### 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.
### Terminate the algorithm.
### Terminate the algorithm.
## Otherwise, set <math>p := p.right</math>.
## Otherwise, set <math>p := p</math>.right.


== Complexity ==
== Complexity ==
'''Statement:''' Linear in the length of the sequence in the worst case (more precisely, linear in the height of the tree).
'''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.
[[File:wcbst.png|300px|thumb|right|Worst case binary search tree]]
 
'''Proof:''' Obvious.
'''Proof:''' Obvious.



Latest revision as of 13:39, 3 March 2017

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