Implementação de árvore AVL.

O que é árvore AVL?

"There are many structures and algorithm aimed at keeping trees as balanced as possible. (...) The first ones in chronological are the height balanced search trees or AVL trees proposed by the two Russians Adelson-Velskii and Landis in 1962, which have worst case height equal to 1.44log(n + 2) - 0.328. In an AVL tree the left and right subtree height of all nodes may differ at most by one level. This is achieved by embedding one more field in the node, the balance factor which may take only three values: -1, 0 or 1." Encyclopedia of Computer Science and Technology: Volume 28 - Supplement 13 ISBN 9780824722814

"Há muitas estruturas e algoritmos destinados a manter as árvores mais equilibrada possível. (...) Os primeiros em ordem cronológica são a altura equilibrado árvores de busca ou árvores AVL propostas pelo dois russos Adelson-Velskii e Landis em 1962, que têm pior altura caso igual a 1.44log (n + 2) - 0.328. Em uma árvore AVL a altura subárvore esquerda e direita de todos os nós podem diferir em mais de um nível. Isto é conseguido através da incorporação de mais um campo no nó, o factor de equilíbrio que pode ter apenas três valores: -1, 0 ou 1."