AVL tree

views updated

AVL tree (height-balanced tree) A binary search tree such that for each node the heights of the left and right subtrees differ by at most one. Thus the balance of each node is –1, 0, or +1. During insertion or deletion, a node in an AVL tree may become critical or unbalanced and then the tree has to be reorganized to maintain its balanced property. The tree is named for its originators, Adel'son-Vel'skii and Landis.