پرش به محتویات

تریپ (Treap) (درخت دکارتی)

تریپ (Treap) یک ساختمان داده است که درخت دودویی (binary tree) و هرم دودویی (binary heap) را با هم ترکیب می‌کند (و نام آن نیز از همین ترکیب گرفته شده است: tree + heap $\Rightarrow$ Treap).

به طور مشخص‌تر، تریپ ساختمان داده‌ای است که زوج‌های $(X, Y)$ را در یک درخت دودویی به گونه‌ای ذخیره می‌کند که نسبت به $X$ یک درخت جستجوی دودویی (binary search tree) و نسبت به $Y$ یک هرم دودویی (binary heap) باشد. اگر گره‌ای از درخت حاوی مقادیر $(X_0, Y_0)$ باشد، تمام گره‌ها در زیردرخت چپ دارای $X \leq X_0$ و تمام گره‌ها در زیردرخت راست دارای $X_0 \leq X$ هستند، و تمام گره‌ها در هر دو زیردرخت چپ و راست دارای $Y \leq Y_0$ هستند.

تریپ اغلب به عنوان «درخت دکارتی» (cartesian tree) نیز شناخته می‌شود، زیرا به راحتی می‌توان آن را در یک صفحه دکارتی ترسیم کرد:

تریپ‌ها توسط Raimund Siedel و Cecilia Aragon در سال ۱۹۸۹ پیشنهاد شدند.

مزایای چنین سازماندهی داده‌ای

در چنین پیاده‌سازی، مقادیر $X$ کلیدها (و در عین حال مقادیر ذخیره شده در تریپ) هستند و مقادیر $Y$ اولویت (priority) نامیده می‌شوند. بدون اولویت‌ها، تریپ یک درخت جستجوی دودویی معمولی بر اساس $X$ خواهد بود و یک مجموعه از مقادیر $X$ می‌توانست به درختان بسیار متفاوتی منجر شود که برخی از آن‌ها تبهگن (degenerate) هستند (مثلاً به شکل یک لیست پیوندی) و در نتیجه بسیار کند عمل می‌کنند (عملیات اصلی پیچیدگی $O(N)$ خواهند داشت).

در عین حال، اولویت‌ها (وقتی یکتا باشند) این امکان را می‌دهند که درختی که ساخته می‌شود به طور منحصر به فرد مشخص شود (البته این موضوع به ترتیب اضافه شدن مقادیر بستگی ندارد)، که با استفاده از قضیه مربوطه قابل اثبات است. بدیهی است که اگر اولویت‌ها را به صورت تصادفی انتخاب کنید، به طور متوسط درختان غیرتبهگن به دست می‌آورید که پیچیدگی $O(\log N)$ را برای عملیات اصلی تضمین می‌کند. از این رو نام دیگر این ساختمان داده درخت جستجوی دودویی تصادفی (randomized binary search tree) است.

عملیات

یک تریپ عملیات زیر را ارائه می‌دهد:

  • Insert (X,Y) با پیچیدگی $O(\log N)$. یک گره جدید به درخت اضافه می‌کند. یک روش ممکن این است که فقط $X$ را به عنوان ورودی بگیریم و $Y$ را به صورت تصادفی داخل تابع تولید کنیم.
  • Search (X) با پیچیدگی $O(\log N)$. به دنبال گره‌ای با مقدار کلید مشخص $X$ می‌گردد. پیاده‌سازی آن همانند یک درخت جستجوی دودویی معمولی است.
  • Erase (X) با پیچیدگی $O(\log N)$. به دنبال گره‌ای با مقدار کلید مشخص $X$ می‌گردد و آن را از درخت حذف می‌کند.
  • Build ($X_1$, ..., $X_N$) با پیچیدگی $O(N)$. یک درخت از لیستی از مقادیر می‌سازد. این کار را می‌توان در زمان خطی انجام داد (با فرض اینکه $X_1, ..., X_N$ مرتب باشند).
  • Union ($T_1$, $T_2$) با پیچیدگی $O(M \log (N/M))$. دو درخت را با هم ادغام می‌کند، با این فرض که تمام عناصر متفاوت هستند. اگر عناصر تکراری باید در حین ادغام حذف شوند، می‌توان به همین پیچیدگی دست یافت.
  • Intersect ($T_1$, $T_2$) با پیچیدگی $O(M \log (N/M))$. اشتراک دو درخت (یعنی عناصر مشترک آنها) را پیدا می‌کند. ما در اینجا پیاده‌سازی این عملیات را بررسی نخواهیم کرد.

