处理 AVL 树中的重复键
我想让我的 avl-tree 支持重复键，但是带有重复项的二叉搜索树的默认行为存在问题，旋转可能会使节点具有相同的键位于父母的左侧和右侧。
例如，当添加三个都带有键 A 的节点时，将导致树进行如下旋转：
A
/ \
A A
因此，获取具有该键的所有条目将是一个问题......并且在两个方向上搜索都不好。
我想到的解决方案是让每个节点存储一个重复项数组 因此，当添加已存在的新项目时，只需将新项目添加到数组中， 删除带有键的项目将删除整个节点，而查找带有键的所有项目将返回该数组。
还有其他方法可以处理重复项吗？
插入项需要一个键和一个值..所以我需要存储这些值，以便通过 findAll 使用某些键方法返回它们。
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.
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.
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 ?
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
让每个节点包含一个计数：添加重复项将增加计数，删除将减少计数，除非它为 1，在这种情况下，整个节点将被删除。
Have each node contain a count: addition of duplicates will increment the count, removals will decrement the count unless it's 1, in which case the whole node will be removed.
另一种通用方法是在内部将值作为键的一部分，这样就不再有重复的键了。无论如何，您都需要键和值才能从允许重复的树中删除条目。
要在不知道值的情况下搜索键，您可以执行类似的操作（伪代码）：
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):