BST 根的特殊属性 - 中间值？

Question

如果将 BST 的所有值放入排序数组中，是否始终保证 BST 的根节点是 BST 的“中间”值？

假设数组中的第一个元素默认为根，数组中的所有其他元素将根据 BST 排序结构放置在 BST 中（较小的节点位于左侧，较大的节点位于右侧）。

如果不总是“中间值”，什么情况下是中间值？

Answer 1

BST 无法保证其根值是多少。例如，如果按升序插入值，则根将是最小值。如果按降序插入值，根将是最大值。

如果你选择AVL树作为BST，这样它是自平衡的，那么你可以限制根值作为值的可能性，但仍然不能保证它是中间值。例如，如果按顺序插入值 3、2、7、1、5、8、4、6、9，那么即使是 AVL 树也不会应用任何重新平衡操作，因此值 3 将保留在根，而中间值 5 位于树的第三层：

        3
       / \
      2   7
     /   / \
    1   5   8  
       / \   \
      4   6   9