- A binary tree whose subtrees have exactly the same height (or
alternatively called
*depth*) is an AVL tree. - Searching in
a perfectly balanced ordered binary tree with
*n*nodes requires*O(log n)*steps - Inserting a new element into an AVL tree requires on average more steps than inserting an element into an ordinary ordered binary tree.
- Every tree with a height of at most two is an AVL tree.
- Searching in a degenerated ordered binary tree, that is a tree with maximal height, has the same work complexity as searching in a list.

Gabriele Keller Last modified: Mon Oct 29 14:58:56 EST 2001