处理AVL树中的重复键

Question

我想让我的avl-tree支持重复键，但与binary search tree与重复的默认行为的问题，即旋转可以使具有相同的关键节点是在左边，父权。

例如添加三个节点时所有密钥A将导致树做旋转是这样的：

   A
  /  \ 
 A    A

因此，让所有与该键条目将是一个问题...在这两个方向搜索是不好的。

，我曾想到的溶液使每一个节点存储重复的阵列 所以加入已经存在将只是增加一个新的项目到阵列的新项目时， 与键删除项目将删除整个节点，而找到钥匙的所有项目将返回数组。

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

在插入项需要一个关键字和一个值..所以我需要存储的值序由用的findAll某些关键方法返回它们。

Answer 1

另一种通用的方法是在内部使键的值的部分，这样你就真的没有重复键了。你会为了删除一个树允许重复的条目需要两个键和值呢。

要搜索键不知道的价值，你会那么做类似（伪代码）：

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

Answer 2

让每个节点包含一个计数：除了重复的将递增计数，清除将减小计数，除非它是1，在这种情况下，整个节点将被移除

。