AVLツリーでサイズkの頂点を見つける

Question

をa個の頂点を持つAVLツリーとする。 各頂点には、頂点自体をルートとしてそのサブツリーのサイズを表す拡張があります。私は入力として数k s.tを取得するアルゴリズムを実装しようとしています。 1 < = k < = nとし、サイズkの頂点をO（logn）に返します。

ツリーが完全なバイナリツリーの場合、高さhのすべてのノードが同じサイズになるため、必要なサイズのノードに到達するまで右/左に移動するのは簡単です。しかし、木が満ちていないときは、私は立ち往生しています。

ご協力いただければ幸いです。

ありがとうございます！

P.S.私は各頂点が異なる値を持つと仮定します。

Answer 1

まず、左側のサブツリーがkより大きいかどうかを確認します。 それ以外の場合は、左のサブツリーのサイズ+ 1がkに等しいかどうかをチェックします。その場合、現在の要素がkthなので、現在のノードを返します。 これまでのところでは、k番目の要素が右のサブツリーにあることを意味しているので、右のサブツリーに移動し、k - （左のサブツリーのサイズ+1）要素を検索します。すでにこれらのノードをすべて削除しました。