HN 日本語サマリー

← 一覧へ戻る
プログラミング

Treap (Cartesian Tree)

Treap (Cartesian Tree) (cp-algorithms.com)

8 pointsby vismit20000 コメント

要約

Treap（ツリーとヒープを組み合わせたデータ構造）は、キーXと優先度Yのペアを二分探索木（X基準）かつ二分ヒープ（Y基準）として格納します。ランダムな優先度を割り当てることで、平均O(log N)の操作効率を持つ非退化な木構造を保証します。SplitとMerge操作を基本とし、挿入、削除、構築、和集合などの操作を効率的に行えます。また、サブツリーサイズの管理や、オフラインでのO(N)構築、インプリシットトレアプによる配列ライクな操作も可能です。

全文翻訳

Treap (Cartesian Tree)

Treapは、二分木と二分ヒープ（Tree + Heap $\Rightarrow$ Treap）を組み合わせたデータ構造です。

より具体的には、Treapは $(X, Y)$ のペアを二分木に格納し、Xに関しては二分探索木、Yに関しては二分ヒープの性質を満たすようにします。木のノードが $(X_0, Y_0)$ を含む場合、左部分木内のすべてのノードは $X \leq X_0$ を満たし、右部分木内のすべてのノードは $X_0 \leq X$ を満たします。また、左右両方の部分木内のすべてのノードは $Y \leq Y_0$ を満たします。

Treapは「Cartesian Tree」とも呼ばれます。これは、デカルト平面に埋め込みやすいからです。

［画像: Treapの構造を示す図］

Treapは1989年にRaimund SiedelとCecilia Aragonによって提案されました。

このようなデータ編成の利点

この実装では、$X$ の値はキー（同時にTreapに格納される値）であり、$Y$ の値は優先度と呼ばれます。優先度がない場合、TreapはXに関する通常の二分探索木となり、Xの値のセットによっては多くの異なる木構造（例えば、連結リストのような退化した構造）に対応する可能性があり、それらは極端に遅くなる可能性があります（主要な操作の複雑性は $O(N)$ になります）。

同時に、優先度（一意である場合）は、構築される木を一意に指定することを可能にします（もちろん、値が追加される順序には依存しません）。これは対応する定理によって証明できます。明らかに、優先度をランダムに選択すると、平均して非退化な木が得られ、主要な操作の $O(\log N)$ の複雑性が保証されます。したがって、このデータ構造のもう一つの名前はランダム化二分探索木です。

操作

Treapは以下の操作を提供します：

  • 挿入 (X,Y): $O(\log N)$。
    新しいノードを木に追加します。1つの可能なバリアントは、Xのみを渡し、操作内でYをランダムに生成することです。
  • 検索 (X): $O(\log N)$。
    指定されたキー値Xを持つノードを検索します。実装は通常の二分探索木と同じです。
  • 削除 (X): $O(\log N)$。
    指定されたキー値Xを持つノードを検索し、木から削除します。
  • 構築 ($X_1$, ..., $X_N$): $O(N)$。
    値のリストから木を構築します。これは線形時間で行うことができます（$X_1, ..., X_N$ がソートされていると仮定）。
  • 和集合 ($T_1$, $T_2$): $O(M \log (N/M))$。
    2つの木をマージします。要素がすべて異なることを前提としています。重複要素をマージ中に削除する必要がある場合でも、同じ複雑性を達成できます。
  • 積集合 ($T_1$, $T_2$): $O(M \log (N/M))$。
    2つの木の積集合（つまり、共通の要素）を見つけます。この操作の実装はここでは扱いません。

さらに、Treapは二分探索木であるため、$K$ 番目に大きい要素を見つける、要素のインデックスを見つけるなどの他の操作も実装できます。

実装の説明

実装の観点からは、各ノードは $X$、$Y$、および左 ($L$) と右 ($R$) の子へのポインタを含みます。

必要なすべての操作は、2つの補助操作、SplitとMergeのみを使用して実装します。

Split

［画像: Split操作の概念図］

Split ($T$, $X$) は、木 $T$ を2つの部分木 $L$ と $R$（Splitの戻り値）に分離します。これにより、$L$ はキー $X_L \leq X$ を持つすべての要素を含み、$R$ はキー $X_R > X$ を持つすべての要素を含みます。この操作は $O(\log N)$ の複雑性を持ち、クリーンな再帰を使用して実装されます：

  1. ルートノード（R）の値が $X$ 以下の場合、L は少なくとも R->L と R で構成されます。次に R->R に対してsplitを呼び出し、その分割結果を L' と R' として記録します。最後に、L は L' も含み、R = R' となります。
  2. ルートノード（R）の値が $X$ より大きい場合、R は少なくとも R と R->R で構成されます。次に R->L に対してsplitを呼び出し、その分割結果を L' と R' として記録します。最後に、L=L' となり、R は R' も含みます。

