19.2 Draw all binary search trees that can result from inserting permutations of

Question

19.2 Draw all binary search trees that can result from inserting permutations
of 1, 2, 3, and 4. How many trees are there? What are the probabilities
of each tree’s occurring if all permutations are equally
likely?

(10 points) Exercise 19.2 included finding the probability (based on equally likely insertion orders of each of the 24 permutations) of each of the 14 different trees that can result when inserting the numbers 1, 2, 3, and 4 into an initially empty BST (with no re-balancing).

(a) With the same assumption (that all permutations of the four numbers are equally likely), what is the (weighted) average height of the BSTs?

(b) With the same assumptions, do the same exercise for inserting the four numbers into an AVL tree. In other words, what is the average height of the AVL trees?

Explanation / Answer

There are 24 permutations of these numbers (4 x 3 x 2 x 1 = 24). Each insert order gives rise to a particular tree, but sometimes the same tree occurs for 2 different permutations. For example, inserting 3124 and 3241 and 3214 all make the same tree.

In parentheses I list the number of possible insertion sequences that give the same tree.

1234 (1), 1243 (1), 1324 (2), 1423 (1), 1432 (1),
2143 (3), 2134 (3),
3214 (3), 3124 (3),
4321 (1), 4312 (1), 4213 (2), 4123 (1), 4132 (1).

14 trees are possible, their probabilities are calculated from the number in brackets as eg, 1/24, 2/24 or 3/24

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.