AVL Trees

AVL Tree is a balanced binary search tree. The post introduced binary search trees. The search, insertion, and deletion times for a binary tree depend on the height of the tree. In the worst case, the height is O(n). If a tree is perfectly balanced–i.e., a complete binary tree—its height is log n. Can we maintain a perfectly balanced tree? Yes, but doing so will be costly. The compromise is to maintain a well-balanced tree—that is, the heights of every node’s two subtrees are about the same.

AVL trees are well balanced. AVL trees were invented in 1962 by two Russian computer scientists, G. M. Adelson-Velsky and E. M. Landis (hence the name AVL). In an AVL tree, the difference between the heights of every node’s two subtrees is 0 or 1. It can be shown that the maximum height of an AVL tree is O(log n).

The process for inserting or deleting an element in an AVL tree is the same as in a regular binary search tree, except that you may have to rebalance the tree after an insertion or deletion operation. The balance factor of a node is the height of its right subtree minus the height of its left subtree. A node is said to be balanced if its balance factor is -1, 0, or 1. A node is considered left-heavy if its balance factor is -1, and right-heavy if its balance factor is +1.

The above is the detailed content of AVL Trees. For more information, please follow other related articles on the PHP Chinese website!