したがって、Splitアルゴリズムは次のようになります：

  1. ルートノードが属するべき部分木（左または右）を決定します。
  2. 子に対して再帰的にsplitを呼び出します。
  3. 再帰呼び出しを再利用して最終結果を作成します。
Merge

［画像: Merge操作の概念図］

Merge ($T_1$, $T_2$) は、2つの部分木 $T_1$ と $T_2$ を結合して新しい木を返します。この操作も $O(\log N)$ の複雑性を持ちます。これは、$T_1$ と $T_2$ が順序付けられている（$T_1$ のすべてのキー $X$ が $T_2$ のキーより小さい）という仮定の下で機能します。したがって、優先度 $Y$ の順序を壊さずにこれらの木を結合する必要があります。これを行うには、ルートノードに高い優先度 $Y$ を持つ木をルートとして選択し、もう一方の木と選択されたルートノードの対応する部分木に対して再帰的にMergeを呼び出します。

Insert

［画像: Insert操作の概念図］

Insert ($X$, $Y$) の実装は明白になりました。まず、木を下降します（Xに関する通常の二分探索木のように）、優先度値が $Y$ より小さい最初のノードで停止します。ここに新しい要素を挿入する場所が見つかりました。次に、見つかったノードから始まる部分木に対して Split ($T$, $X$) を呼び出し、返された部分木 $L$ と $R$ を新しいノードの左の子と右の子として使用します。

あるいは、初期TreapをXで分割し、新しいノードとの2回のMergeを行うことで挿入できます（図を参照）。

Erase

［画像: Erase操作の概念図］

Erase ($X$) の実装も明らかです。まず、削除したい要素を検索するために木を下降します（Xに関する通常の二分探索木のように）。ノードが見つかったら、その子の Merge を呼び出し、操作の戻り値を削除する要素の場所に配置します。

あるいは、2回のSplit操作でXを含む部分木を分離し、残りのTreapをマージすることもできます（図を参照）。

Build

$N$ 回の Insert 呼び出しを使用して、$O(N \log N)$ の複雑性で Build 操作を実装します。

実装

struct item {
    int key, prior;
    item *l, *r;
    item() { }
    item(int key) : key(key), prior(rand()), l(NULL), r(NULL) { }
    item(int key, int prior) : key(key), prior(prior), l(NULL), r(NULL) { }
};
typedef item* pitem;

これは私たちのitem定義です。2つの子ポインタ、整数キー（BST用）、および整数優先度（ヒープ用）が含まれていることに注意してください。優先度は乱数ジェネレータを使用して割り当てられます。

void split (pitem t, int key, pitem & l, pitem & r) {
    if (!t)
        l = r = NULL;
    else if (t->key <= key)
        split (t->r, key, t->r, r),  l = t;
    else
        split (t->l, key, l, t->l),  r = t;
}

t は分割するTreapであり、key は分割するBST値です。結果の値はどこにもreturnされておらず、代わりに、出力Treapはlとrを通じて書き込まれます。例えば：

pitem l = nullptr, r = nullptr;
split(t, 5, l, r);

このsplit関数は、ポインタ（pitem）とポインタへの参照（pitem &l）の両方を持つため、理解が難しい場合があります。関数呼び出し split(t, k, l, r) が意図することを言葉で理解しましょう：「Treap t を値 k で2つのTreapに分割し、左のTreapをlに、右のTreapをrに格納する」。素晴らしい！では、前のセクションで分析した場合分けを使用して、2つの再帰呼び出しにこの定義を適用しましょう：（最初のif条件は空のTreapに対する自明なベースケースです）

  1. ルートノードの値が key 以下の場合、split (t->r, key, t->r, r) を呼び出します。これは、「Treap t->r（t の右部分木）を値 key で分割し、左部分木を t->r に、右部分木を r に格納する」という意味です。その後、l = t と設定します。これで、l の結果値が t->l、t、および t->r（これは呼び出した再帰呼び出しの結果です）をすべて正しい順序でマージした状態を含むことがわかります！この l と r の結果が、以前の実装説明で議論した内容と正確に対応していることを確認するために一時停止してください。
  2. ルートノードの値が key より大きい場合、split (t->l, key, l, t->l) を呼び出します。これは、「Treap t->l（t の左部分木）を値 key で分割し、左部分木を l に、右部分木を t->l に格納する」という意味です。その後、r = t と設定します。これで、r の結果値が t->l（これは呼び出した再帰呼び出しの結果です）、t、および t->r をすべて正しい順序でマージした状態を含むことがわかります！この l と r の結果が、以前の実装説明で議論した内容と正確に対応していることを確認するために一時停止してください。

