binary-search-tree - 这是最优二叉搜索树吗？
问题描述
在这个发布的问题中，图 15.9 (b) 被认为是期望搜索成本为 2.75 的最优树，但是通过将 k_3 子树与叶子 d_0 交换，我们可以获得 2.65 的预期搜索成本，我的推理有什么不正确的吗？
解决方案
正如你在书中看到的那样 K = {k1; k2;:::;kn} 的 n 个不同键按排序顺序（因此 k1 < k2 < k3< k4 < k5）
因为图 15.9 (a) 和图 15.9 (b) 都是 BST，所以如果使用前序遍历，它们的顺序相同：k1=>k2=>k3=>k4=>k5
通过将 k_3 子树与叶子 d_0 交换，如果您使用前序遍历，顺序将会改变：k3=>k1=>k2=>k4=>k5