Notation:
h height of the node
N number of nodes in one binary search tree
N(h) number of nodes on height h
As we know, binary search tree has O(h) running time on the operation, which means the complexity of BST is based on its height. If we can make the tree always keep the good height, which is
$$ h<=logN $$
\(\sqrt{2}\)
AVL Tree is a selef balanced tree with O(logN) time to do the operation.
We will prove AVL Tree is balanced as following.
Reference: https://cs.nyu.edu/courses/fall02/V22.0310-002/lectures/lecture-16.html