実装の理解にまだ苦労している場合は、帰納的に見るべきです。つまり、再帰呼び出しを何度も分解しようとしないでください。空のTreapに対するsplit実装が正しく機能すると仮定し、次に1ノードのTreap、次に2ノードのTreapなどで実行してみてください。その際、小さいTreapに対するsplitが機能するという知識を毎回再利用します。

void insert (pitem & t, pitem it) {
    if (!t)
        t = it;
    else if (it->prior > t->prior)
        split (t, it->key, it->l, it->r),  t = it;
    else
        insert (t->key <= it->key ? t->r : t->l, it);
}

void merge (pitem & t, pitem l, pitem r) {
    if (!l || !r)
        t = l ? l : r;
    else if (l->prior > r->prior)
        merge (l->r, l->r, r),  t = l;
    else
        merge (r->l, l, r->l),  t = r;
}

void erase (pitem & t, int key) {
    if (t->key == key) {
        pitem th = t;
        merge (t, t->l, t->r);
        delete th;
    }
    else
        erase (key < t->key ? t->l : t->r, key);
}

pitem unite (pitem l, pitem r) {
    if (!l || !r)  return l ? l : r;
    if (l->prior < r->prior)  swap (l, r);
    pitem lt, rt;
    split (r, l->key, lt, rt);
    l->l = unite (l->l, lt);
    l->r = unite (l->r, rt);
    return l;
}

サブツリーサイズの管理

Treapの機能を拡張するために、各ノードのサブツリー内のノード数を格納する必要があることがよくあります。例えば、item構造体のint cntフィールドです。これにより、例えば$O(\log N)$で木から$K$番目に大きい要素を見つける、または同じ複雑性でソート済みリスト内の要素のインデックスを見つけることができます。これらの操作の実装は、通常の二分探索木と同じになります。

木が変更される（ノードが追加または削除されるなど）と、一部のノードのcntを更新する必要があります。cnt()は現在のcntの値を返しますが、ノードが存在しない場合は0を返します。upd_cnt()は、その子のLとRのcntの値がすでに更新されていると仮定して、このノードのcntの値を更新します。明らかに、cnt値を最新の状態に保つために、insert、erase、split、mergeの末尾にupd_cnt()の呼び出しを追加するだけで十分です。

int cnt (pitem t) {
    return t ? t->cnt : 0;
}

void upd_cnt (pitem t) {
    if (t)
        t->cnt = 1 + cnt(t->l) + cnt (t->r);
}

Treapをオフラインモードで $O(N)$ で構築する

ソート済みのキーのリストが与えられた場合、キーを1つずつ挿入する（$O(N \log N)$かかる）よりも速くTreapを構築できます。キーがソートされているため、バランスの取れた二分探索木を線形時間で簡単に構築できます。ヒープ値$Y$はランダムに初期化され、その後キー$X$とは無関係にヒープ化して $O(N)$ でヒープを構築できます。

void heapify (pitem t) {
    if (!t) return;
    pitem max = t;
    if (t->l != NULL && t->l->prior > max->prior)
        max = t->l;
    if (t->r != NULL && t->r->prior > max->prior)
        max = t->r;
    if (max != t) {
        swap (t->prior, max->prior);
        heapify (max);
    }
}

pitem build (int * a, int n) {
    // Values {a[0], a[1], ..., a[n - 1]} on a treap construct
    if (n == 0) return NULL;
    int mid = n / 2;
    pitem t = new item (a[mid], rand ());
    t->l = build (a, mid);
    t->r = build (a + mid + 1, n - mid - 1);
    heapify (t);
    upd_cnt(t);
    return t;
}

注：upd_cnt(t)の呼び出しは、サブツリーサイズが必要な場合にのみ必要です。

上記のアプローチは常に完全にバランスの取れた木を提供しますが、これは実用上は一般的に良好ですが、各ノードに最初に割り当てられた優先度を維持できないというコストがかかります。したがって、このアプローチは次の問題を解決するには現実的ではありません：

