The balance algorithm for RB-tree

Author: Nikoloz Grdzelidze
Co-authors: George Shvelidze
Keywords: RBT, AVL, hybrid data
Annotation:

Hybrid data structure is very closely related to the existing balance algorithms. Hybrid RB tree means that in some cases, only for a short time, colour field has different function, which gives us abilities that RB tree doesn’t have. Though, the knot structure remains unchanged.The RB tree operations are conducted in guaranteed logarithm time. Although, searching operations are relatively slow comparing to the AVL tree. If it happens in practice that the long process of adding and deleting of the knots, followed by a long searching process, etc. occurs, then it is preferred to transform RB tree into AVL tree before the searching operation and counter transformation may be done only if necessary. The transformation into AVL tree will occur by circling in inorder style of the initial tree and the taking of knots from the RB tree by increasing numbers and putting them into AVL tree by the same principle. In fact, the use of Day’s algorithm for the re-balancing is the same as transformation into AVL tree with the precise details of the implementation). There is no technical obstacle; when it comes to programming, everything is done within the same class, which is united with the one mode field. The structure of the knot remains unchanged. There are two fixups for the adding and the same amount for the deleting – according to the regime. RB tree and AVL tree are different only by this fixup. There are also algorithms to transfer them in each other. One of them means the re-balancing of the RB Tree with Day’ algorithm.

Lecture files:

BalancingRBT [ka]