Matrix tree

The data structures called by binary search trees are known. They consist of the elements containing search keys and connected by pointers so that the left and right descendants of each element differ in values of the keys respectively in the lower or greater side concerning value of a key of the ancestor.

Binary search trees consist of the element root which does not have the ancestor, the elements tops having the ancestor both not less than one descendant and the elements leaves having the ancestor and not having any descendant. In the course of adding or removal of elements of a position of a root, tops and leaves of a tree can occupy the different elements having different street addresses in memory of computing installation. For providing continuous access to a root of a binary tree the root pointer containing the current address of a root element is included.

Except a key, each element contains some information value compared to a key and which is actually a search subject and also the left and right pointers on elements descendants. For simplification of algorithms of transactions over a binary tree the structure of an element can join in addition the pointer on an element ancestor.

The binary tree is divided in a root and in any top having two descendants into the left and right subtrees containing elements with keys respectively smaller or big concerning the ancestor's key.

Such ordered arrangement of keys in a binary tree allows to perform their effective search. Search time decides by quantity of steps from a root to an element on a required key and is described by logarithmic dependence of O (log n) where n is number of tops of a binary tree. For the purpose of preserving of efficiency of search in the course of change of structure of elements in a binary tree it is necessary to maintain balance of the left and right subtrees so that their heights (quantity of tops) did not differ among themselves more than per unit of.

Binary tree balance is made by shift of elements in its structure. Time of shift of elements is defined by height of a binary tree.

At failure the difference of heights of the left and right subtrees as a result of adding or removal of elements can significantly differ from binary tree balance. As a last resort the binary tree can degenerate in the linear list of elements with search time of O (n).

For reduction of time of shift of elements of a binary tree the condition of its balance is mitigated so that heights of the left and right subtrees could differ among themselves no more, than twice. At the same time search time remains at the level O (log n).

Two species of the so-called self-balanced binary trees meeting this condition are known:

• The AVL-tree offered by G.M. Adelson-Velsky and E.M. Landis [1];
• the red ebony offered by R. Bauer [2].

For implementation of algorithms of balancing additional indicators are entered into structure of elements of these trees: difference of heights of the left and right subtrees (AVL-tree) and color of an element (red ebony).

The main lack of the known self-balanced binary trees is the remaining dependence of time of shift of elements on tree height. With a big height of a tree and frequent updating of structure of its elements the overall effectiveness of application of similar data structures in the course of information search significantly decreases.

For the purpose of overcoming this shortcoming the new type of the self-balanced binary search tree – a matrix tree is offered. The term "matrix" is used for reflection of that fact that the key of each element of a tree can be spread out to two multiplicands defining the place of an element – its level concerning the level of leaves of a tree and the taken position concerning the most left element at this level (similar to indexes of array element).

Besides, the matrix tree is separated in the root pointer into even and odd subtrees, each of which consists of the elements connected in the form of the binary search tree. The even subtree includes elements with even keys, odd – elements with odd keys. Each element of a matrix tree contains a key, information value, the right and left pointers on elements descendants.

Levels of a matrix tree nomerutsya from leaves to a root, positions of elements at one level nomerutsya from left to right. The key of the nxy element has indexes x and y where x – element level concerning leaves of a tree and y – an element position concerning the first element at the level.

The matrix tree has the following characteristic properties.

1. The key of each element can be spread out to two multiplicands

• for an even subtree
• n = 2x * z in case of the beginning of a nomeration of keys with 1
• n + 2 = 2x * z in case of the beginning of a nomeration of keys with 0
• where n is an element key, x - the level at which the element, z - the multiplicand is located
• for an odd subtree
• n + 1 = 2x * z

2. The element position at the level is equal

• y = (z + 1)/2

3. Quantity of the elements located under the general top, equally

• k = 2m where m is a difference on the module of levels of elements and the general

tops

4. The position of the last element at the level located under the general top is equal

• yi+k-1 = uvershiny * 2m

5. The key of the general top is equal to an arithmetic average of keys of the first and last elements located under the general top

• nvershiny = (ni + ni+k-1)/2

6. If the first element has the general top with the second element, then this top is overlying general top for the general top of the second element with the third element.

Degree of balance of a matrix tree depends on a type of the sequence in which keys before adding of elements in a matrix tree were sorted.

The method of balancing of a matrix tree is shown on the example of adding/removal of elements with a random series of keys.

The algorithm of adding/removal of elements from structure of a matrix tree is based on determination of the general top for two elements – the added/deleted element and earlier included/saved element. The computing complexity of an algorithm is defined by quantity of the elements participating in shifts which are among:

• • the element which is earlier included or remaining in a tree;
  • the element added or deleted from a tree;
  • the element which is the general top for the first two elements and also added/deleted from a tree;
  • the element which is earlier included or remaining in a tree which joins or from which the general top is disconnected.

The algorithm of adding/removal of elements from structure of a matrix tree consists of the following actions.

Stage 1.

Let the first element in the reviewed example have key 24. Further this element we will designate "24".

We determine the level and a position of the 24 element:

• 24 = 23 * 3, where
• level – 3, degree of the basis 2
• position – 2, private from division (3+1)/2

Due to the lack of other elements the 24 element joins in an even subtree as a root. The address of an element registers in the root pointer.

Stage 2.

The second element has key 6. We determine the level and a position of the 6 element:

• 6 = 21 * 3, where
• level – 1, degree of the basis 2
• position – 2, private from division (3+1)/2

