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

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

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

像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

最好的树具有最小的平均值和最小的最大深度。换句话说，最好的树已完全填充了每个级别（最后一个级别除外）。

例如，即使下面的两棵树具有相同数量的节点，并且具有相同的最大深度，但左侧的树并不是最小高度树，因为它缺少第三级的节点（这意味着平均深度会大于右侧的树）。