Consider a tree T storing 100,000 entries. What is the worst-case height of T in the following cases?

Mathematics

1 answer:

Darina [25.2K]3 years ago

6 0

Answer:

Step-by-step explanation:

a.) The worst-case height of an AVL tree or red-black tree with 100,000 entries is 2 log 100, 000.

b.) A (2, 4) tree storing these same number of entries would have a worst-case height of log 100, 000.

c.) A red-black tree with 100,000 entries is 2 log 100, 000

d.) The worst-case height of T is 100,000.

e.) A binary search tree storing such a set would have a worst-case height of 100,000.

You might be interested in

Find the expected value of the winnings from a game that has the following payout probability distribution: Skip Payout ($) 1 2

Nezavi [6.7K]

Answer:

$4.35

Step-by-step explanation:

The expected value of a random variable X, often denoted as E(X), indicates the probability-weighted average of all possible values/events. The general formula of expected value is

$\mathrm{E(\textit X \mathrm)} = \displaystyle\sum_{\mathclap{i=1}}^{k} \ X \times P(X) \\ \\ \\ = X_{1} \times P(X_{1}) \ + \ X_{2} \times P(X_{2}) \ + \ X_{3} \times P(X_{3}) + \ \cdots \ + X_{k} \times P(X_{k})$ .

Therefore, the expected value of the winnings from a game is

$\mathrm{E(\textit X \mathrm)} \ = \ 1 \times 0.35 \ + \ 2 \times 0.2 \ + \ 5 \times 0.1 + \ 8 \times 0.2 \ + 10 \times 0.15 \\ \\ = \ 4.35 \ \ (\mathrm{nearest \ hundredth})$ .