- A binary tree whose subtrees have exactly the same height (or
alternatively called
*depth*) is an AVL tree.*False*: the following tree has subtrees of the same height, but is not AVL, since only the topmost node is balanced:Node 0 5 / \ Node 2 4 Node -2 6 / \ / \ Node 1 3 Leaf Leaf Node -1 7 / \ / \ Node 0 2 Leaf Leaf Node 0 7 / \ / \ Leaf Leaf Leaf Leaf

- Searching in
a perfectly balanced ordered binary tree requires
*O(log n)*steps*True* - Inserting a new element into an AVL tree requires on average
more steps than inserting an element into an ordinary ordered binary
tree.
*True*: to preserve the AVL property, it might be necessary to rotate the nodes which requires a constant number of additional steps. - Every tree with a height of at most two is an AVL tree.
*True*: The two subtree can have at most height 1, so they height cannot differ by more than 1. - Searching in a degenerated ordered binary tree, that is a tree with maximal
height, has the same work complexity as searching in a list.
*True*: A degenerated tree has the same shape as a tree. It's height is propotional to the number of nodes.

Gabriele Keller Last modified: Mon Oct 29 14:59:18 EST 2001