3
我正试图实现一个自我平衡二叉树。其中一个明显的内部操作是tree rotation。但是，树轮转需要考虑到其中一个子节点与父节点相同的可能性;举例来说，如果我有left <= middle < right，和我目前的节点是让平衡值位于自平衡二叉树的任一侧的缺点？
0
/\
0 1
那么我就不能顺时针旋转。但是，如果我允许在任何一方都能找到相同的价值，那么我就不必担心这一点。
到目前为止，我还没有发现任何问题......
- 的插入仍然是快速的。它仍然可以遵循
left <= middle < right并根据需要进行平衡，或者在插入相等值时找出最佳方面 - 假设您只需找到一个出现（如果值相等，则不需要拆分，因为您已经找到它）
- 删除单个节点应该没问题，因为它只是一个搜索
- 删除一个值的所有出现将需要上述拆分 - 如果我想删除A的所有发生，我会有如果我遇到了A，则搜索节点的两侧，而如果我严格保留它，那么我只需要在一侧进行搜索。但它看起来好像不会退化
- 我认为这也可以让我始终保持左侧身高不超过右侧身高的+ -1。
我想知道如果：
- 存在这样的情况在树中的任何行动将变质
- 这违反任何“一BST的原则，”任何情况下
- 还有别的什么事，我错过并应考虑
我这样做在Haskell，如果它的确与众不同
如果它们都是相同的值，为什么不存储计数而不是列表？ –
@GabrielGonzalez：在写答案时，我正在考虑一个类似地图的数据结构，而不是集合式数据结构。但是，是的，如果你只有钥匙，那么存储计数是另一种可能性。 – hugomg