##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
Tracing the classic example
Build BST with minimum expected search cost. Keys have access frequencies . = min cost for keys to .
Transition: pick root . Cost = (depth increases by 1 for all nodes). QI holds for this cost function. Apply Knuth: . Fill by increasing interval length. Each searches bounded range. Total: .
