algorithm - 二叉搜索树的最小高度插入顺序

Question

因此，在类里面，我的练习之一是找到导致具有最小高度和最大高度的二叉搜索树的插入顺序。插入的数字是[1,2,3,4]。最终的答案是这样的:

图3.9:

但是我无法理解的是，为什么插入订单 1324,1342,4213,4231 不包含在导致最小高度的插入订单中，因为从技术上讲，这些不会导致最小高度为 2 的 BST还有吗？

提前谢谢您!

Answer 1

有趣的是，文本中没有提到这四种情况。它们没有最坏情况下的高度，但也不是最小的。树有两个特征:

• 从根到任意节点的最大深度
• 从根到任意节点的平均深度

像 1432 这样的树，最大深度为 3，平均深度 (0+1+2+3)/4 = 1.50
像 3124 这样的树的最大深度为 2，平均深度 (0+1+1+2)/4 = 1.00
像 1324 这样的树的最大深度为 2，但平均深度 (0+1+2+2)/4 = 1.25

最好的树具有最小的平均值以及最小的最大深度。换句话说，最好的树的每一层(除了最后一层)都被完全填满。

例如，即使下面的两棵树具有相同的节点数和相同的最大深度，左侧的树也不是最小高度树，因为它缺少第三层的节点(这意味着平均深度将大于右侧的树)。