**AVL** tree(Adelson-Velsky and Landis tree named after it’s inventor) is a height-balanced Binary Search Tree such that the difference between the height of a left subtree and a right subtree (of a node) is 1, 0 or -1. It has the following properties:

- It should be a Binary Search Tree i.e, key in the left subtree are always less than or equal to the root, and key in right subtree should be greater than root.
- The difference between the hight of left subtree and right subtree is known as balance factors and its value should always be 1, 0, -1.
- The left and right subtrees should also be AVL trees.

##### Balance Factor

Balance Factor is the difference between the height of the left subtree and the right subtree and its value should be -1, 0, or 1.

BalanceFactor = height(left subtree) – height(right subtree)

BalanceFactor ∈ {-1, 0, 1}

##### Example

### The time complexity of various operations on an AVL tree

## Algorithm / Operation |
## Average Case |
## Worst Case |

Height | O(log N) | O(log N) |

Search | O(log N) | O(log N) |

Insert | O(log N) | O(log N) |

Delete | O(log N) | O(log N) |

Tree Traversal | O(N) | O(N) |

The reason AVL is better than BST is that most of its operation takes O(log N) time in worst case too as compared to BST where in worst-case time complexity becomes O(N), where N is the number of nodes in the tree.

##### Height

The maximum height of an AVL tree is floor(log_{2 }N) can’t exceed 1.44*log_{2}N, where N is the number of nodes in the given tree.

Given the height of an AVL tree as h, the maximum number of nodes it can have is 2^{h}^{+}^{1} – 1 and the minimum number of nodes it can have is given by the formula:

N(h) = N(h-1) + N(h-2) + 1 for n>2 where N(0) = 1 and N(1) = 2.