What is purpose of AVL tree?

Answer 1

AVL TreesIn computer science, an AVL tree is the first-invented self-balancing binary search tree. In an AVL tree the heights of the two child subtrees of any node differ by at most one, therefore it is also known as height-balanced. Lookup, 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 two inventors, G.M. Adelson-Velsky and E.M. Landis, who published it in their 1962 paper "An algorithm for the organization of information."

The balance factor of a node 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 any other balance factor is considered unbalanced and requires rebalancing the tree. The balance factor is either stored directly at each node or computed from the heights of the subtrees.

Answer 2

Binary Search trees offer improved average case performance for searching. However, if they are unbalanced their search performance degrades to that of a linked list. AVL trees guarantee that the difference in height of any two subtrees rooted at the same node will be at most one. This guarantees an asymptotic running time of O(log(n)) as opposed to O(n) in the case of a standard bst.

Answer 3

An AVL tree is most commonly used in computer science and was named after its inventors. It is a self-balancing binary search tree which automatically keeps its height. The purpose of this is to provide efficient implimentations for ordered lists.

Answer 4

An AVL tree is a self-balancing binary search tree. This was the first data structure that was invented and is named after their inventors.

Answer 5

Avl tree is self binary tree in which balancing factor lie

between the -1 to 1.It is also known as self balancing tree.

so BF=h(T(left sub tree))-h(T(right sub tree));