1

質問が述べているように、平衡二分探索木でキー「k」の後継者を見つけるアルゴリズムを見つけようとしています。バランスの取れた BST は AVL ツリーと同じだと思います (間違っていたら訂正してください)。O(log n) 時間で 1 回のパスでこれを実行できることを望んでいましたが、私が見つけたすべてのことは、ツリーの右側を下ってから左側を下る必要があると言っています。私はツリー全体に慣れていないので、まだ少し混乱しています。どんな助けでも大歓迎です！

ありがとう。

4

2 に答える 2

1

二分探索木では、下に行くための 2 つのパス オプションがあります:左または右です。ここで、ノードNに要素kがあるとします。kよりも大きいツリーの最小要素であるkの後継者を見つけたいと考えています。

ここには 3 つの使用例があります。

  • Nには NULL でない右の子があります:右のサブツリーの左端の要素はkの後継要素です。
  • Nにはそのような右の子はなく、親Pの左の子です。この場合、Pはkの後継者を保持します。
  • 最後に、Nはその親Pの右の子です。次に、その後継者を見つけるには、以下に示すより複雑な手順に従う必要があります...

S = Parent(P)から開始: S ≠ Root AND P ≠ Left(S)

  1. P ← S
  2. S ← 親(S)

S = Root およびP = Right(S)の場合、kはツリーの最大要素でした...それ以外の場合は、S ← Right(S)を設定した後、次のループを実行します。

S ≠ NULL の場合:

  1. P ← S
  2. S ← 左(S)

このループが終了すると、Pはkの後続を保持します。

于 2013-10-30T18:31:14.813 に答える
0

キー k を持つノードに右のサブツリーがある場合、それはそのサブツリーの左端のノードです。それ以外の場合、キー k を持つノードが左の子である場合、それはこのノードの親です。それ以外の場合は、右のサブツリーを持つ直接の親以外のノードの最も近い祖先を見つけます。これは、そのサブツリーの最も左のノードです。そのような祖先が存在しない場合、ノードは最大であり、後続ノードはありません。

ツリーはバランスが取れているため、O(log n) で常に見つけることができます。

于 2013-10-30T18:30:41.310 に答える