dealing with duplicates in a bst

My bst has to be able to cope with duplicate entries. Does anyone have any strategies for how to go about this that doesn't require excessive amounts of code? I thought of consist开发者_Python百科ently adding duplicates to the right but then that will mess up the bst order. for example what happens when the duplicate has two children who in turn have two children?. inserting the duplicate is easy enough, but what is to be done with the node it replaced?

As long as it's not a self balancing BST, I don't see a problem with putting equal nodes either at the left or right of the node that is equal to them.

Edit (after simonn's remark):

If the "duplicate node" in question already has 2 children, then simply insert the "new duplicate node" to the left and let the left child of the "old duplicate node" become the left child of the "new duplicate node".

Let me clarify with an example. The tree before inserting a duplicate:

    4'
   / \
  2   5
 / \
1   3

And now the element 4'' is inserted:

      4'
     / \
    4'' 5
   /
  2   
 / \
1   3

As long as the tree is not self balancing, you should be okay.

You could make the nodes of the binary search tree into linked lists.

class Data implements Comparable<Data>
{
   // These are the data elements in your binary search tree
}

class TreeNode
{
  TreeNode left; // elements less than current node, or null
  TreeNode right; // elements greater than current node, or null
  List<Data> items = new LinkedList<Data>();    
}

Here, treeNode.items is always a non-empty list, such that item1.compareTo(item2) == 0 for every item1 and item2 in treeNode.items.

To insert a duplicate element, you would find the relevant TreeNode object and add a new item to items.

The logic of finding elements is almost the same as you had before, except that once you find the relevant TreeNode object you have to walk the linked list.

I wonder if you actually need to store the duplicate entries as separate nodes? Would adding a counter variable to your Node be enough? That way if you traverse the tree you would know the number of duplicate entries and still preserve the order.