AVL tree Guide, Meaning , Facts, Information and Description

In computer science, an AVL tree is a self-balancing binary search tree where the height of the two child subtrees of any node differ by at most one, also known as height-balanced. Look-up, insertion and deletion are all O(log(n)) in both the average and worst cases. Additions and deletions may require the tree to be rebalanced by one or more tree rotations. The AVL tree is named after its inventors, Adelson-Velskii and Landis, who designed it in 1962.

Each node in the tree has a balance factor stored in the node. This balance factor is the height of its right subtree minus the height of its left subtree. A node with balance factor -1,0, or 1 is considered balanced. A node with balance factor -2 or 2 is considered unbalanced and requires rebalancing the tree.

Inserts require at most one single or double rotation.

See also

• splay tree
• red-black tree
• B-tree

• Description from the Dictionary of Algorithms and Data Structures
• AVL Tree Traversal
• Linked AVL tree
• C++ AVL Tree Template and C AVL TREE "Generic Package" by Walt Karas
• A Visual Basic AVL Tree Container Class by Jim Harris
• AVL Trees: Tutorial and C++ Implementation by Brad Appleton
• Ulm's Oberon Library: AVLTrees
• The AVL TREE Data Type
• CNAVLTree Class Reference
• GNU libavl
• AVL-trees - balanced binary trees by Alex Konshin
• Simulation of AVL Trees
• AVL tree applet

This is an Article on AVL tree. Page Contains Information, Facts Details or Explanation Guide About AVL tree

	Web www.E-paranoids.com