处理AVL树中的重复键

Question

我想让我的avl-tree支持重复的关键字，但是binary search tree的默认行为有一个问题，即旋转可能会使具有相同关键字的节点位于父节点的左侧和右侧。

例如，当添加三个节点时，全部使用键A将导致树进行旋转，如下所示：

   A
  /  \ 
 A    A

因此，获取具有该键的所有条目将是一个在两个方向上都进行搜索的problem...and，这是不好的。

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

有没有其他方法来处理重复数据？

插入项接受一个键和一个值..所以我需要存储这些值，以便通过带有某些键方法的findAll返回它们。

Answer 1

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

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

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

Answer 2

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