バイナリ検索ツリーでn番目に小さい要素を見つける

Question

BSTでn番目に小さい要素を見つけるアルゴリズムを書いたが、n番目に小さいものの代わりにルートノードを返す。したがって、ノードを7 4 3 13 21 15の順番で入力すると、find（root、0）の呼び出し後のこのアルゴリズムは、3ではなく7のNodeを返し、find（root、1）の呼び出しでは4の代わりに13を返します。思考？

Binode* Tree::find(Binode* bn, int n) const 
{ 
    if(bn != NULL) 
    { 

    find(bn->l, n); 
    if(n-- == 0) 
     return bn;  
    find(bn->r, n); 

    } 
    else 
     return NULL; 
} 

とBinode

class Binode 
{ 
public: 
    int n; 
    Binode* l, *r; 
    Binode(int x) : n(x), l(NULL), r(NULL) {} 
}; 

Answer 1

の定義コードを持ついくつかの問題がある：

1）意図したとおりに機能を想定値（正しいノードが、動作している戻りfind()）はその値を呼び出しチェーンに伝播しないので、トップレベルの呼び出しは、（見つかった）見つかった要素について知りません

Binode* elem = NULL; 
elem = find(bn->l, n); 
if (elem) return elem; 
if(n-- == 0) 
    return bn;  
elem = find(bn->r, n); 
return elem; // here we don't need to test: we need to return regardless of the result 

2）あなたは正しい場所にnの減少を行うにもかかわらず、変更が呼び出しチェーンで上向きに伝播しません。このパラメータは参照によって渡される必要があります（関数シグネチャ内のintの後に&を書き留めておきます）。したがって、変更は元の値で行われます。

です。

Binode* Tree::find(Binode* bn, int& n) const 

効率的にそれ自体で二分探索木のn番目の最小の要素を取得することはできません、私が提案した変更をテストしていませんが、彼らが進行

Answer 2

のために正しい方向にあなたを置く必要があります。ただし、各ノードにサブツリー全体のノード数を示す整数を保持すると、これが可能になります。 my generic AVL tree implementationから：

static BAVLNode * BAVL_GetAt (const BAVL *o, uint64_t index) 
{ 
    if (index >= BAVL_Count(o)) { 
     return NULL; 
    } 

    BAVLNode *c = o->root; 

    while (1) { 
     ASSERT(c) 
     ASSERT(index < c->count) 

     uint64_t left_count = (c->link[0] ? c->link[0]->count : 0); 

     if (index == left_count) { 
      return c; 
     } 

     if (index < left_count) { 
      c = c->link[0]; 
     } else { 
      c = c->link[1]; 
      index -= left_count + 1; 
     } 
    } 
} 

上記のコードで

、node->link[0]とnode->link[1]nodeの左と右の子であり、node->countはnodeのサブツリー全体のノード数です。

上記のアルゴリズムは、ツリーが均衡していると仮定すると、O（logn）時間の複雑さを持ちます。また、これらのカウントを保持すると、別の操作が可能になります。ノードへのポインタがあれば、インデックス（効率的にインデックスを求めることができます）を求めることができます。リンクされたコードでは、この操作はBAVL_IndexOf()と呼ばれます。

ツリーが変更されるとノードの数を更新する必要があることに注意してください。これは、時間の複雑さの変化なしに（漸近的に）行うことができる。