如何构造二分查找树

Question

我目前正在学习二进制搜索树，如果我将这些值插入到我的树中：

13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18

那么我的二进制搜索树应该是这样的：

​

​

如果我将另一个数字15添加到树中：

13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18, 15

我的问题是第一个是否：

13
  \
   14
    \
     15
      \
       18

或者第二个：

13
  \
   14
     \
      18
      /
     15

在上面的二叉树中插入15是正确的方式吗？

Answer 1

如果你是“平常”的BST，那么第二个输出是正确的。但是，如果您正在使用平衡BST，则有可能导致树中节点的相对位置的重新排列。我很确定你正在阅读的书(或参考文献)一定有关于这个问题的解释。一般而言，当添加节点时，不对BST的先前结构(即，节点的先前位置)进行修改。然而，这可能导致“不平衡”或“倾斜”的树。这可能会导致节点的搜索时间更长。为了解决这个问题，使用了“平衡树”，如红黑树、avl树等。在这种树中，当添加节点时，通常需要对树结构进行修改。有关详细信息，请参阅以下内容：

https://en.wikipedia.org/wiki/Binary_search_tree?oldformat=true

https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree?oldformat=true

Answer 2

这两种方法都可以工作，但第一种方法与当前树的构建方式不一致。

具体来看4-12-10部分：

4
 \
 12
 /
10

数据在树中显示的级别在插入时是固定的，并且不会随着添加更多的项而改变。这就是为什么第二种方法是你正在寻找的。