Tree Questions: Example

• 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.