علاوه بر این، به دلیل اینکه تریپ یک درخت جستجوی دودویی است، می‌تواند عملیات دیگری مانند یافتن $K$-امین عنصر بزرگتر یا یافتن اندیس یک عنصر را نیز پیاده‌سازی کند.

توضیحات پیاده‌سازی

از نظر پیاده‌سازی، هر گره شامل $X$، $Y$ و اشاره‌گرهایی به فرزندان چپ ($L$) و راست ($R$) است.

ما تمام عملیات مورد نیاز را فقط با استفاده از دو عملیات کمکی پیاده‌سازی خواهیم کرد: Split و Merge.

Split

Split ($T$, $X$) درخت $T$ را به ۲ زیردرخت $L$ و $R$ (که مقادیر بازگشتی تابع split هستند) تقسیم می‌کند، به طوری که $L$ شامل تمام عناصری با کلید $X_L \le X$ و $R$ شامل تمام عناصری با کلید $X_R > X$ است. این عملیات پیچیدگی $O (\log N)$ دارد و با استفاده از یک بازگشت تمیز پیاده‌سازی می‌شود:

  1. اگر مقدار گره ریشه (R) کوچکتر یا مساوی $X$ باشد، آنگاه L حداقل شامل R->L و خود R خواهد بود. سپس ما split را بر روی R->R فراخوانی می‌کنیم و نتیجه تقسیم آن را به عنوان L' و R' در نظر می‌گیریم. در نهایت، L شامل L' نیز خواهد بود، در حالی که R = R' می‌شود.
  2. اگر مقدار گره ریشه (R) بزرگتر از $X$ باشد، آنگاه R حداقل شامل خود R و R->R خواهد بود. سپس ما split را بر روی R->L فراخوانی می‌کنیم و نتیجه تقسیم آن را به عنوان L' و R' در نظر می‌گیریم. در نهایت، L=L' می‌شود، در حالی که R شامل R' نیز خواهد بود.

بنابراین، الگوریتم split به این صورت است:

  1. تصمیم بگیرید که گره ریشه به کدام زیردرخت (چپ یا راست) تعلق دارد.
  2. به صورت بازگشتی split را بر روی یکی از فرزندانش فراخوانی کنید.
  3. با استفاده مجدد از فراخوانی بازگشتی split، نتیجه نهایی را ایجاد کنید.

Merge

Merge ($T_1$, $T_2$) دو زیردرخت $T_1$ و $T_2$ را ترکیب کرده و درخت جدید را برمی‌گرداند. این عملیات نیز پیچیدگی $O (\log N)$ دارد. این تابع با این فرض کار می‌کند که $T_1$ و $T_2$ مرتب هستند (تمام کلیدهای $X$ در $T_1$ کوچکتر از کلیدها در $T_2$ هستند). بنابراین، باید این دو درخت را بدون نقض ترتیب اولویت‌های $Y$ ترکیب کنیم. برای انجام این کار، درختی را به عنوان ریشه انتخاب می‌کنیم که اولویت $Y$ بالاتری در گره ریشه خود دارد و به صورت بازگشتی Merge را برای درخت دیگر و زیردرخت متناظر از گره ریشه انتخاب شده فراخوانی می‌کنیم.

Insert

