处理AVL树中的重复密钥 [英] Handling duplicates keys within an AVL tree

问题描述

我想使我的 avl-tree 支持重复键，但是 binary search tree 的默认行为存在问题，因为重复操作会导致节点旋转用相同的键位于父级的左侧和右侧.

I want to make my avl-tree support duplicate keys but there is a problem with the default behavior of the binary search tree with duplicates that the rotation could make nodes with equal key be on the left and the right of the parent.

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

For example when adding three nodes all with key A will cause the tree to do a rotation to be something like this:

   A
  /  \ 
 A    A

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

So getting all the entries with that key will be a problem...and searching in both direction is not good.

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

The solution that i have thought of is making each node stores an array of duplicates so when adding a new item that already exists will be just adding a new item to the array , removing item with key will delete the whole node while the find all items with key will return that array.

还有其他方法可以处理重复项吗?

Are there are any other methods to handle duplicates ?

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

The insert item takes a key and a value .. so i need to store the values inorder to return them by the findAll with certain key method.

推荐答案

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

Another general approach is to internally make the value part of the key so that you don't really have duplicate keys anymore. You'll need both the key and the value anyway in order to delete an entry from a tree that allows duplicates.

要在不知道值的情况下搜索键，则需要执行类似(伪代码)的操作:

To search for a key without knowing the value, you would then do something like (pseudo-code):

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

这篇关于处理AVL树中的重复密钥的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！