二叉搜索树中的第二大元素 [英] Next largest element in a binary search tree

问题描述

我正在寻找一种简单的算法来查找二叉搜索树中的下一个最大元素(键)，有人可以帮忙吗?

I'm looking for a simple algorithm to find the next largest element (key) in a binary search tree, can anyone help?

推荐答案

假设下一个最大节点"是指当前节点所在位置的下一个最大节点...

Assuming that by "next largest," you mean, the next largest node from wherever the current node is...

在当前节点上，向右走一次.您去了一个价值更高的节点.然后，尽可能多地向左走.您已在价值最低的节点处结束，该节点仍比起点高.

From the current node, go right once. You've gone to a higher valued node. Then, go left as many times as possible. You've ended at the lowest valued node which is still higher than where you started.

_{(来源:在cs.lmu.edu发出的光线)}

示例.从60开始，向右走一次，向左走尽可能多的次数.您最终排名62.

Example. Start at 60, go right once, go left as many times as you can. You end up at 62.

对41尝试相同的操作.最终将变为42.

Try the same thing for 41. You will end up at 42.

这应该有助于您解决第二种情况.伪代码:

This should help with your second case. Pseudocode:

If (current.hasNoRightChild)
    testParent = current
    nextLargest = maxValueInTree
    While (testParent.hasParent)
        testParent = current.Parent
        If (testParent > current  && testParent < nextLargest)
            nextLargest = testParent
            While (testParent.hasLeftChild)
                testLeftChild = testParent.testLeftChild
                If (testLeftChild > current && testLeftChild < nextLargest)
                    nextLargest = testLeftChild
                End if
            End while
        End if
    End while
End if

不能保证没有错误，但是通常的想法是您检查每个父级，然后慢慢地走到树顶.在每个节点上，停下来查看是否是下一个最大节点"的候选对象(即，该节点大于您从其开始的节点，并且小于当前猜测的下一个最大节点).在这些停靠点的每个停靠点，如果节点大于开始位置，则必须仅在左分支的该节点的子树下一直进行探索，并检查整个过程中的每个值.我认为应该这样做，但是您可能应该使用随机值对其进行大量测试，以确保没有任何其他情况我们被忽略.

Can't guarantee no bugs in that, but the general idea is you check each parent, slowly working your way to the top of the tree. At each node, you stop and see if it is a candidate to be the "next largest" (i.e. it is greater than the node you started from and less than the current guess of next largest). At each of these stops, if the node is greater than where you started, you must explore all the way down the subtree of that node on the left branch only, checking each value along the way. I think that should do it, but you should probably test it heavily with random values to make sure there aren't any other cases we've overlooked.

这篇关于二叉搜索树中的第二大元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！