c++ - 在 C++ 中将字符串插入 AVL 树？

Question

我了解 AVL 树如何与整数一起工作。但我很难找到一种将字符串插入其中的方法。如何比较字符串？

我曾想过只使用 ASCII 总值并以这种方式排序。但在这种情况下，插入两个相同的 ASCII 词（例如“tied”和“diet”）似乎会返回错误。

你如何解决这个问题？我是否以错误的方式思考它，并且需要一种不同的方式来对节点进行排序？

不，它们不需要按字母顺序排列或任何东西......只需在 AVL 树中，这样我就可以快速搜索它们。

Answer 1

处理字符串时，通常使用词法比较——即，从每个字符串的第一个字符开始。如果一个小于另一个（例如，“diet”与“tied”，“d”小于“t”），则比较基于该字母。当且仅当第一个字母相等时，您转到第二个字母，依此类推。仅当从字符串的开头到结尾的每个字符（按顺序）都相等时，两者才相等。

Answer 2

好吧，由于 AVL 树是有序结构，因此该int string::compare(const string&) const例程应该能够告诉您如何对字符串进行排序。

如果项目的顺序实际上无关紧要，那么您将从可以更好地利用您正在尝试做的事情的无序结构中获得更好的性能：哈希表。

将字符串等映射到固定大小的键称为散列函数，将多个键映射到同一个值的现象称为冲突。预计在散列时偶尔会发生冲突，并且需要扩展基本数据结构来处理它，可能通过使每个节点成为所有项目的“桶”（链表，向量，数组，你有什么）碰撞哈希值，然后线性搜索。