acm
cz
acm
cz
Dept. of Computer Science and Engineering, Czech Technical University in Prague
Faculty of Mathematics and Physics, Charles University in Prague
Faculty of Electrical Engineering and Computer Science, Technical University of Ostrava
Faculty of Informatics and Information Technologies, Slovak University of Technology
Faculty of Informatics, Masaryk University
Faculty of Management Science and Informatics, University of Zilina
CTU Open Contest 2008
Tree In sert ion s
insert.c, insert.C, insert.java, insert.p
All modern banks employ information systems to process their data. The amount of data is
enormous. Imagine all the transactions, payments, e-banking, web services, etc. Therefore,
advanced data structures must be used to store the data and allow to access them very quickly.
A Binary Search Tree (BST) is one example of such a data structure It holds a collection of
values with some comparison operation that provides linear ordering on these values.
BST consists of nodes, each of them contains one value and has at most two subnodes: left and
right (BST is a binary tree). The left subtree always contains only values strictly less than the
node value, the right subtree only values greater than or equal to the node value.
As a consequence, values may easily be looked up by traversing the tree recursively. We begin
withtherootnodeandcompareitsvaluewiththevaluewearesearchingfor. Dependingon
the result, we descend either into the left or into the right subtree, but we never need to walk
through both.
If we want to insert values to an existing tree, the procedure is also simple. The first value
(when the tree is empty) is always put as the root. If the tree already exists, we start with the
root node and traverse the tree recursively, as in the case of searching. When the traversal leads
us to a missing subnode, we create a new leaf node at that position and assign it the new value.
The figures below show the tree after subsequently adding the following sequence of numbers:
3, 4, 3, 5, 4, 1, and 2.
3
3
4
3
3
4
3
3
4
5
3
3
4
5
4
3
1
3
4
5
4
3
1
23
4
5
4