Home | PSI RAS | RCIS | S-Tree Lib

In the theory of data structures the problem of index representation is known as the problem of maintaining dynamic dictionaries. A dynamic dictionary is a data structure for storing dictionary elements, called keys, together with algorithms of search, insertion, and deletion of the keys. Balanced trees are intended to provide for an efficient solution of the problem.

Fig.1. Balanced tree with numerical keys.

A balanced tree stores keys chosen from a finite set of keys K. The key set K is linearly ordered, and the keys are placed to the tree according to the ordering (see Fig.1). Each node of the tree contains a number of keys. Leaves don’t contain anything else, while the internal nodes additionally contain references to other nodes. A number of references in an internal node equals the number of keys in the node plus 1. An internal node S composed of m keys is denoted by

S = (S₀,k₀,...,S_i,k_i,S_i+1,...,k_m-1,S_m)

The following property of the nodes of the tree is the bases for an efficient tree searching.

1. For each key k_i of the node all keys located at the sub-tree accessible via the reference S_i to the left of k_i are less than k_i, and all keys located at the sub-tree accessible via the reference S_i+1 which is to the right of k_i are greater than k_i.

A balanced tree is organized such that

2. All paths in the tree from the root to a leaf have equal lengths.

Trees satisfying the above properties 1 and 2 are called structured trees.