理解二叉搜索树的构建方式

Question

我很难理解二叉搜索树是如何构建的。它们需要初始数据按顺序排序才能找到最顶层的根吗？

- George L

Answer 1

二叉搜索树的形状取决于两个因素：

1. 元素插入的顺序。 2. 插入期间树执行的平衡操作（如果有）。

如果您拥有一个没有任何重新平衡逻辑的纯二叉搜索树，则元素插入的顺序将对树的形状产生很大影响。例如，取值为1、2、3、4、5、6、7。如果按照4、2、6、1、3、5、7的顺序插入它们，则会得到以下树形结构：

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

这是因为我们要经历以下一系列树结构：

     4

     4
   /
  2

     4
   /   \
  2     6 

     4
   /   \
  2     6
 /
1

     4
   /   \
  2     6
 / \
1   3

     4
   /   \
  2     6
 / \   /
1   3 5

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

另一方面，如果按照1、2、3、4、5、6、7的顺序插入值，则会得到以下树形结构:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6
           \
            7

有趣的是，按照排序顺序将元素插入BST是最糟糕的事情之一，因为它会使树成为线性结构。最好选择元素的随机排列方式进行插入，或者（如果它们都提前知道）对排序后的序列使用以下递归算法：

• 如果没有元素，则完成。
• 否则：
  • 将中位数插入BST。
  • 递归地将元素的前半部分插入BST。
  • 递归地将元素的后半部分插入BST。

希望这能帮到你！

- templatetypedef

---

将中位数插入BST。因此，为了获得中位数值，我首先必须按顺序排列线性数据，例如5,3,6,2,4,1必须重新排序为1,2,3,4,5,6，然后4将成为根节点？ - George L

@GeorgeL- 我不确定我理解你的评论。你能澄清一下吗？ - templatetypedef

抱歉，我没有意识到按下回车键会提交评论。 - George L

@GeorgeL - 如果你想要一个最优的二叉搜索树，你需要事先对数据进行排序，或者使用一个至少与排序数据一样多的算法。 - templatetypedef

@GeorgeL- 话虽如此，BST的根节点（除非BST使用平衡算法）始终是第一个插入的元素。 - templatetypedef