インデックス付きバイナリ ツリー

次のような問題に遭遇しました。 次の機能を提供するデータ ストレージ コンテナーを実装する必要があります。

• 新しい要素を挿入する
• シリアル番号で要素を削除する
• 要素を序数で取得する
• データはソートされた形式で保存されます

データは常に追加および削除されるため、高速な動作速度を確保できる構造にする必要があります。 最初は、標準のコンテナを使用してそのようなことを実装しようとしました STD。 この道は成功を収めることができず、自分で何かを実行する必要があると理解しました。 思いついたのは二分探索木を使うことだけでした。 これは、データの高速な挿入、削除、およびソートされた形式での保存という要件を満たしているためです。 残っているのは、すべての要素にインデックスを付け、ツリーが変更されたときにインデックスを再計算する方法を見つけ出すことだけです。

struct node_s {    
    data_t data;

    uint64_t weight; // вес узла

    node_t *left;
    node_t *right;

    node_t *parent;
};

この記事には、コードよりも多くの写真と理論が含まれます。 コードは以下のリンクでご覧いただけます。

重量

これを達成するために、ツリーはわずかに変更され、追加情報が追加されました。 重さ ノード。 ノードの重みは このノードの子孫の数 + 1 (単一要素の重量)。

ノードの重みを取得する関数:

uint64_t bntree::get_child_weight(node_t *node) {
    if (node) {
        return node->weight;
    }

    return 0;
}

それに応じてシートの重量は次のようになります。 0.

次に、そのようなツリーの例の視覚的表現に移りましょう。 ブラック ノードキーは色で表示されます（値は必要ないため表示されません）。 赤 — ノットの重み、 緑 — ノードインデックス。

ツリーが空の場合、その重みは 0 です。それにルート要素を追加しましょう。

ツリーの重みは 1 になり、ルート要素の重みは 1 になります。ルート要素の重みがツリーの重みになります。

さらにいくつかの要素を追加してみましょう。

新しい要素が追加されるたびに、ノードを下っていき、渡された各ノードの重みカウンターを増やします。 新しいノードが作成されると、それに重みが割り当てられます 1。 そのようなキーを持つノードがすでに存在する場合は、値を上書きしてルートに戻り、渡したすべてのノードの重みの変更をキャンセルします。
ノードが削除されている場合は、下に進み、渡されたノードの重みを減分します。

索引

次に、ノードにインデックスを付ける方法に移りましょう。 ノードはインデックスを明示的に保存せず、ノードの重みに基づいて計算されます。 インデックスを保存している場合は、それが必要になります O（N） ツリー内の各変更後にすべてのノードのインデックスを更新する時間がかかります。
視覚的な表現に移りましょう。 ツリーは空なので、最初のノードを追加しましょう。

最初のノードにはインデックスがあります 0と、2つのケースが考えられるようになりました。 XNUMX つ目ではルート要素のインデックスが変更されますが、XNUMX つ目では変更されません。

ルートでは、左側のサブツリーの重みは 1 です。

XNUMX番目のケース:

ルートの左側のサブツリーの重みが 0 のままであるため、ルートのインデックスは変更されませんでした。

ノードのインデックスは、その左側のサブツリーの重み + 親から渡された数値として計算されます。 この数字は何ですか?、これはインデックス カウンタです。最初は次の値に等しいです。 0、 なぜならルートには親がありません。 それから、それはすべて、左の子か右の子がどこに行くかによって決まります。 左の場合、カウンタには何も追加されません。 現在のノードのインデックスを右のノードに追加するとします。

たとえば、キー 8 の要素 (ルートの右の子) のインデックスがどのように計算されるかなどです。 これは、「ルート インデックス」 + 「キー 8 を持つノードの左サブツリーの重み」 + 「1」 == 3 + 2 + 1 == です。 6
キー 6 の要素のインデックスは、「ルート インデックス」 + 1 == 3 + 1 == になります。 4

したがって、インデックスによる要素の取得や削除には時間がかかります。 O（log n）なぜなら、目的の要素を取得するには、まずそれを見つける必要があるからです (ルートからこの要素まで下っていきます)。

深さ

重量に基づいて、木の深さを計算することもできます。 バランスをとるために必要です。
これを行うには、現在のノードの重みを、指定された重み以上の最初の 2 乗の数値に丸め、そこから XNUMX 進対数を取得する必要があります。 これにより、バランスが取れていると仮定して、ツリーの深さが得られます。 新しい要素を挿入すると、ツリーのバランスが調整されます。 木のバランスをとる方法についての理論は説明しません。 ソース コードはバランシング機能を提供します。

重さを深さに変換するコード。

/*
 * Возвращает первое число в степени 2, которое больше или ровно x
 */
uint64_t bntree::cpl2(uint64_t x) {
    x = x - 1;
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);
    x = x | (x >> 32);

    return x + 1;
}

/*
 * Двоичный логарифм от числа
 */
long bntree::ilog2(long d) {
    int result;
    std::frexp(d, &result);
    return result - 1;
}

/*
 * Вес к глубине
 */
uint64_t bntree::weight_to_depth(node_t *p) {
    if (p == NULL) {
        return 0;
    }

    if (p->weight == 1) {
        return 1;
    } else if (p->weight == 2) {
        return 2;
    }

    return this->ilog2(this->cpl2(p->weight));
}

結果

• 新しい要素の挿入が発生する O（log n）
• シリアル番号による要素の削除は、 O（log n）
• シリアル番号による要素の取得は、 O（log n）

スピード O（log n） 私たちは、すべてのデータがソートされた形式で保存されるという事実に対してお金を払っています。

このような構造がどこで役立つかわかりません。 木の仕組みをもう一度理解するためのパズルです。 ご清聴ありがとうございました。

リファレンス

• ツリーのソースコード

プロジェクトには動作速度を確認するためのテストデータが含まれています。 木が埋まってきています 1000000 要素。 要素の連続的な削除、挿入、取得が行われます。 1000000 一度。 あれは 3000000 オペレーション。 結果は非常に良好でした〜8秒。

出所： habr.com