Module avl_tree.api

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.

Index

Variables

Functions