acmsguru - Cartesian Tree

ペア $(x_i, y_i)$ のシーケンスが与えられた場合、それらにカルテジアンツリーを構築します。すべての$x_i$とすべての$y_i$は一意です。

この問題では優先度はランダムではないため、頂点を1つずつ挿入するだけでは二次解が得られる可能性があります。

可能な解決策の1つは、各要素について、それより優先度が小さい最も近い左と右の要素を見つけることです。これらの2つの要素のうち、優先度が高い方が現在の要素の親になります。

この問題は、線形時間で最小スタックの変更で解決できます。以下の構築は、通常のTreap実装で使用される最大ヒープ規約とは異なり、優先度に対して最小ヒープ規約を使用し、itemが親ポインタp（nullptrに初期化）で拡張されていると仮定します：

void connect(auto from, auto to) {
    vector<pitem> st;
    for(auto it: ranges::subrange(from, to)) {
        while(!st.empty() && st.back()->prior > it->prior) {
            st.pop_back();
        }
        if(!st.empty()) {
            if(!it->p || it->p->prior < st.back()->prior) {
                it->p = st.back();
            }
        }
        st.push_back(it);
    }
}

pitem build(int *x, int *y, int n) {
    vector<pitem> nodes(n);
    for(int i = 0; i < n; i++) {
        nodes[i] = new item(x[i], y[i]);
    }
    connect(nodes.begin(), nodes.end());
    connect(nodes.rbegin(), nodes.rend());
    for(int i = 0; i < n; i++) {
        if(nodes[i]->p) {
            if(nodes[i]->p->key < nodes[i]->key) {
                nodes[i]->p->r = nodes[i];
            } else {
                nodes[i]->p->l = nodes[i];
            }
        }
    }
    return nodes[min_element(y, y + n) - y];
}

Implicit Treaps

Implicit Treapは、非常に強力なデータ構造である通常のTreapの単純な変更です。実際、Implicit Treapは、以下のプロシージャが実装された配列と見なすことができます（すべてオンラインモードで $O(\log N)$）：

  • 配列の任意の場所に要素を挿入する
  • 任意の要素を削除する
  • 任意の区間での合計、最小/最大要素などを見つける
  • 任意の区間での加算、ペイント
  • 任意の区間での要素の反転

アイデアは、キーが配列内の要素のインデックス（0ベース）であるということです。しかし、これらの値を明示的に格納しません（そうしないと、例えば要素を挿入すると、木 $O(N)$ ノードのキーが変更されることになります）。

ノードのキーは、それより小さいノードの数であることを思い出してください（そのようなノードは左部分木だけでなく、祖先の左部分木にも存在する可能性があります）。より具体的には、あるノードTの暗黙的なキーは、このノードの左部分木内の頂点数 $cnt (T \rightarrow L)$ と、ノードTの各祖先Pについて、TがPの右部分木にある場合の同様の値 $cnt (P \rightarrow L) + 1$ の合計です。

現在のノードの暗黙的なキーを迅速に計算する方法は明らかです。すべての操作で木を下降してノードに到達するため、この合計を累積し、関数に渡すことができます。左部分木に移動する場合、累積合計は変更されません。右部分木に移動する場合は、$cnt (T \rightarrow L) +1$ だけ増加します。

ここに、SplitとMergeの新しい実装があります：

void merge (pitem & t, pitem l, pitem r) {
    if (!l || !r)
        t = l ? l : r;
    else if (l->prior > r->prior)
        merge (l->r, l->r, r),  t = l;
    else
        merge (r->l, l, r->l),  t = r;
    upd_cnt (t);
}

void split (pitem t, pitem & l, pitem & r, int key, int add = 0) {
    if (!t)
        return void( l = r = 0 );
    int cur_key = add + cnt(t->l); //implicit key
    if (key <= cur_key)
        split (t->l, l, t->l, key, add),  r = t;
    else
        split (t->r, t->r, r, key, add + 1 + cnt(t->l)),  l = t;
    upd_cnt (t);
}

上記の С++ 実装では、$split(T, T_1, T_2, k)$ の呼び出し後、木 $T_1$ は $T$ の最初の $k$ 個の要素（つまり、暗黙的なキーが $k$ より小さい要素）で構成され、$T_2$ は残りのすべての要素で構成されます。

