将大样本放在二叉搜索树上（不平衡）

我需要从一个拥有200多万行（每行会给我一对key/val）的文件构造一个二叉搜索树。由于数据是有序的，所以如果我只读了一行，得到key和val并添加到我的树中，高度会很大，这样树就无法搜索。所以，我在想如果有一个好的方法来构建这个搜索树，使它没有很大的高度。我的尝试是获得第100000个密钥，随机播放，放在树上等，但它似乎没有多少效率。任何建议？我不得不使用不平衡的搜索树。将大样本放在二叉搜索树上（不平衡）

谢谢！

来源

2015-05-29 Giiovanna

如果已经订购了数据，那么最好使用数组或List来进行二分搜索。否则，你需要构建一个平衡的树，否则你会得到一个烂摊子......正如我所说，我需要使用二进制搜索树不平衡的 –

。 – Giiovanna

这可能会让你感兴趣http://stackoverflow.com/questions/30521757/would-this-algorithm-run-in-on – dejvuth

如果您可以多次读取文件，您可以第一次读取文件，并读取列表中的1000个条目（即每2000行一个），然后进行第一次平衡插入，以便首先将元素插入位置500然后两个位置250和750然后位置4位置125,375,625,975等第一遍之后，您可以读取整个文件（并管理重复项）并获得更平衡的树。

另一种方法是根本不使用BinarySearchTree，而是使用Array，因为数据是有序的，所以可以使用二分搜索（您检查数组中间的值，并且如果您获得的值较大，则重复对列表的前半部分进行操作，它使用列表的后半部分的值更低）;但我不知道使用列表是否符合您的要求。

来源

2015-05-29 14:45:37 Giovanni

作为一个方面说明，创建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]

而直到我们离开，我们可以递归重复这个逻辑只有一个孩子或两个范围内都没有，此时我们创建了一个叶节点。

递归地应用到每个分支的两侧，钻到树叶上，这会给你最佳的平衡树。

来源

2015-05-29 15:20:10

将大样本放在二叉搜索树上（不平衡）

回答

相关问题