Balanced tree -A tree where no leaf is much farther away from the root than any other leaf.

Different balancing schemes allow different definitions of "much farther" and different amounts of work to keep them balanced. 

Height Balanced Tree aka AVL Tree  (Inventors G.M. Adel’son-Vel’skii and E.M. Landis), are self-balancing binary search trees.

An AVL tree is one that requires heights of left and right children of every node to differ by at most ±1.

AVL Tree (Height Balanced Tree) - A tree whose subtrees differ in height by no more than one and the subtrees are height-balanced, too.

An empty tree is height-balanced.

 

Time Complexity

Space Complexity

 

Average

Worst

Worst

Data Structure 

 Access 
 Search 
 Insertion 
 Deletion 
 Access 
 Search 
 Insertion 
 Deletion 
 

AVL Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)