次に、Implicit Treapでのさまざまな操作の実装を検討します：

  • 要素の挿入。
    位置 $pos$ に要素を挿入する必要があるとします。木を2つの部分に分割します。これは配列 $[0..pos-1]$ と $[pos..sz]$ に対応します。これを行うには、$split(T, T_1, T_2, pos)$ を呼び出します。次に、新しいノードとのMergeを呼び出すことによって木 $T_1$ を結合できます。$merge(T_1, T_1, \text{new item})$（すべての前提条件が満たされていることは容易にわかります）。最後に、$merge(T, T_1, T_2)$ を呼び出して木 $T_1$ と $T_2$ を $T$ に戻します。
  • 要素の削除。
    この操作はさらに簡単です。削除する要素 $T$ を見つけ、その子のLとRのMergeを実行し、Mergeの結果で要素 $T$ を置き換えます。実際、Implicit Treapでの要素削除は、通常のTreapでの削除とまったく同じです。
  • 区間での合計/最小値などを見つける。
    まず、item構造に追加フィールド$F$を作成して、このノードのサブツリーのターゲット関数の値を格納します。このフィールドは、サブツリーサイズの管理と同様に簡単に維持できます。子ノードの値に基づいてこの値を計算する関数を作成し、木を変更するすべての関数の末尾にこの関数の呼び出しを追加します。
    次に、任意の区間 $[A; B]$ のクエリを処理する方法を知る必要があります。
    区間 $[A; B]$ に対応する木の一部を取得するには、$split(T, T_2, T_3, B+1)$ を呼び出し、次に $split(T_2, T_1, T_2, A)$ を呼び出す必要があります。その後、$T_2$ は区間 $[A; B]$ 内のすべての要素のみで構成されます。したがって、クエリへの応答は $T_2$ のルートのフィールド $F$ に格納されます。クエリが回答された後、 $merge(T, T_1, T_2)$ と $merge(T, T, T_3)$ を呼び出して木を復元する必要があります。
  • 区間での加算/ペイント。
    前の段落と同様に行いますが、フィールドFの代わりに、サブツリーに追加された値（またはサブツリーがペイントされる値）を含むaddフィールドを格納します。操作を実行する前に、この値を正しく「プッシュ」する必要があります。つまり、$T \rightarrow L \rightarrow add$ と $T \rightarrow R \rightarrow add$ を変更し、親ノードのaddをクリアします。これにより、木への変更後も情報は失われません。
  • 区間での反転。
    これは前の操作と同様です。ブールフラグrevを追加し、現在のノードのサブツリーを反転する必要があるたびにそれを切り替える必要があります。「プッシュ」値は少し複雑です。ノードの子をスワップし、それらのフラグを切り替えます。

ここでは、区間での反転を含むImplicit Treapの例実装を示します。各ノードには、現在の位置の配列要素の実際の値であるvalueフィールドが格納されています。また、Implicit Treapの現在の状態に対応する配列を出力するoutput()関数の実装も提供します。

typedef struct item * pitem;
struct item {
    int prior, value, cnt;
    bool rev;
    pitem l, r;
};

int cnt (pitem it) {
    return it ? it->cnt : 0;
}

void upd_cnt (pitem it) {
    if (it)
        it->cnt = cnt(it->l) + cnt(it->r) + 1;
}

void push (pitem it) {
    if (it && it->rev) {
        it->rev = false;
        swap (it->l, it->r);
        if (it->l)  it->l->rev ^= true;
        if (it->r)  it->r->rev ^= true;
    }
}

void merge (pitem & t, pitem l, pitem r) {
    push (l);
    push (r);
    if (!l || !r)
        t = l ? l : r;
    else if (l->prior > r->prior)
        merge (l->r, l->r, r),  t = l;
    else
        merge (r->l, l, r->l),  t = r;
    upd_cnt (t);
}

void split (pitem t, pitem & l, pitem & r, int key, int add = 0) {
    if (!t)
        return void( l = r = 0 );
    push (t);
    int cur_key = add + cnt(t->l);
    if (key <= cur_key)
        split (t->l, l, t->l, key, add),  r = t;
    else
        split (t->r, t->r, r, key, add + 1 + cnt(t->l)),  l = t;
    upd_cnt (t);
}

void reverse (pitem t, int l, int r) {
    pitem t1, t2, t3;
    split (t, t1, t2, l);
    split (t2, t2, t3, r-l+1);
    t2->rev ^= true;
    merge (t, t1, t2);
    merge (t, t, t3);
}

void output (pitem t) {
    if (!t)  return;
    push (t);
    output (t->l);
    printf ("%d ", t->value);
    output (t->r);
}

文献

実践問題

貢献者：