java - 在二叉搜索树中查找重复条目的策略

Question

我有一个包含重复条目的 BST。我正在尝试查找重复的条目。现在显然我可以编写一个遍历整棵树的愚蠢算法，这很容易。

但是，我想写一个更高效的。这是我到目前为止所做/想到的:

假设下面的树。

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

如果我要找出所有的8，我会先找到10的左子树上的8。要找到重复的，如果它没有右 child ，它是否会是右边的最左边的节点-大于该节点 (8) 的第一个父节点的子树？如果它确实有一个右 child ，那么它可以在其右子树的最左节点或左子树的最右节点？

这些都是可以通过一堆循环和 if 语句来实现的情况吗？

如果不是，什么是更好的方法？谁能帮忙？

谢谢

编辑:其实我只是意识到它不能是“最左边的节点”或“最右边的节点”。这将找到下一个最高值或上一个最低值的节点。之前会不会是一个节点？

编辑 2:

修复了我的 BST 示例。它遵循以下插入方法:

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

这意味着重复项将添加到其重复项的右侧..对吧？

Answer 1

1. 使用通常的二叉树搜索算法找到与您的键匹配的元素。如果没有找到，停止。
2. 检查 LH 支行。如果它的键匹配，则将其设为当前节点并重复此步骤。
3. 您现在位于树中具有该键的第一个元素。现在从该节点出发，在键值相等的情况下进行树遍历，即访问该节点、右子树、父节点、父节点的右子树等，留给读者作为练习。