0

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) {}
};
4

2 に答える 2

2

二分探索木の n 番目に小さい要素を単独で効率的に検索することはできません。ただし、サブツリー全体のノード数を示す整数を各ノードに保持すると、これが可能になります。私の一般的なAVLツリーの実装から：

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()います。

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

于 2012-04-28T12:05:51.747 に答える
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

私は提案された変更をテストしていませんが、それらはあなたを進歩のための正しい方向に導くはずです

于 2012-04-28T11:54:10.377 に答える