如何構建二叉搜索樹

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 

在該數據顯示在樹被固定在插入，並且如獲取添加更多的項目不會改變電平。這就是爲什麼第二種方法就是你要找的。