اکنون پیاده‌سازی Insert ($X$, $Y$) واضح می‌شود. ابتدا در درخت پایین می‌رویم (مانند یک درخت جستجوی دودویی معمولی بر اساس X) و در اولین گره‌ای که مقدار اولویت آن کمتر از $Y$ است، متوقف می‌شویم. ما مکانی را که عنصر جدید را در آن درج خواهیم کرد، پیدا کرده‌ایم. سپس، Split (T, X) را بر روی زیردرختی که از گره یافت شده شروع می‌شود فراخوانی می‌کنیم و از زیردرخت‌های بازگشتی $L$ و $R$ به عنوان فرزندان چپ و راست گره جدید استفاده می‌کنیم.

به طور جایگزین، می‌توان عملیات insert را با تقسیم کردن (split) تریپ اولیه بر اساس $X$ و انجام ۲ عمل ادغام (merge) با گره جدید انجام داد (تصویر را ببینید).

Erase

پیاده‌سازی Erase ($X$) نیز واضح است. ابتدا در درخت پایین می‌رویم (مانند یک درخت جستجوی دودویی معمولی بر اساس $X$) و به دنبال عنصری که می‌خواهیم حذف کنیم، می‌گردیم. هنگامی که گره پیدا شد، Merge را بر روی فرزندان آن فراخوانی می‌کنیم و مقدار بازگشتی این عملیات را در جای عنصری که حذف می‌کنیم، قرار می‌دهیم.

به طور جایگزین، می‌توانیم زیردرخت حاوی $X$ را با ۲ عملیات split جدا کرده و تریپ‌های باقی‌مانده را با هم ادغام کنیم (تصویر را ببینید).

Build

ما عملیات Build را با پیچیدگی $O (N \log N)$ با استفاده از $N$ فراخوانی Insert پیاده‌سازی می‌کنیم.

Union

Union ($T_1$, $T_2$) دارای پیچیدگی نظری $O (M \log (N / M))$ است، اما در عمل بسیار خوب کار می‌کند، احتمالاً با یک ثابت پنهان بسیار کوچک. بدون از دست دادن کلیت، فرض کنیم $T_1 \rightarrow Y > T_2 \rightarrow Y$ باشد، یعنی ریشه $T_1$ ریشه نتیجه خواهد بود. برای به دست آوردن نتیجه، باید درختان $T_1 \rightarrow L$، $T_1 \rightarrow R$ و $T_2$ را در دو درخت ادغام کنیم که می‌توانند فرزندان ریشه $T_1$ باشند. برای این کار، Split ($T_2$, $T_1\rightarrow X$) را فراخوانی می‌کنیم، و بدین ترتیب $T_2$ را به دو بخش L و R تقسیم می‌کنیم، که سپس آنها را به صورت بازگشتی با فرزندان $T_1$ ترکیب می‌کنیم: Union ($T_1 \rightarrow L$, $L$) و Union ($T_1 \rightarrow R$, $R$)، و در نتیجه زیردرخت‌های چپ و راست نتیجه را به دست می‌آوریم.

