File AVLTree.h

↰ Parent directory (ADS/tree)

The AVL tree of Adelson-Velsky and Landis, beyond the book [see File SearchTree.h for the Red-Black tree of chapter 6]: a binary search tree whose every node has subtrees of heights differing by at most 1, so that its height is below :math:` 1.4405 log_2 ( n + 2 ) , a little more balanced than a Red-Black tree (whose bound is :math: 2 log_2 ( n + 1 ) `), at the price of more rotations on the updates.

Definition (ADS/tree/AVLTree.h)

Detailed Description

Each node keeps its height; an insertion or a removal goes down recursively and, on the way back, restores the balance of each node by a single or a double rotation, in :math:` O( log n ) ` time. It is a DICTIONARY [see File ADT.h] with lookup(), insert() and remove(), and forEach() visits the pairs by increasing keys.

The contracts [see File Contract.h]: insert() ensures that the key is there and remove() that it is not; the invariant is the order of the keys, the heights stored and the balance of every node, an O( n ) check at the level 3. The operations are defined in AVLTree.tpp.

    1. Adelson-Velsky, E. M. Landis, An algorithm for the organization of information, Soviet Mathematics Doklady 3, 1259-1263, 1962

    1. Knuth, The Art of Computer Programming, vol. 3, 2nd ed., Addison-Wesley, 1998, section 6.2.3

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes