最优二叉搜索树

使用二叉搜索树可以节约搜索的时间。搜索某个节点的时间，等于该节点的深度+1。

希望文本中出现频繁的的单词和根节点较近，较少出现的单词最好能离根节点越远越好。

最优二叉搜索树的期望搜索代价最低。但是最优二叉搜索树的高度不一定是最矮的。

考虑搜索失败的问题。如果要搜索的值没有在二叉搜索树里面，就表示搜索失败。对不在二叉搜索树里面的值，需要使用虚叶子结点。

最优二叉搜索树关键思想: 最优二叉搜索树的子树也必然是最优二叉搜索树。