پیاده‌سازی

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 ما است. توجه داشته باشید که دو اشاره‌گر به فرزندان، یک کلید صحیح (برای 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 تریپی است که باید تقسیم شود و key مقدار BST است که بر اساس آن تقسیم انجام می‌شود. توجه داشته باشید که ما مقادیر نتیجه را در هیچ‌کجا return نمی‌کنیم، بلکه به این صورت از آنها استفاده می‌کنیم:

pitem l = nullptr, r = nullptr;
split(t, 5, l, r);
if (l) cout << "Left subtree size: " << (l->size) << endl;
if (r) cout << "Right subtree size: " << (r->size) << endl;

درک تابع split می‌تواند کمی دشوار باشد، زیرا هم اشاره‌گر (pitem) و هم ارجاع به آن اشاره‌گرها (pitem &l) را دارد. بیایید با کلمات بفهمیم که فراخوانی تابع split(t, k, l, r) چه قصدی دارد: «تریپ t را بر اساس مقدار k به دو تریپ تقسیم کن و تریپ چپ را در l و تریپ راست را در r ذخیره کن». عالی! حال، بیایید این تعریف را برای دو فراخوانی بازگشتی به کار ببریم، با استفاده از تحلیل موردی که در بخش قبل انجام دادیم: (شرط if اول یک حالت پایه پیش پا افتاده برای یک تریپ خالی است)

  1. هنگامی که مقدار گره ریشه $\le$ کلید است، ما split (t->r, key, t->r, r) را فراخوانی می‌کنیم، که به این معنی است: «تریپ t->r (زیردرخت راست t) را بر اساس مقدار key تقسیم کن و زیردرخت چپ را در t->r و زیردرخت راست را در r ذخیره کن». پس از آن، ما l = t را قرار می‌دهیم. توجه داشته باشید که اکنون مقدار نتیجه l شامل t->l، خود t و همچنین t->r (که نتیجه فراخوانی بازگشتی ما است) است که همگی قبلاً به ترتیب صحیح ادغام شده‌اند! باید مکث کنید تا مطمئن شوید که این نتیجه برای l و r دقیقاً با آنچه قبلاً در بخش «توضیحات پیاده‌سازی» بحث کردیم، مطابقت دارد.
  2. هنگامی که مقدار گره ریشه بزرگتر از کلید است، ما split (t->l, key, l, t->l) را فراخوانی می‌کنیم، که به این معنی است: «تریپ t->l (زیردرخت چپ t) را بر اساس مقدار key تقسیم کن و زیردرخت چپ را در l و زیردرخت راست را در t->l ذخیره کن». پس از آن، ما r = t را قرار می‌دهیم. توجه داشته باشید که اکنون مقدار نتیجه r شامل t->l (که نتیجه فراخوانی بازگشتی ما است)، خود t و همچنین t->r است که همگی قبلاً به ترتیب صحیح ادغام شده‌اند! باید مکث کنید تا مطمئن شوید که این نتیجه برای l و r دقیقاً با آنچه قبلاً در بخش «توضیحات پیاده‌سازی» بحث کردیم، مطابقت دارد.

اگر هنوز در درک این پیاده‌سازی مشکل دارید، باید به آن به صورت استقرایی نگاه کنید، یعنی: سعی نکنید فراخوانی‌های بازگشتی را بارها و بارها تجزیه کنید. فرض کنید پیاده‌سازی split برای تریپ خالی به درستی کار می‌کند، سپس سعی کنید آن را برای یک تریپ تک‌گره‌ای، سپس یک تریپ دو گره‌ای و غیره اجرا کنید، و هر بار از دانش خود مبنی بر اینکه 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;
}

نگهداری اندازه زیردرخت‌ها

برای گسترش عملکرد تریپ، اغلب لازم است که تعداد گره‌ها در زیردرخت هر گره را ذخیره کنیم - فیلد int cnt در ساختار item. به عنوان مثال، می‌توان از آن برای یافتن K-امین عنصر بزرگتر درخت با پیچیدگی $O (\log N)$ یا برای یافتن اندیس عنصر در لیست مرتب شده با همان پیچیدگی استفاده کرد. پیاده‌سازی این عملیات مشابه درخت جستجوی دودویی معمولی خواهد بود.

هنگامی که یک درخت تغییر می‌کند (گره‌ها اضافه یا حذف می‌شوند و غیره)، cnt برخی از گره‌ها باید به روز شود. ما دو تابع ایجاد خواهیم کرد: cnt() مقدار فعلی cnt را برمی‌گرداند یا اگر گره وجود نداشته باشد ۰ را برمی‌گرداند، و upd_cnt() مقدار cnt را برای این گره به‌روز می‌کند با این فرض که برای فرزندان L و R آن مقادیر cnt قبلاً به‌روز شده‌اند. واضح است که کافی است فراخوانی‌های upd_cnt() را به انتهای توابع insert، erase، split و merge اضافه کنیم تا مقادیر 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);
}

ساختن تریپ با پیچیدگی $O(N)$ به صورت آفلاین

