Tree Questions: Example
Which of the following five statements is incorrect?
- 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