A self-balancing binary search tree in which the heights of a node's two child subtrees differ by at most one, rebalanced through rotations after insertion or deletion so that search, insertion and deletion all stay logarithmic.
Facts
Core PrincipleA self-balancing binary search tree in which the heights of the two child subtrees of any node differ by no more than one; an insertion or deletion that breaks this balance triggers one or more tree rotations to restore it. 1 Connections
Sources
1. Wikipedia: AVL tree
Wikimedia FoundationLead section, second paragraph
The AVL tree is named after its two Soviet inventors, Georgy Adelson-Velsky and Evgenii Landis, who published it in their 1962 paper "An algorithm for the organization of information".
Lead section, first paragraph
In an AVL tree, the heights of the two child subtrees of any node differ by not more than one; if at any time they differ by more than one, rebalancing is done to restore this property.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.