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

Question

我有一个BST,它有重复的条目.我想找到重复的条目.现在显然我可以编写一个遍历整个树的哑算法,这很容易.

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

假设以下树.

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

如果我想找到所有8个,我将首先找到10的左边子树上的8个.要找到重复的,如果它没有正确的子节点,它将是右子树的最左边节点第一个父节点大于那个节点(8)？如果它确实有一个正确的子节点,那么它可以位于其右子树的最左侧节点,也可以位于其左侧子树的最右侧节点上？

那些是所有的情况,可以用一堆循环和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. 您现在位于树中带有该键的第一个元素。现在，在键相等的情况下，从该节点开始进行树遍历，即访问该节点、右子树、父节点、父节点的右子树等，留给读者作为练习。