为什么以(反向)顺序添加节点会导致搜索效率低下？

Question

我正在准备考试,我偶然发现了以下问题:

绘制二进制搜索树,如果要按以下顺序添加数据,将会产生这种结果:

10,9,8,7,6,5,4,3

为什么树不适合高效搜索？

我的答案:

我想在创建BST时,我们以值10作为根节点开始,然后在第一级添加9作为左子树值.然后是8到9的左子树,依此类推.我不知道为什么这会使搜索效率低下.有任何想法吗？

Answer 1

由于值按递减顺序排列,因此它们会在每个级别添加到左侧,实际上会为您留下一个链接列表,该列表需要O(N)进行搜索,而不是BST的首选O(logN).

画画:

              10
             /
            9
           /
          8
         /
        7
       /
      6
     /
    5
   /
  4
 /
3