PDS - 04225 Balanced Trees - Chapter 7

Indicate whether the tree is an AVL tree

• Yes

• No

Indicate whether the tree is an AVL tree

• Yes

• No

Indicate whether the tree is an AVL tree

• Yes

• No

What is the minimum possible height of an AVL tree with 7 nodes?

• 2

• 3

• 5

• 7

Answer explanation

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. The minimum would be a perfect tree

What is the maximum possible height of an AVL tree with 7 nodes?

• 2

• 3

• 5

• 7

Answer explanation

If there are n nodes in AVL Tree, its maximum height can not exceed 1.44log₂n. Approximately 1.5 times the minimum, since the minimum is 2 , then 2 * 1.5 = 3

An AVL tree maintains the minimum possible height.

• True

• False

Which red-black tree requirement does this BST not satisfy?

• Root node must be black

• None

• A red node's children cannot be red.

• All paths from a node to a null leaf nodes must have the same number of black nodes.

Is this a valid red-black tree?.

• Yes

• No

Answer explanation

You still have to satisfy the binary tree requirements; 49 can't be to the right of 55, elements lower than the parent need to be on the left, not to the right of it.

All valid red-black trees will have more black nodes than red nodes.

• True

• False

Any BST can be made a red-black tree by coloring all nodes black.

• True

• False