با داشتن یک لیست مرتب از کلیدها، می‌توان یک تریپ را سریع‌تر از درج یک به یک کلیدها که $O(N \log N)$ زمان می‌برد، ساخت. از آنجایی که کلیدها مرتب هستند، یک درخت جستجوی دودویی متوازن را می‌توان به راحتی در زمان خطی ساخت. مقادیر هرم $Y$ به صورت تصادفی مقداردهی اولیه می‌شوند و سپس می‌توانند مستقل از کلیدهای $X$ برای ساختن هرم در زمان $O(N)$ به حالت هرم (heapify) درآیند.

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) {
    // Construct a treap on values {a[0], a[1], ..., a[n - 1]}
    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$ ها یکتا هستند.

توجه داشته باشید که در این مسئله اولویت‌ها تصادفی نیستند، از این رو صرفاً درج رأس‌ها به صورت یک به یک می‌تواند به یک راه حل با پیچیدگی درجه دو منجر شود.

یکی از راه حل‌های ممکن در اینجا این است که برای هر عنصر، نزدیک‌ترین عناصر در سمت چپ و راست را که اولویت کمتری نسبت به این عنصر دارند، پیدا کنیم. از بین این دو عنصر، آنکه اولویت بزرگتری دارد باید والد عنصر فعلی باشد.

این مسئله با یک تغییر در پشته مینیمم در زمان خطی قابل حل است:

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) یک تغییر ساده از تریپ معمولی است که یک ساختمان داده بسیار قدرتمند محسوب می‌شود. در واقع، تریپ ضمنی را می‌توان به عنوان یک آرایه در نظر گرفت که رویه‌های زیر بر روی آن پیاده‌سازی شده‌اند (همه با پیچیدگی $O (\log N)$ در حالت آنلاین):

  • درج یک عنصر در هر مکانی از آرایه
  • حذف یک عنصر دلخواه
  • یافتن مجموع، عنصر کمینه / بیشینه و غیره در یک بازه دلخواه
  • افزودن، رنگ‌آمیزی در یک بازه دلخواه
  • معکوس کردن عناصر در یک بازه دلخواه

ایده این است که کلیدها باید اندیس‌های صفر-مبنای عناصر در آرایه باشند. اما ما این مقادیر را به طور صریح ذخیره نخواهیم کرد (در غیر این صورت، به عنوان مثال، درج یک عنصر باعث تغییر کلید در $O (N)$ گره از درخت می‌شود).

توجه داشته باشید که کلید یک گره، تعداد گره‌های کمتر از آن است (چنین گره‌هایی می‌توانند نه تنها در زیردرخت چپ آن بلکه در زیردرخت‌های چپ اجداد آن نیز وجود داشته باشند). به طور مشخص‌تر، کلید ضمنی برای یک گره T برابر است با تعداد رأس‌های $cnt (T \rightarrow L)$ در زیردرخت چپ این گره به علاوه مقادیر مشابه $cnt (P \rightarrow L) + 1$ برای هر جد P از گره T، اگر T در زیردرخت راست P باشد.

اکنون مشخص است که چگونه کلید ضمنی گره فعلی را به سرعت محاسبه کنیم. از آنجا که در تمام عملیات با پایین رفتن در درخت به هر گره می‌رسیم، می‌توانیم این مجموع را انباشته کرده و آن را به تابع منتقل کنیم. اگر به زیردرخت چپ برویم، مجموع انباشته شده تغییر نمی‌کند، اگر به زیردرخت راست برویم، به اندازه $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$ شامل $k$ عنصر اول $T$ خواهد بود (یعنی عناصری که کلید ضمنی آنها کمتر از $k$ است) و $T_2$ شامل بقیه عناصر خواهد بود.

