將大樣本放在二叉搜索樹上（不平衡）

Question

我需要從一個擁有200多萬行（每行會給我一對key/val）的文件構造一個二叉搜索樹。由於數據是有序的，所以如果我只讀了一行，得到key和val並添加到我的樹中，高度會很大，這樣樹就無法搜索。所以，我在想如果有一個好的方法來構建這個搜索樹，使它沒有很大的高度。 我的嘗試是獲得第100000個密鑰，隨機播放，放在樹上等，但它似乎沒有多少效率。任何建議？我不得不使用不平衡的搜索樹。

謝謝！

Answer 1

如果您可以多次讀取文件，您可以第一次讀取文件，並讀取列表中的1000個條目（即每2000行一個），然後進行第一次平衡插入，以便首先將元素插入位置500然後兩個位置250和750然後位置4位置125,375,625,975等 第一遍之後，您可以讀取整個文件（並管理重複項）並獲得更平衡的樹。

另一種方法是根本不使用BinarySearchTree，而是使用Array，因爲數據是有序的，所以可以使用二分搜索（您檢查數組中間的值，並且如果您獲得的值較大，則重複對列表的前半部分進行操作，它使用列表的後半部分的值更低）;但我不知道使用列表是否符合您的要求。

Answer 2

作爲一個方面說明，創建BST當你已經交給一個有序陣列是一種瘋狂的事情，但與一旁......

如果你給一個有序陣列已經，它實際上給了你如何構建一個最小高度平衡BST的答案。爲簡單起見，假設數組是：

[0,1,2,3,4,5,6,7,8,9,10]

在這種情況下，這將是在根本上存儲一個平衡樹的最佳元素？自然的答案是列表的中間，5。

那麼接下來我們留下與陣列的兩個子範圍：

i<5: [0,1,2,3,4] 
i>5: [6,7,8,9,10] 

那麼，什麼是被存儲在左邊的孩子理想的元素？我們再次走左邊子列表（i<5）的中心，這將是2，我們有陣列的兩個子範圍：

i<2: [0,1] 
i>2: [3,4] 

而直到我們離開，我們可以遞歸重複這個邏輯只有一個孩子或兩個範圍內都沒有，此時我們創建了一個葉節點。

遞歸地應用到每個分支的兩側，鑽到樹葉上，這會給你最佳的平衡樹。