Working with duplicates in bst
My bst should be able to handle duplicate entries. Does anyone have any strategies for how to do this that doesn't require inordinate amount of code? I was thinking about constantly adding duplicates to the right, but then it will mess up the order of bst. for example, what happens when the duplicate has two children, who in turn have two children? inserting a duplicate is easy enough, but what about replacing a node?
source to share
While this is not a self balancing BST, I see no problem with placing equal nodes either to the left or right of a node equal to them.
Edit (after simonn's comment):
If the "duplicate node" already has 2 children, just 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 explain with an example. Tree before inserting the duplicate:
4'
/ \
2 5
/ \
1 3
And now the element is inserted 4''
:
4'
/ \
4'' 5
/
2
/ \
1 3
As long as the tree is not balancing itself, you should be fine.
source to share
You can turn the nodes of a 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 is treeNode.items
always a non-empty list such as item1.compareTo(item2) == 0
for each item1
and item2
in treeNode.items
.
To insert a duplicate item, you will find the matching object TreeNode
and add the new item to items
.
The logic for finding items is pretty much the same as before, except that once you find a matching object TreeNode
, you need to traverse the linked list.
source to share