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

Question

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

例如，当添加三个都带有键 A 的节点时，将导致树进行如下旋转:

   A
  /  \ 
 A    A

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

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

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

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

Answer 1

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

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

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