$5.(10\%)$ Given a sequence

K

$=$

$($

k

$1$

$,$

k

$2$

$,$

$...$

$,$

k

$6$

$)$

of $6$ distinct keys in sorted order with probabilities

$0\mathrm{.}06$

$,$

$0\mathrm{.}08$

$,$

$0\mathrm{.}10$

$,$

$0\mathrm{.}04$

$,$

$0\mathrm{.}12$

$,$

$0\mathrm{.}14.$

Some searches may be for values not in

K

$,$

and so we also have $7$ dummy keys,

d

$0$

$,$

d

$1$

$,$

$...$

$,$

d

$6$

$,$

with probabilities

$0\mathrm{.}07$

$,$

$0\mathrm{.}07$

$,$

$0\mathrm{.}07$

$,$

$0\mathrm{.}07$

$,$

$0\mathrm{.}06$

$,$

$0\mathrm{.}06$

$,$

$0\mathrm{.}06.$

Because we have probabilities of searches for each key and each dummy key, we can determine the expected cost a search in a given binary search tree

T

$.$

Suppose the expected cost of a search in

T

is

E

$[$

search cost in

T

$]$

$=$

$$

n

i

$=$

$0$

$($

d

e

p

t

h

T

$($

d

i

$)$

$+$

$1$

$)$

$$

q

i

$,$

where

d

e

p

t

h

T

denotes a node$$s depth in the tree

T

$.$

Determine the cost of an optimal binary search tree.