Homepage: https://www.gnu.org/software/emacs
Author: Inge Wallin, Per Cederqvist, Thomas Bellman, Toby Cubitt
Balanced binary trees, AVL-trees
An AVL tree is a self-balancing binary tree. As such, inserting, deleting, and retrieving data from an AVL tree containing n elements is O(log n). It is somewhat more rigidly balanced than other self-balancing binary trees (such as red-black trees and AA trees), making insertion slightly slower, deletion somewhat slower, and retrieval somewhat faster (the asymptotic scaling is of course the same for all types). Thus it may be a good choice when the tree will be relatively static, i.e. data will be retrieved more often than they are modified. Internally, a tree consists of two elements, the root node and the comparison function. The actual tree has a dummy node as its root with the real root in the left pointer, which allows the root node to be treated on a par with all other nodes. Each node of the tree consists of one data element, one left sub-tree, one right sub-tree, and a balance count. The latter is the difference in depth of the left and right sub-trees. The functions with names of the form "avl-tree--" are intended for internal use only.