这是最优二叉搜索树吗？
Is this an optimal 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
在这个
正如你在书中看到的那样 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