حال بیایید پیاده‌سازی عملیات مختلف بر روی تریپ‌های ضمنی را بررسی کنیم:

  • درج عنصر. فرض کنید باید یک عنصر را در موقعیت $pos$ درج کنیم. ما تریپ را به دو بخش تقسیم می‌کنیم که متناظر با آرایه‌های $[0..pos-1]$ و $[pos..sz]$ هستند؛ برای این کار $split(T, T_1, T_2, pos)$ را فراخوانی می‌کنیم. سپس درخت $T_1$ را با گره جدید ادغام می‌کنیم (با فراخوانی $merge(T_1, T_1, \text{new item})$). در نهایت، درخت $T_1$ (که اکنون شامل عنصر جدید است) و $T_2$ را دوباره با هم ادغام می‌کنیم تا تریپ نهایی را بسازیم.
  • حذف عنصر. این عملیات حتی ساده‌تر است: گره‌ای که باید حذف شود ($T$) را پیدا کنید، فرزندان آن ($L$ و $R$) را با هم ادغام کنید، و عنصر $T$ را با نتیجه این ادغام جایگزین کنید. در واقع، حذف عنصر در تریپ ضمنی دقیقاً همانند تریپ معمولی است.
  • یافتن مجموع / کمینه، و غیره در یک بازه. اولاً، یک فیلد اضافی $F$ در ساختار item ایجاد کنید تا مقدار تابع هدف را برای زیردرخت این گره ذخیره کند. نگهداری این فیلد مشابه نگهداری اندازه زیردرخت‌ها آسان است: یک تابع ایجاد کنید که این مقدار را برای یک گره بر اساس مقادیر فرزندانش محاسبه کند و فراخوانی‌های این تابع را به انتهای تمام توابعی که درخت را تغییر می‌دهند اضافه کنید. ثانیاً، باید بدانیم چگونه یک پرس‌وجو برای یک بازه دلخواه $[A; B]$ را پردازش کنیم. برای به دست آوردن بخشی از درخت که متناظر با بازه $[A; B]$ است، باید $split(T, T_2, T_3, B+1)$ و سپس $split(T_2, T_1, T_2, A)$ را فراخوانی کنیم: پس از این، $T_2$ شامل تمام عناصر در بازه $[A; B]$ و فقط آنها خواهد بود. بنابراین، پاسخ به پرس‌وجو در فیلد $F$ ریشه $T_2$ ذخیره می‌شود. پس از پاسخ به پرس‌وجو، درخت باید با ادغام مجدد سه بخش بازیابی شود: ابتدا $T_1$ و $T_2$ را ادغام کرده و سپس نتیجه را با $T_3$ ادغام می‌کنیم.
  • افزودن / رنگ‌آمیزی در یک بازه. ما مشابه پاراگراف قبلی عمل می‌کنیم، اما به جای فیلد F، یک فیلد add ذخیره می‌کنیم که حاوی مقدار اضافه‌شده برای زیردرخت (یا مقداری که زیردرخت با آن رنگ‌آمیزی شده) خواهد بود. قبل از انجام هر عملیاتی باید این مقدار را به درستی "push" کنیم - یعنی $T \rightarrow L \rightarrow add$ و $T \rightarrow R \rightarrow add$ را تغییر دهیم و add را در گره والد پاک کنیم. به این ترتیب پس از هر تغییری در درخت، اطلاعات از بین نخواهد رفت.
  • معکوس کردن در یک بازه. این عملیات نیز مشابه عملیات قبلی است: باید یک پرچم بولین rev اضافه کنیم و زمانی که زیردرخت گره فعلی باید معکوس شود، آن را true کنیم. "Push" کردن این مقدار کمی پیچیده‌تر است - ما فرزندان این گره را با هم تعویض می‌کنیم و این پرچم را برای آنها true می‌کنیم.

در اینجا یک پیاده‌سازی نمونه از تریپ ضمنی با قابلیت معکوس کردن در یک بازه آورده شده است. برای هر گره، فیلدی به نام value ذخیره می‌کنیم که مقدار واقعی عنصر آرایه در موقعیت فعلی است. ما همچنین پیاده‌سازی تابع 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);
}

ادبیات

مسائل تمرینی