如何使用具有多个重复键值或其他替代方法的二叉树
How to use a binary tree with multiple duplicated key values or other alternative
我正在使用 Java 开展一个项目，我从电影商店网站检索有关电影的数据。所以我得到了一个评级数字 x（从 0 到 5 的整数）和一个类别 y（例如 "horror"）。我必须 return y 类别中评分最低为 x 的电影。最重要的是，我必须使用不会遍历每部电影的数据结构来检索此数据。
所以我首先想到对每个类别实施一个二叉树，其中关键是评分（从 0 到 5）。所以在这种情况下，我会有一些重复的键，但无论如何都会将值添加到树中。起初它似乎有效，但我陷入了困境：如果我想检索最低评级 x 的电影并且只有一部评级为 x 的电影（它是树的叶子），我找不到办法检索其他 >= x 电影。
我还尝试了 Java 中的 TreeMap。但是它不允许重复的密钥，所以它不会在这个项目上工作。
有人可以帮助我吗？我想要一些关于如何解决二叉树问题的建议。或其他选择。
一般来说，二叉树可能支持也可能不支持重复键，这取决于实现细节。如果您使用的是不支持重复键的实现，例如 Java 中的 TreeMap，您仍然有多种选择。
使用多图
有一个名为 Multimap 的结构，它允许每个键存储多个值。您可以像现在一样存储类别树，然后按每个类别的评分存储 multimap（而不是 map，因为您现在正在做）。标准 java 集合中没有 multimap 实现，但是有无数的开源实现可用。 For example Google Guava Multimap.
使用复合键
将所有电影存储在单个 TreeMap 中，使用复合键 - (Category, Rating, GeneratedUniqueIntegerForDisambiguation) 的三元组。比较器会先比较类别，如果它们相同，然后比较评级，如果它们仍然相同，然后生成的 int。
Treemap 支持高效的区间查询subMap(fromKey, toKey)。因此可以像这样检索评级至少为 3 的恐怖：
map.submap(new MyKey("horror", 3, Integer.MIN_VALUE), new MyKey("horror", 5, Integer.MAX_VALUE))
我正在使用 Java 开展一个项目，我从电影商店网站检索有关电影的数据。所以我得到了一个评级数字 x（从 0 到 5 的整数）和一个类别 y（例如 "horror"）。我必须 return y 类别中评分最低为 x 的电影。最重要的是，我必须使用不会遍历每部电影的数据结构来检索此数据。
所以我首先想到对每个类别实施一个二叉树，其中关键是评分（从 0 到 5）。所以在这种情况下，我会有一些重复的键，但无论如何都会将值添加到树中。起初它似乎有效，但我陷入了困境：如果我想检索最低评级 x 的电影并且只有一部评级为 x 的电影（它是树的叶子），我找不到办法检索其他 >= x 电影。
我还尝试了 Java 中的 TreeMap。但是它不允许重复的密钥，所以它不会在这个项目上工作。
有人可以帮助我吗？我想要一些关于如何解决二叉树问题的建议。或其他选择。
一般来说，二叉树可能支持也可能不支持重复键，这取决于实现细节。如果您使用的是不支持重复键的实现，例如 Java 中的 TreeMap，您仍然有多种选择。
使用多图
有一个名为 Multimap 的结构，它允许每个键存储多个值。您可以像现在一样存储类别树，然后按每个类别的评分存储 multimap（而不是 map，因为您现在正在做）。标准 java 集合中没有 multimap 实现，但是有无数的开源实现可用。 For example Google Guava Multimap.
使用复合键
将所有电影存储在单个 TreeMap 中，使用复合键 - (Category, Rating, GeneratedUniqueIntegerForDisambiguation) 的三元组。比较器会先比较类别，如果它们相同，然后比较评级，如果它们仍然相同，然后生成的 int。
Treemap 支持高效的区间查询subMap(fromKey, toKey)。因此可以像这样检索评级至少为 3 的恐怖：
map.submap(new MyKey("horror", 3, Integer.MIN_VALUE), new MyKey("horror", 5, Integer.MAX_VALUE))