AVL tree
lastmod 2020-09-20created 2020-09-134 edits
The AVL tree is the earliest balanced binary search tree. It was published in 1962 by G.M. Adelson-Velskii and E.M. Landis in their paper "An algorithm for the organization of information" and is named after them. An AVL tree keeps, at each node (branch point), information about the height difference between its left and right sub-trees, and has the property that the height difference of the sub-trees is not greater than 1. A balanced AVL tree with n elements can search, insert, and delete in O(log n) time complexity. However, because insertion and deletion require 2 paths to find the desired node, it is not as efficient as the red-black tree and is not often used.