読者です 読者をやめる 読者になる 読者になる

競プロ記録

問題を解いた際に自分の復習用として使ってます

二分探索木:探索

競技プログラミング

アルゴリズムとデータ構造】二分探索木:探索(解説)

215ページの解説をしていきます。

 

まずどこから探索していくかの基準となるxと調べる値kを引数として受け取ります。

そのあとxをどんどん移していくのですがそのxの値が存在しなくなるまたは、keyにたどり着くまでループ内の作業を繰り返します。

kの値がその基準のxよりも小さい場合にはxを左の子へ移し、大きい場合にはxの子を右の子へ移します。

 

この操作を繰り返すことで、節点を探し出すことができます。

 

以上解説でした。