3

I'm trying to implement a self balancing binary tree for practice. One of the obvious internal operations is a tree rotation. However, a tree rotation needs to take account the possibility that one of the child nodes is the same as the parent node; for example, if I have left <= middle < right, and my current node is

  0
 / \
0   1

Then I can't rotate clockwise. However, if I were to allow equal values to be found on either side, then I wouldn't have to worry about that.

So far I haven't found any problems...

  • Insertions could still be fast. It could still follow left <= middle < right and balance as needed, or figure out the optimal side when inserting equal values
  • Searches would be unaffected, assuming you just need to find a single occurences (no need to split if the values are equal, because you've already found it)
  • Deleting a single node should be fine because its just a search
  • Deleting all occurences of a value would require the aforementioned splitting - if I want to delete all occurences of A, I'd have to search both sides of the node if I encountered A, whereas if I kept it strictly left <= middle < right (or vise versa) I'd only have to search one side. But it doesn't seem like it'd degenerate
  • I think it also lets me always keep the height on the left side no more than +-1 from the heigh on the right side.

I'm wondering if:

  • There are any cases where any operations on the tree would degenerate
  • This violates any "principles of a BST"
  • There's anything else I missed and should consider

I'm doing this in Haskell, if it makes a difference

4

1 回答 1

0

正如您已经设法找到自己的那样，在树上多次使用相同的密钥并没有根本性的问题。

我认为这里最大的问题是找出具有相同键的多个键值对在您的问题域中意味着什么 - 之后选择要做什么变得更加简单。例如，在每个节点中存储一个值列表而不是单个节点可能会使搜索和删除操作不那么模糊，如果有多个值没有意义，那么用新值替换旧值可能更合适......

于 2013-09-30T14:35:30.777 回答