6

AVL ツリー ウィキペディアのページに次のコメントがあることに気付きました。

「各ノードがそのサブツリーのサイズ (それ自体とその子孫を含む) を追加で記録する場合、ノードは O(log n) 時間でインデックスによって取得することもできます。」

私はグーグルで検索し、インデックスによるアクセスについて言及している場所をいくつか見つけましたが、作成するアルゴリズムの説明を見つけることができないようです。

どうもありがとう

[更新] ありがとうございます。@templatetypedef の回答が見つかった場合は、@user448810リンクの 1 つと組み合わせて、特に役立ちます。特にこのスニピット：

「これら両方の機能の鍵は、ノードのインデックスがその左の子のサイズであるということです。左の子を介してツリーを下降している限り、ノードのインデックスを取得するだけです。しかし、移動する必要がある場合右の子を介してツリーをたどると、除外したツリーの半分が含まれるようにサイズを調整する必要があります。」

私の実装は不変であるため、各ノードが構築時にサイズを計算するため、リバランス時に追加の作業を行う必要はありませんでした (リンクされたスキーム impl と同じ)。

私の最終的な実装は次のようになりました。

class Node<K,V> implements AVLTree<K,V> { ...
    public V index(int i) {
        if (left.size() == i) return value;
        if (i < left.size()) return left.index(i);
        return right.index(i - left.size() - 1);
    }
}

class Empty<K,V> implements AVLTree<K,V> { ...
    public V index(int i) { throw new IndexOutOfBoundsException();}
}

これは他の実装とは少し異なります。バグがあると思われる場合はお知らせください。

4

1 に答える 1

11

この構造の背後にある一般的な考え方は、既存の BST を取得し、左側のサブツリーにノードの数を格納することで各ノードを拡張することです。これが完了したら、次の再帰アルゴリズムを使用して、ツリー内の n 番目のノードを検索できます。

  • ルート ノードの左側のサブツリーに k 個の要素がある BST の n 番目の要素を検索するには、次のようにします。
    • k = n の場合、ルート ノードを返します (これはツリーの 0 番目のノードであるため)
    • n ≤ k の場合、左部分木の n 番目の要素を再帰的に検索します。
    • それ以外の場合は、右側のサブツリーで (n - k - 1) 番目の要素を検索します。

これには時間 O(h) がかかります。ここで、h は木の高さです。AVL ツリーでは、これは O(log n) です。CLRS では、この構成を赤/黒ツリーに適用するものとして検討しており、そのようなツリーを「順序統計ツリー」と呼んでいます。

左側のサブツリーにキャッシュされた要素の数を調整するには、ツリーのローテーション中に追加のロジックを追加する必要がありますが、これは特に難しいことではありません。

お役に立てれば！

于 2012-06-08T21:04:35.427 に答える