如何构建二叉搜索树

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的先前结构（即，节点的先前位置）进行修改。但是，这可能会导致“不平衡”或“偏斜”的树木。这可能会导致节点的搜索时间更长。为了解决这个问题，我们使用了“平衡树木”，如红黑树，大树等等。在这样的树中，当添加节点时通常会重新修改树结构。请参阅下面的详细资料：

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

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

Answer 2

这两种方法将工作，但第一个将与您当前树的构建方式不一致。

具体而言，看10年4月12日部分：

4 
\ 
12 
/
10 

在该数据显示在树被固定在插入，并且如获取添加更多的项目不会改变电平。这就是为什么第二种方法就是你要找的。