We check the 24 element for compliance to criteria of the general top for the 6 element. The difference on the module of levels of the 24 and 6 elements is equal to 2. If the 24 element is the general top, the quantity of elements under it at the level of 1 is equal to the basis 2 built in the degree equal to a difference of levels: 4 = 22

The position of the last element under the general top at the level of 1 is equal to the position of the 24 element increased by the basis 2 in the degree equal to a difference of levels: 8 = 2 * 22

The position of the first element under the general top is equal to the position of the last element reduced by quantity of elements under the general top and increased by 1: 5 = 8 – 4 + 1

The position of the 6 element equal 2, does not enter an interval of positions of elements from 5 to 8 for which the 24 element is the general top. With respect thereto we continue search of the general top for the 6 and 24 elements.

We expand an interval of positions of elements which part the position of the 24 element, in the direction of the 6 element is. Expansion is made step by step by doubling of quantity of elements in an interval.

On the first step the quantity of elements in an interval increases to 8. The position of the first element is equal in this interval: 1 = 8 – 8 + 1

Therefore, the position of the 6 element enters this interval.

We define keys of the first and last elements in this interval

Key of the first element: 2 = 21 * (2*1 - 1)

Key of the last element: 30 = 21 * (2*8 - 1)

The key of the general top is equal to an arithmetic average of keys of the first and last elements in an interval: 16 = (2 + 30)/2

The 16 element becomes a root of an even subtree to which leaves "6" and "24" fasten. In the root pointer the address of a root of an even subtree respectively changes.

Stage 3.

The third element has key 12.

We determine the level and a position of the 12 element:

• 12 = 22 * 3
• level – 2, degree of the basis 2
• position – 2, private from division (3+1)/2

We perform search in a tree of an element with which the 12 element can be connected.

Such element is "6".

The difference of levels of these elements on the module is equal to 1. At the same time the 12 element is at higher level.

The quantity of elements for which the 12 element is the general top at the level of 1 is equal to two. An interval of their positions – 3 and 4. The position of the 6 element does not enter this interval.

We expand an interval towards the 6 element by doubling of quantity of elements.

The new interval consists of elements with positions from 1 to 4.

Keys of the first and last elements of an interval are equal respectively to 2 and 14. The key of the general top is equal to 8.

The 6 and 12 elements contact the general top "8" which in turn contacts the root "16".

Stage 4.

The fourth element has key 2.

We determine the level and a position of the 2 element: 2 = 21 * 1

• level – 1, degree of the basis 2
• position – 1, private from division (1+1)/2

We perform search in a tree of an element with which the 2 element can be connected.

Such element is "6".

The difference of levels of these elements on the module is equal to 0.

With respect thereto we begin to expand an interval of positions of the elements which are at the level of 1 in the direction from left to right.

Expansion of an interval is performed from the very first position of the elements located at this level, step by step with doubling of quantity of positions on each step.

On the first step the quantity of positions of elements doubles from 1 to 2.

On each step the received interval is checked for occurrence of the 2 element.

The 2 element enters the interval received on the first step.

With respect thereto we begin to expand an interval in the direction from right to left.

Expansion of an interval begins with the latest position of earlier calculated interval step by step with doubling of quantity of positions of elements on each step.

On the first step the initial quantity of positions of elements doubles from 1 to 2. On each step the received interval is checked for occurrence of the 2 element.

The 2 element enters the interval received on the first step.

The first element of the first interval has position 1, the last element of the second interval has position 2. Keys of elements are equal respectively to 2 and 6. Therefore, the key of the general top is equal to 4. The 2 and 6 elements contact the general top "4" which in turn contacts top "8".

Removal of elements from structure of a matrix tree is performed upside-down.

The analysis of structure and method of balancing of a matrix tree allows to draw conclusions on efficiency of its application in comparison with the AVL-tree or a red ebony.

1. Search time in a matrix tree is defined by a type of the sequence in which keys of elements before their adding in structure of a tree were sorted.

At a random series search is run in a half from the total number of elements. Search time makes O (log n/2) [3] where n/2 is quantity of elements which keys match search key on value of characteristic of parity/oddness.

At inclusion in structure of a random series of keys with identical characteristic of parity/oddness search is run in the total number of elements. Search time makes O(log n). At the increasing / decreasing sequence of a type 2n even and odd subtrees degenerate in linear lists of elements with search time of O (n).

2. The quantity of the elements of a matrix tree participating in shifts during the adding or removal of elements does not exceed four. Respectively, runtime of these transactions for a matrix tree does not exceed O (log 4).

3. The complete bypass of all elements or search of an element with the smallest/greatest key in a matrix tree is performed during O (log n) because of need to repeat these transactions in even and odd subtrees.

4. The matrix tree occupies the smaller amount of memory of computing installation because of absence as a part of elements of additional indicators of a difference of heights of the left and right subtrees or color of an element.

The specified outputs allow to define a scope of matrix trees – in all cases of the recommended use of the self-balanced binary search trees, except for trees which elements contain the keys sorted in the increasing / decreasing sequence of a type 2n.

Literature:

1. Adelson-Velsky G.M., Landis E.I. One algorithm of the organization of information. Reports of Academy of Sciences of the USSR, 1962. T.146, No. 2. Page 263-266.

2. Bayer R. Symmetric Binary B-Trees: Data Structure and Maintenance Algorithms. Acta Informatica, 1972. V.1, No 4. P.290-306.

3. Kormen T., Leyzer Ch., River Rivest. Algorithms: creation and analysis. Chapter 13.4. MCCME, 1999. Page 258-262

4. Vasilyev A.E. Matrix search trees. Natural and technical science. ISSN 1684-2626. 2010. No. 1(45). Page 31