我需要一些可以在 O(log(n)) 复杂度下工作的东西，我考虑过 AVL 树，但问题是某些键可能会重复自己（例如一个人的分数），所以我想不出如何将其实现为一棵树。这样做的正确方法是什么？
问问题
361 次
1 回答
1
有很多可用的选项。大多数类型的二叉搜索树都可以很容易地修改以允许具有重复值的节点，因为平衡操作（通常）纯粹由旋转组成，它使序列保持有序。对于这样的情况，您只需进行正常的 BST 插入，但每次看到重复值时，您只需随意向左或向右移动并继续，就好像该值不同一样。
跳过列表特别容易更新以支持每个键的多个副本，因为它们不会对插入或删除进行任何复杂的结构更新。
如果您没有与每个键关联的辅助信息，那么另一个更简单的选择是存储标准的二叉搜索树，但使用“计数”字段来扩充每个节点，以指示该字段存在多少逻辑副本。每次插入时，如果键不存在，则使用计数 1 创建它。如果它已经存在，则只需增加现有节点中的计数。删除将类似地实施。
当然，如果您不想滚动自己的数据结构，只需找到一个好的多映射或多集实现，它应该可以很好地为您完成工作。根据您选择的编程语言，您甚至可以在标准库中找到这些。:-)
于 2015-08-24T23:01:05.733 回答