Strategy to find duplicate entries in a binary search tree

 

I have a BST which has duplicate entries. I am trying to find duplicate entries. Now obviously I can write a dumb algorithm which traverses the whole tree, which is easy.

However, I want to write a more efficient one. Here's what I've done/thought so far:

Assume the following tree. 

      10
     /   
    5    15
   /    / 
  2  8   10 16
          
       8   12

If I want to find all 8's, I will first find the 8 on the left subtree of the 10. To find a duplicate, if it has no right child, is it going to be the left-most node on the right-subtree of the the first parent that is larger than that node (8)? And if it did have a right child, then it can be either in the left most node of its right subtree or the right most node on its left subtree?

Are those all the cases, which can be achieved with a bunch of loops and if-statements?

If not, what's a better approach? Can anyone help?

Thanks

EDIT: Actually I just realized it can't be the "left most node" or "right most node". That would find the node that is the next highest value or the previous lowest value. Would it be one node before?

EDIT 2:

Fixed my BST example. It follows the following insertion method: 

if (node == null) 
    return new NodeBST<Value>(name, value);

if (node.key().compareTo(name) > 0)
    node.setLeft(insert(node.left(), name, value));     
else
    node.setRight(insert(node.right(), name, value));

This means duplicates will be added to the right of their duplicates.. right?

  • Find an element that matches your key using the usual binary tree search algorithm. If not found, stop.
  • Examine the LH sub-branch. If its key matches, make that the current node and repeat this step.
  • You are now at the first element in the tree with that key. Now do a tree walk from this node while the keys are equal, ie visit this node, the right sub-tree, the parent, the parent's right sub-tree, etc, left as an exercise for the reader.

    • The tree you show assumes (well, at least I assume... ;-)) that less-than are on the left, and greater-than are on the right, am I right?

    So there are two things you should consider:

  • Your tree is wrong! The second "8" on the right of the "10" head cannot be there, since it's less-than 10. A correct insertion, and a correct balancing, would both put in very close, if not right at the "next" iteration from the "left 8".

  • By defining the tree as "less-than-or-equal" on the left, and "greater-than" on the right, you would get the wanted result: all "8"s will be chained to the left of each other on a simple insertion tree.

    • A recursive algorithm can solve this quickly. You do not have to recurse over the whole tree, as you can use the structure of the BST to hunt down the values you need.

    What you have drawn isn't strictly a BST, I might be wrong, but I believe it's pretty broken - all numbers in the left tree should be less than 10, and vice versa.

    链接地址: http://www.djcxy.com/p/55410.html

    上一篇: 重写动态网址

    下一篇: 在二叉搜索树中查找重复条目的策略