binary-tree - 处理 AVL 树中的重复键

Question

我想让我的avl-tree支持重复键，但是具有重复项的默认行为存在问题，binary search tree即旋转可以使具有相同键的节点位于父级的左侧和右侧。

例如，当添加三个节点都带有键 A 时，会导致树进行旋转，如下所示：

   A
  /  \ 
 A    A

因此，使用该键获取所有条目将是一个问题……并且双向搜索并不好。

我想到的解决方案是让每个节点存储一个重复的数组，所以当添加一个已经存在的新项目时，只需向数组中添加一个新项目，使用键删除项目将删除整个节点，同时查找所有项目with key 将返回该数组。

是否有任何其他方法来处理重复？

插入项需要一个键和一个值..所以我需要存储值以便通过 findAll 使用某些键方法返回它们。

Answer 1

另一种通用方法是在内部使值成为键的一部分，这样您就不再真正拥有重复的键了。无论如何，您都需要键和值才能从允许重复的树中删除条目。

要在不知道值的情况下搜索键，您可以执行类似（伪代码）的操作：

searchResult = myTree.SearchGreaterOrEqual(Key);
found = (searchResult != null) && (searchResult.Key == Key);

Answer 2

让每个节点包含一个计数：添加重复项将增加计数，删除将减少计数，除非它为 1，在这种情况下，整个节点将被删除。