バイナリツリーキーに最も近い数値と大きい数値を見つける

Question

バランスのとれたバイナリツリーがあるとします。私はツリー内のキーkを検索したい。しかし、kがバイナリツリーに存在しない場合は、kに最も近い次の最大の番号を与えるはずです。例については

は、私は、ツリーのキーとして[1,5,6,8,10]これらの番号を持っていると仮定します。私は「7」で検索した場合には、8返すべきであると私は2を検索した場合、それは返すべきである5など

何な検索を行うことができるように、バイナリツリー内の変更でなければならないであろうか？私はO（ログn）ソリューションもしたいです。あなたは「二分探索木」ではなく「バイナリ木」を意味すると仮定すると、

Answer 1

は、あなたがツリーように、Y> = xの最小要素yを見つけるために、任意の変更を必要としません。

search(n, x, best_so_far) ::= 
    if n == nil { return best_so_far } 
    if n.value == x { return x } 
    if n.value > x { return search(n.left, x, min(best_so_far, n.value) } 
    if n.value < x { return search(n.right, x, best_so_far) } 

あなたはsearch(root, x, +infinity)としてこの関数を呼び出します。

ノードnの左のブランチを探索する場合、nの右側には何も考慮する必要はありません。n.valueはxより大きく、すべての右側がすべて大きくなりますn.valueよりも。同様に、ノードnの右の分岐を探索している場合、nの左側にあるすべてを破棄することができます。n.valueはxより小さく、nの左側はすべてn.valueより小さくなります。

コードの実行時間がツリーの高さによって制限されるツリーが平衡である場合、これはO（ログn）です。