在AVL树中处理重复键

Question

10

我想让我的avl树支持重复的键，但是默认的二叉搜索树在处理重复键时存在问题，因为旋转操作可能会导致具有相同键的节点位于其父节点的左右两侧。

例如，当添加三个具有键A的节点时，树会执行旋转操作，使其变成以下结构：

   A
  /  \ 
 A    A

因此，获取该键的所有条目将是一个问题...并且在两个方向上搜索都不好。

我想到的解决方法是使每个节点存储一个重复项的数组，因此当添加一个已经存在的新项目时，只需将一个新项目添加到数组中，删除具有关键字的项目将删除整个节点，而找到具有关键字的所有项目将返回该数组。

还有其他处理重复项的方法吗？

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

- Ahmed Kotb

2个回答

3

让每个节点都包含一个计数器：重复的添加操作将增加计数器，删除操作将减少计数器，除非计数器为1，否则整个节点将被删除。

- jball

我忘了说树需要一个键和一个值，所以我必须存储这些值以便在findall方法中返回它们... - Ahmed Kotb

1

请澄清一下，单个键将存储不同的值（而非重复值）？如果是这样，您提出的值数组解决方案对我来说看起来很好。 - jball

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- 500 - Internal Server Error · Accepted Answer

另一种通用方法是将值内部作为键的一部分，这样您就不会再有重复键了。在允许重复项的树中删除条目时，您仍需要键和值。

如果要查找键而不知道值，则可以执行以下操作（伪代码）：

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