-3

二分探索木で次に大きな要素 (キー) を見つける簡単なアルゴリズムを探しています。

4

2 に答える 2

3

「次に大きい」とは、現在のノードがどこにあるかに関係なく、次に大きいノードを意味すると仮定します...

現在のノードから、右に 1 回進みます。より価値の高いノードに移動しました。次に、できるだけ多く左に移動します。開始した場所よりもまだ高い、最も低い値のノードで終了しました。

ここに画像の説明を入力
(ソース: cs.lmu.edu の光線)

例。60 から始めて、右に 1 回、左に何度でも移動します。あなたは62歳で終わります。

41 についても同じことを試してください。42 になります。

編集：

これは、2 番目のケースに役立つはずです。擬似コード:

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

バグがないことを保証することはできませんが、一般的な考え方は、各親をチェックし、ゆっくりとツリーのトップに向かって作業することです。各ノードで停止し、それが「次の最大」の候補であるかどうかを確認します (つまり、開始したノードよりも大きく、次の最大の現在の推定よりも小さい)。これらの各ストップで、ノードが開始した場所よりも大きい場合は、そのノードのサブツリーの左側のブランチのみを探索し、途中で各値を確認する必要があります。そうするべきだと思いますが、見落としている他のケースがないことを確認するために、ランダムな値を使用して十分にテストする必要があります。

于 2012-12-07T05:37:51.000 に答える
1

ケース 1: 右 (x) は空ではない 後継 (x ) = 右 (x) の最小値 ケース 2: 右 (x) は空 現在のノードが左の子になるまでツリーを上る: 後継 (x ) はさらに先に進めない (そしてルートに到達した) 場合の現在のノードの親: x は最大の要素です

于 2012-12-07T05:42:44.557 に答える