2

我的 bst 必须能够处理重复的条目。有没有人有任何不需要过多代码的策略来解决这个问题?我想一直在右侧添加重复项,但这会弄乱 bst 顺序。例如,当副本有两个孩子又有两个孩子时会发生什么?插入副本很容易,但是如何处理它替换的节点?

4

3 回答 3

3

只要它不是自平衡 BST,我认为将相等的节点放在与它们相等的节点的左侧或右侧都没有问题。

编辑(在西蒙的评论之后):

如果有问题的“重复节点”已经​​有2个孩子,那么只需将“新重复节点”插入左侧,让“旧重复节点”的左孩子成为“新重复节点”的左孩子。

让我用一个例子来澄清一下。插入副本之前的树:

    4'
   / \
  2   5
 / \
1   3

现在元素4''被插入:

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

只要树不是自平衡的,你应该没问题。

于 2009-10-10T12:37:16.050 回答
2

您可以将二叉搜索树的节点制作成链表。

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>();    
}

在这里,treeNode.items始终是一个非空列表,例如item1.compareTo(item2) == 0对于 everyitem1item2in treeNode.items

要插入重复元素,您将找到相关TreeNode对象并将新项目添加到items.

查找元素的逻辑与之前的几乎相同,只是一旦找到相关TreeNode对象就必须遍历链表。

于 2009-10-10T12:17:12.947 回答
0

我想知道您是否真的需要将重复的条目存储为单独的节点?向您的节点添加一个计数器变量就足够了吗?这样,如果您遍历树,您将知道重复条目的数量并仍然保留顺序。

于 2012-06-21T18:26:10.077 回答