c++ - 排序一个vector，然后放入AVL树，还是直接输入哪个更快？

Question

情况是这样的:

我有数百万(可能是数十亿)个字符串，我正在尝试解析这些字符串并将其放入排序结构中，假设我有 5,000,000 个字符串。我正在尝试编写一个快速程序，可以将所有这些字符串从一个未排序的 vector 放入一个有序的数据结构中，该结构也可以快速搜索结构，因此是 AVL 树的推理(最终我计划使用哈希表的 a-z 用于更快的查找，但稍后会出现)。我首先将所有字符串放入一个 vector 中，但它们都乱七八糟，未排序且长度不同。我不想在我的树中出现任何重复的字符串，因此如果程序找到字符串“hello”和“hello”，它将只有一个 AVL 条目，并且会增加一个整数持有者以表示该字符串出现的频率。

所以我的问题是:首先对 vector 进行排序(使用诸如多线程快速排序或其他快速排序之类的东西)然后将其输入到 AVL 树中，在所有单词与其他单词一起排序后是否会更快相同的词，或者只是将未排序 vector 中的所有数据放入 AVL 树，并不断检查 AVL 树是否已经存在一个词，然后递增它是否更快。

所以按照操作顺序来描绘它是两种情况:

CASE A:

> Get input/parse strings
> Put strings into vector (unsorted)
> Put vector into array or linked-list
> Quicksort that array/llist
> Input that sorted array into the AVL Tree

CASE B:

> Get input/parse strings
> Put strings into vector (unsorted)
> Insert vector data into AVL tree
> During insertion, check if there are duplicate words, if so, increment the counter

哪种情况更快？？

--编辑-- 因此，在听到一些评论后，从一开始就将排序数组插入 AVL 树中将是一个坏主意，因为有多少次旋转是有道理的制成。看起来直接插入到 AVL 树中可能是个好主意，但是当一个词已经在树中某处时，高效插入的最佳方法是什么？我怎样才能确保找到它？这是我的排序可以发挥作用的地方吗？

Answer 1

想想 AVL 树的平衡方式。如果“中间值”先出现，效果最好。对于已排序的输入，您将需要大量的重新平衡，因此预排序可能弊大于利。

例如，考虑以下包含值 1-6 的 AVL 树:

    4
   / \
  2   5
 / \   \
1   3   6

如果输入顺序是 4, 2, 5, 1, 3, 6，您永远不需要平衡树。相反，对于已排序的输入 1, 2, 3, 4, 5, 6，您将需要许多重新平衡操作:

  1     +3     2     +4     2       +5     2       +6       3
   \   --->   / \   --->   / \     --->   / \     --->     / \
    2        1   3        1   3          1   4            2   5
                               \            / \          /   / \
                                4          3   5        1   4   6

---

更新 最初的问题是在插入 AVL 树之前对数据进行排序是否会提高性能。现在 OP 编辑​​了问题，转向了他的具体问题。

but what is the best way to efficiently insert when a word is already in the tree somewhere? How can I make sure that I find it? Is that where my sorting can come in?

AVL 树的全部意义在于有效地查找数据，所以我不明白这个问题。如何遍历二叉搜索树来找到一个值应该是显而易见的。为什么要为此对数据进行排序？

请注意，二叉搜索树是一种很好的存储键的数据结构，但它也可以管理与这些键关联的任意数据。在您的情况下，您希望将计数与 key 一起存储。因此，您不需要单词/字符串树，而是代表单词及其计数的对(字符串、整数)树。对于树顺序，只需考虑字符串键，即单词。

对于每个要插入的单词，在树中查找它。如果它已经存在，更新字数。否则，插入一个字数为 1 的新对。

最后一点:C++ 标准库带有一个 map 类型，通常(总是？)使用平衡树(AVL 或红黑)实现。仅使用此实现，您就可以省去大量工作和错误修复工作。自 C++11 以来，还有一个 unordered_map，通常(总是？)使用哈希表实现。