This file implements the AVL tree structure (cf. https://en.wikipedia.org/wiki/AVL_tree), named from their two
inventors Adelson-Velsky and Landis. An AVL tree is a binary search
tree with self-balancing properties.
In this implementation an AVL-tree is a binary tree from the binary_tree module. Simply, the functions are
prefixed with the avlTree key.
The implementation is functional by choice. It could as well be
imperative. Compared to the binary tree implementation, it provides
an empty AVL-tree.
The height h (counted as the maximal number of levels) of an AVL
tree with n nodes lies in the interval :
log(n+1) ≤ h < log(n+2)/log(φ) + b
where φ is the golden ratio (~= 1.618) and b := log(5) / 2log(φ) -
2 (~= -0.327).
The operations of research, insertion and deletion are done in
O(log(n)) time in the average and in the worst case.
This file implements the AVL tree structure (cf. https://en.wikipedia.org/wiki/AVL_tree), named from their two inventors Adelson-Velsky and Landis. An AVL tree is a binary search tree with self-balancing properties.
In this implementation an AVL-tree is a binary tree from the binary_tree module. Simply, the functions are prefixed with the
avlTreekey.The implementation is functional by choice. It could as well be imperative. Compared to the binary tree implementation, it provides an empty AVL-tree.
The height
h(counted as the maximal number of levels) of an AVL tree withnnodes lies in the interval :log(n+1) ≤ h < log(n+2)/log(φ) + b
where φ is the golden ratio (~= 1.618) and b := log(5) / 2log(φ) - 2 (~= -0.327).
The operations of research, insertion and deletion are done in O(log(n)) time in the average and in the worst case.