构建二叉搜索树时的比较次数

Question

我正在自学二叉搜索树。有一道题是在一棵最初为空的树中插入字母E、A、S、Y、Q、U、E、S、T、I、O、N，需要比较多少次才能建树。

我画了二叉搜索树，统计了插入每个元素时的比较次数。

 E 
/ \
A  S
   /\
  Q  Y
 /   /
 E   U
 \   /
  I  S
   \  \
    O  T
    /
    N

我得到了 36.

对吗？还有，有没有不用画树就知道比较次数的方法？

Answer 1

比较次数为 36 次。

您可以得出结论，在 BST 中插入一个元素的最大比较次数不会超过树的高度。

Answer 2

对我来说，我得到的比较次数是48次。

本次构建的最大比较次数如下：

1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + 6 + 6 + 7 = 48

每个元素插入比较如下：（1 + 节点的深度）。因此，如果我将要插入的元素的所有比较加起来，构建 BST，我将得到上面的答案 48.

Number of comparisons when building a binary search tree