3

假设我有一个具有以下节点定义的二叉树。 


struct node
{
 int key1 ;
 int key2 ;
}

二叉搜索树是在key1的基础上创建的。现在可以根据 O(1) 空间中的 key2 重新排列二叉搜索树。尽管我可以使用指向节点的指针数组在变量空间中执行此操作。

我需要这个的实际问题是“计算文件中唯一单词的出现次数并以频率降序显示结果”。这里，一个 BST 节点是 


{
 char *word;
 int freq ;
}
BST 首先是根据单词的字母顺序创建的，最后我想要它基于频率。

我在选择数据结构（即 BST）时错了吗？

4

6 回答 6

1

在您选择的语言中使用 HashTable (Java) 或 Dictionary (.NET) 或等效数据结构（STL 中的 hash_set 或 hash_map）将在计数阶段为您提供 O(1) 次插入，这与在某处的二叉搜索树不同插入时从 O(log n) 到 O(n) 取决于它是否平衡自身。如果性能真的那么重要，请确保您尝试将 HashTable 初始化为足够大的大小，这样它就不需要动态调整自身大小，这可能会很昂贵。

至于按频率列出，如果不涉及排序，我无法立即想到一种棘手的方法，即 O(n log n)。

于 2009-08-13T13:39:31.243 回答
1

如果您需要为您的字典排序输出，则 Map、BST 很好。

如果您需要混合添加、删除和查找操作，这很好。我不认为这是你在这里的需要。您加载字典，对其进行排序，然后只在其中查找，对吗？在这种情况下，排序数组可能是更好的容器。（参见Scott Meyer的Effective STL中的第 23 项）。
（更新：只需考虑一个映射可能比排序数组产生更多的内存缓存未命中，因为数组在内存中获取其数据连续，并且映射中的每个节点都包含指向映射中其他节点的 2 个指针。当您的对象是简单并且在内存中占用的空间不多，排序向量可能是更好的选择。我强烈建议您阅读 Meyer 书中的那个项目）

关于您正在谈论的那种排序，您将需要来自 stl: stable_sort的算法。这个想法是对字典进行排序，然后在频率键上使用 stable_sort() 进行排序。

它会给出类似的东西（实际上没有测试，但你明白了）：

struct Node
{
char * word;
int key;
};

bool operator < (const Node& l, const Node& r)
{
    return std::string(l.word) < std::string(r.word));
}

bool freq_comp(const Node& l, const Node& r)
{
    return l.key < r.key;
}

std::vector<node> my_vector;
... // loading elements
sort(vector.begin(), vector.end());
stable_sort(vector.begin(), vector.end(), freq_comp);
于 2009-08-13T13:43:34.010 回答
1

这是我根据新键重新平衡树的建议（嗯，我有 2 条建议）。

第一个也是更直接的一个是以某种方式适应 Heapsort 的“起泡”功能（使用 Sedgewick 的名称）。这是维基百科的链接，他们称之为“筛选”。它不是为完全不平衡的树（这是您所需要的）而设计的，但我相信它展示了树的就地重新排序的基本流程。可能有点难以理解，因为树实际上是存储在数组中而不是树中（尽管某种意义上的逻辑将其视为树） --- 不过，也许你会发现这样一个基于数组的代表是最好的！谁知道。

我的更疯狂的建议是使用张开树。我认为它们很漂亮，这是wiki 链接。基本上，您访问的任何元素都会“冒泡”到顶部，但它保持 BST 不变量。因此，您保持原始 Key1 用于构建初始树，但希望大多数“较高频率”值也将位于顶部附近。这可能还不够（因为这意味着高频词将“靠近”树的顶部，不一定以任何方式排序），但如果你碰巧拥有或找到或制作了一棵树-平衡算法，它可能在这样的展开树上运行得更快。

希望这可以帮助！谢谢你的一个有趣的谜语，这对我来说听起来像是一个很好的 Haskell 项目..... :)

于 2009-08-13T16:32:37.587 回答
1

您可以在 O(1) 空间中轻松完成此操作，但不能在 O(1) 时间内完成；-)

尽管递归地重新排列一棵树直到它再次排序似乎是可能的，但它可能不是很快 - 它最多可能是 O(n)，在实践中可能更糟。因此，在完成树后将所有节点添加到数组中，并使用快速排序频率（平均为 O(log n)）对该数组进行排序，您可能会获得更好的结果。至少那是我会做的。即使很难，它也需要额外的空间，这对我来说听起来比重新布置树更有希望。

于 2009-08-13T16:45:02.447 回答
1

我认为您可以创建一棵按排序的新树freq并将所有从旧树中弹出的元素推送到那里。

这可能是O(1) 虽然可能更像O(log N)是无论如何都不大。

Also, I don't know how you call it in C#, but in Python you can use list but sort it by two different keys in-place.

于 2009-08-14T01:10:15.990 回答
0

您可以考虑的一种方法是构建两棵树。一个由 索引word，一个由 索引freq。

只要树节点包含指向数据节点的指针，您就可以通过word基于 - 的树访问以更新信息，但稍后通过freq- 基于树访问它以输出。

虽然，如果速度真的那么重要，我希望摆脱字符串作为键。字符串比较是出了名的慢。

如果速度不重要，我认为您最好的选择是根据yves 的建议收集数据word并重新排序。freq

于 2009-08-13T13:55:37.777 回答