Treap আর skip list — এলোমেলোতার সাহায্যে ভারসাম্য

১ · সমস্যা — নিয়মের ভারসাম্য বনাম ভাগ্যের ভারসাম্য

পর্ব ২৭-এ দেখেছেন, সাধারণ binary search tree (BST) খুব সুন্দর, যতক্ষণ key-গুলো এলোমেলো ক্রমে আসে। কিন্তু সাজানো ক্রমে এলে — 1, 2, 3, … — tree একটি লম্বা শিকল হয়ে যায়, উচ্চতা n, আর প্রতিটি খোঁজা O(n). বাস্তবে সাজানো বা প্রায়-সাজানো ডেটা খুবই সাধারণ: তারিখ অনুযায়ী আসা লেনদেন, ক্রমিক রোল নম্বর, বাড়তে থাকা অর্ডার আইডি।

এর একটি সমাধান পর্ব ২৮ আর ২৯-এ দেখেছেন: AVL tree আর red-black tree. এরা কড়া নিয়ম রাখে — “দুই পাশের উচ্চতার পার্থক্য ১-এর বেশি নয়”, বা “প্রতি পথে সমান সংখ্যক কালো node” — আর প্রতিটি insert ও delete-এর পর নিয়ম ভাঙলে rotation আর রং বদলে মেরামত করে। ফল চমৎকার: worst case-এও O(log n). কিন্তু দাম আছে: red-black tree-র delete-এ অনেকগুলো আলাদা ক্ষেত্র, কনটেস্টের চাপে নির্ভুল লেখা কঠিন।

এই পর্বের প্রশ্ন: নিয়ম না মেনে কি ভারসাম্য পাওয়া যায়? উত্তর আসে একটি পুরোনো পর্যবেক্ষণ থেকে। Key-গুলো এলোমেলো ক্রমে ঢোকালে সাধারণ BST নিজে থেকেই প্রায় ভারসাম্যপূর্ণ হয় — প্রত্যাশিত গভীরতা O(log n). সমস্যা হলো, ইনপুটের ক্রম আমাদের হাতে নেই। কিন্তু যদি আমরা নিজেরাই প্রতিটি key-কে একটি এলোমেলো “লটারির টিকিট” দিই, আর tree-কে এমনভাবে সাজাই যেন key-গুলো টিকিটের ক্রমে এসেছিল? তখন ইনপুটের ক্রম যা-ই হোক, tree-র আকৃতি ঠিক হবে আমাদের লটারিতে। এটিই treap-এর মূল ভাবনা।

এখানে একটি সূক্ষ্ম কিন্তু গুরুত্বপূর্ণ পার্থক্য আছে, যা পর্ব ৫ আর ২২-এ (randomized quicksort) দেখেছেন। Average case বিশ্লেষণে আমরা ইনপুট সম্পর্কে অনুমান করি (“ইনপুট এলোমেলো”). Randomized অ্যালগরিদমে ইনপুট সম্পর্কে কোনো অনুমান নেই; এলোমেলোতা আসে অ্যালগরিদমের ভেতর থেকে। তখন যে সীমা পাই, তার নাম expected running time: প্রতিটি ইনপুটের জন্য, আমাদের এলোমেলো পছন্দগুলোর ওপর গড়।

আরও একটি কথা: treap আর skip list সবসময় সঠিক উত্তর দেয়। এলোমেলোতা শুধু গতিকে প্রভাবিত করে, ফলকে নয়। এই ধরনের অ্যালগরিদমকে বলে Las Vegas অ্যালগরিদম (পর্ব ৬১-এ বিস্তারিত)। এই পর্বে দুটি কাঠামো দেখব: treap, যা BST-কে এলোমেলো করে, আর skip list, যা linked list-কে এলোমেলোভাবে কয়েক তলা উঁচু করে।

২ · Treap — key-তে BST, priority-তে heap

Treap শব্দটি tree আর heap জুড়ে বানানো। প্রতিটি node-এ দুটি সংখ্যা: একটি key (যা দিয়ে খুঁজব) আর একটি priority (node তৈরির সময় এলোমেলোভাবে বেছে নেওয়া)। Tree-টিকে একসাথে দুটি নিয়ম মানতে হয়:

• Key-র দিক থেকে BST: প্রতিটি node-এর বাঁ subtree-র সব key ছোট, ডান subtree-র সব key বড় — পর্ব ২৭-এর BST property. তাই inorder traversal সবসময় সাজানো ক্রম দেয়।
• Priority-র দিক থেকে heap: প্রতিটি node-এর priority তার সন্তানদের চেয়ে বড় — পর্ব ২৩-এর max-heap-এর heap property. তাই root-এ থাকে সবচেয়ে বড় priority-র key.

দুটি নিয়ম একসাথে মানা সম্ভব কি? হ্যাঁ, আর আকৃতিটি অনন্য: key আর priority সব আলাদা হলে এমন tree ঠিক একটিই আছে। কারণ: সবচেয়ে বড় priority-র key-কে root হতেই হবে (heap নিয়ম); তার চেয়ে ছোট key-গুলো বাঁ subtree-তে, বড়গুলো ডানে (BST নিয়ম); এখন দুই পাশে একই যুক্তি induction-এ খাটে। এই কাঠামো ১৯৮০ সালে Jean Vuillemin Cartesian tree নামে বর্ণনা করেন; Seidel আর Aragon-এর অবদান হলো priority-গুলো এলোমেলো বেছে নেওয়া, আর তা থেকে ভারসাম্যের প্রমাণ।

Insert — leaf-এ বসান, তারপর rotation দিয়ে ওপরে তুলুন

নতুন key x ঢোকাতে: (১) একটি এলোমেলো priority বেছে নিন; (২) সাধারণ BST-র মতো x-কে সঠিক leaf-এর জায়গায় বসান — BST নিয়ম ঠিক থাকে; (৩) এখন heap নিয়ম ভাঙতে পারে, যদি x-এর priority তার parent-এর চেয়ে বেশি হয়। তাহলে x আর parent-এর মধ্যে একটি rotation করুন: x বাঁ সন্তান হলে right rotation, ডান সন্তান হলে left rotation. Rotation BST নিয়ম ভাঙে না (পর্ব ২৮), আর x এক ধাপ ওপরে ওঠে। যতক্ষণ x-এর priority parent-এর চেয়ে বেশি, ততক্ষণ চালিয়ে যান — ঠিক heap-এর sift-up-এর মতো, শুধু অদলবদলের বদলে rotation.

নিচের ডায়াগ্রামে পাঁচটি key ঢোকানো হচ্ছে, প্রতিটির priority বন্ধনীতে দেওয়া (বোঝার সুবিধার জন্য হাতে বাছা; আসল treap-এ এগুলো এলোমেলো)। লেখা 50(40) মানে key 50, priority 40.

Delete — উল্টো পথে: rotation দিয়ে নিচে নামান, তারপর কেটে ফেলুন

Key x মুছতে প্রথমে x-কে খুঁজুন। x leaf হলে সরাসরি কেটে ফেলুন। না হলে x-কে নিচে নামান: x-এর দুই সন্তানের মধ্যে যার priority বেশি, তাকে rotation দিয়ে x-এর জায়গায় তুলুন (বাঁ সন্তান উঠলে right rotation, ডান সন্তান উঠলে left rotation). বেশি priority-র সন্তানকে তোলাই নিয়ম, কারণ সে-ই নতুন parent হিসেবে অন্য সন্তানের চেয়ে বড় — heap নিয়ম রক্ষা পায়। x যতক্ষণ leaf না হয়, চালিয়ে যান; তারপর কেটে ফেলুন। একটি বিকল্প চিন্তা: x-এর priority −∞ করে দিন, তাহলে heap নিয়ম তাকে নিচে ঠেলে দেবে। Seidel আর Aragon দেখান, insert বা delete প্রতিটিতে প্রত্যাশিত rotation-এর সংখ্যা ২-এর কম — ধ্রুবক, n-এর ওপর নির্ভর করে না।

Pseudocode — treap insert and delete with rotations (max-heap on priority)

insert(t, x):
    if t == NIL: return new node(x, random priority)
    if x < t.key:  t.left  = insert(t.left, x);  if t.left.pri  > t.pri: t = rotateRight(t)
    else:          t.right = insert(t.right, x); if t.right.pri > t.pri: t = rotateLeft(t)
    return t

delete(t, x):
    if t == NIL: return NIL
    if x < t.key: t.left = delete(t.left, x)
    elif x > t.key: t.right = delete(t.right, x)
    elif t is a leaf: return NIL
    elif t.right == NIL or (t.left != NIL and t.left.pri > t.right.pri):
        t = rotateRight(t);  t.right = delete(t.right, x)    // x moved down to the right
    else:
        t = rotateLeft(t);   t.left  = delete(t.left, x)     // x moved down to the left
    return t

৩ · কেন প্রত্যাশিত গভীরতা O(log n) — treap আসলে একটি random BST

প্রথম মূল পর্যবেক্ষণ: একটি treap ঠিক সেই BST, যা key-গুলোকে priority-র ক্রমে (বড় থেকে ছোট) সাধারণ BST-তে ঢুকিয়ে পাওয়া যায়। কারণ সেই BST-তেও প্রথমে ঢোকা (সবচেয়ে বড় priority-র) key root হয়, তারপর প্রতিটি key তার আগে ঢোকা — মানে বড় priority-র — key-গুলোর নিচে বসে। দুটি tree-ই অনন্যভাবে নির্ধারিত, তাই হুবহু এক।

এখন priority-গুলো স্বাধীনভাবে এলোমেলো, তাই তাদের ক্রম n! টি ক্রমের যেকোনোটি সমান সম্ভাবনায়। অর্থাৎ treap-টি একটি random BST — key-গুলো যেন একটি সম্পূর্ণ এলোমেলো ক্রমে এসেছিল। আসল ইনপুটের ক্রম (সাজানো, উল্টো, যা-ই হোক) আকৃতিতে কোনো প্রভাব ফেলে না। এটি randomized quicksort-এর সাথে হুবহু মেলে (পর্ব ২২): root হলো প্রথম pivot, যে key-গুলোকে দুই ভাগে ভাগ করে; প্রতিটি subtree-র root সেই ভাগের pivot.

প্রমাণ — কে কার পূর্বপুরুষ?

Key-গুলোকে সাজানো ক্রমে নাম দিন: x₁ < x₂ < … < x_n. x_k-এর গভীরতা = তার ancestor-এর (পূর্বপুরুষ) সংখ্যা। তাই প্রশ্ন: x_i কখন x_k-এর ancestor?

লেমা: i ≠ k হলে, x_i হলো x_k-এর ancestor যদি এবং কেবল যদি x_i আর x_k-এর মাঝের (দুই প্রান্তসহ) সব key-র মধ্যে x_i-এর priority সবচেয়ে বড়।

যুক্তি: Key-গুলো priority-র ক্রমে ঢোকানোর কল্পনা করুন, আর রেঞ্জ R = {x_i, …, x_k} দেখুন (ধরুন i < k). R-এর কোনো key ঢোকার আগে যত key ঢুকেছে, সবাই R-এর বাইরে — হয় R-এর সবার চেয়ে ছোট, নয় সবার চেয়ে বড়। তাই BST-তে নামার সময় এরা R-এর সব key-কে একই দিকে পাঠায়: R-এর সবাই একই ফাঁকা জায়গার দিকে যাচ্ছে। এখন R থেকে প্রথম যে key ঢোকে (R-এ সবচেয়ে বড় priority-র), সে সেই জায়গায় বসে, আর R-এর বাকি সবাই তার নিচে যাবে। তিনটি ক্ষেত্র: (ক) সে x_i নিজে — তাহলে x_k তার নিচে, x_i ancestor; (খ) সে x_k — তাহলে উল্টো, x_i ancestor নয়; (গ) সে মাঝের কোনো x_j — তাহলে x_i যায় তার বাঁয়ে আর x_k ডানে, আলাদা subtree-তে; কেউ কারও ancestor নয়। ∎

R-এ |k − i| + 1 টি key, আর priority এলোমেলো, তাই প্রত্যেকের সর্বোচ্চ হওয়ার সম্ভাবনা সমান। ফলে

এখন linearity of expectation: x_k-এর ancestor-এর প্রত্যাশিত সংখ্যা = প্রতিটি i-এর জন্য ওপরের সম্ভাবনার যোগফল। বাঁ পাশের key-গুলো থেকে 1/2 + 1/3 + … + 1/k = H_k − 1, আর ডান পাশ থেকে H_n−k+1 − 1, যেখানে H_m = 1 + 1/2 + … + 1/m হলো harmonic সংখ্যা (পর্ব ৬), প্রায় ln m. তাই

সুতরাং প্রতিটি খোঁজা, insert আর delete প্রত্যাশিত O(log n). পুরো tree-র উচ্চতাও প্রত্যাশিতভাবে O(log n) — random BST-র উচ্চতা নিয়ে Luc Devroye ১৯৮৬ সালে দেখান যে এটি প্রায় 4.311 ln n-এর কাছে থাকে, আর with high probability c log n-এর বেশি হয় না। জায়গা Θ(n): প্রতিটি node-এ শুধু একটি বাড়তি priority.

৪ · Split আর merge — দুই কাজেই সব কাজ

Rotation দিয়ে treap লেখা যায়, কিন্তু কনটেস্টে আর বাস্তবে আরও জনপ্রিয় একটি পদ্ধতি আছে, যেখানে rotation-এর নামই নেই। সব কিছু দাঁড়িয়ে দুটি কাজের ওপর:

• split(t, k): treap t-কে দুটি treap-এ ভাগ করে — L-এ k-এর চেয়ে ছোট সব key, R-এ বাকিগুলো (k বা তার বড়)।
• merge(L, R): দুটি treap জোড়া দেয়, যখন L-এর সব key R-এর সব key-র চেয়ে ছোট।

Split কীভাবে: root-এর key k-এর চেয়ে ছোট হলে root আর তার পুরো বাঁ subtree নিশ্চিতভাবে L-এর অংশ; শুধু ডান subtree-তে মিশ্রণ আছে, তাই সেটিকে recursion-এ split করুন, আর ফলের ছোট অংশটিকে root-এর নতুন ডান সন্তান বানান। Root-এর key k বা বড় হলে উল্টোটা। প্রতিটি ধাপে এক স্তর নামি, তাই খরচ O(গভীরতা) = প্রত্যাশিত O(log n). Heap নিয়ম ভাঙে না, কারণ কোনো node-এর নতুন সন্তান সবসময় তার পুরোনো subtree থেকেই আসে।

Merge কীভাবে: L আর R-এর root-এর মধ্যে যার priority বেশি, সে-ই নতুন root. L-এর root জিতলে তার ডান সন্তান = merge(L-এর ডান subtree, R); R-এর root জিতলে তার বাঁ সন্তান = merge(L, R-এর বাঁ subtree). BST নিয়ম ঠিক থাকে, কারণ L-এর সবাই R-এর সবার চেয়ে ছোট। খরচ O(L-এর ডান পাশের দৈর্ঘ্য + R-এর বাঁ পাশের দৈর্ঘ্য) = প্রত্যাশিত O(log n).

এর পর বাকি সব এক লাইনের:

Pseudocode — everything from split and merge

insert(t, x):  (L, R) = split(t, x)
               return merge(merge(L, newNode(x)), R)
erase(t, x):   (L, R) = split(t, x)          // L: keys < x
               (M, R) = split(R, x + 1)      // M: exactly the key x (integer keys)
               return merge(L, R)
range(t, a, b): split twice to cut out the keys in [a, b) as one treap

আগের ডায়াগ্রামের শেষ treap নিয়ে split(t, 55) চালাই, তারপর key 55 (priority 60) ঢোকাই দুটি merge দিয়ে:

৫ · Subtree-র আকার আর implicit treap — অবস্থান দিয়ে sequence

Order statistics — k-তম ছোট key

প্রতিটি node-এ তার subtree-র node-সংখ্যা sz রাখুন — পর্ব ২৭-এর order-statistic tree-এর মতো একটি augmented data structure. প্রতিটি split আর merge-এ যার সন্তান বদলায়, শুধু তার sz = 1 + sz(বাঁ) + sz(ডান) আবার হিসাব করলেই চলে (কোডে pull). তখন k-তম ছোট key খুঁজতে: root-এর বাঁ subtree-তে s টি key থাকলে root নিজে (s + 1)-তম। k ≤ s হলে বাঁয়ে যান; k = s + 1 হলে root-ই উত্তর; নইলে ডানে যান k − s − 1 খুঁজতে। একইভাবে “x-এর চেয়ে ছোট কয়টি key” (rank) বের করা যায়। দুটোই প্রত্যাশিত O(log n).

Implicit treap — key ছাড়াই, শুধু অবস্থান

এবার একটি চমৎকার মোড়। ধরুন key বলে কিছু নেই, আছে শুধু একটি sequence — যেমন একটি লম্বা লেখার অক্ষরগুলো, বা খাতায় সাজানো নম্বরের সারি। প্রতিটি উপাদানের “key” হবে তার অবস্থান (index). কিন্তু অবস্থান সংরক্ষণ করব না, কারণ মাঝে একটি উপাদান ঢোকালে পরের সবার অবস্থান বদলায়। বদলে অবস্থান হিসাব করব sz থেকে: কোনো node-এর অবস্থান = তার বাঁয়ে কয়টি node আছে। এটিই implicit treap.

Split এখন key দিয়ে নয়, সংখ্যা দিয়ে: split(t, k) প্রথম k টি উপাদান L-এ দেয়, বাকিগুলো R-এ। Root-এর বাঁয়ে s টি থাকলে: s < k হলে root L-এ যায় আর ডানে খুঁজি k − s − 1 টি; নইলে root R-এ যায় আর বাঁয়ে খুঁজি k টি। Merge হুবহু আগের মতো। এখন:

• অবস্থান p-তে ঢোকানো: split(t, p) → (L, R); merge(merge(L, নতুন node), R).
• অবস্থান p মোছা: split(t, p) → (L, R); split(R, 1) → (M, R); merge(L, R).
• [l, r] অংশ উল্টানো: দুবার split করে মাঝের অংশ M আলাদা করুন, M-এর root-এ একটি “উল্টাও” চিহ্ন বসান, তারপর জোড়া দিন। চিহ্নটি তখনই নিচে নামে, যখন কেউ ওই node-এর ভেতরে ঢোকে — এটিই lazy propagation (পর্ব ৩৫): চিহ্ন নামানোর সময় দুই সন্তান অদলবদল হয়, আর চিহ্ন দুই সন্তানে চলে যায়।
• রেঞ্জের যোগফল বা সর্বনিম্ন: sz-এর মতো sum রাখুন, অংশটি কেটে root-এর sum পড়ুন।

প্রতিটি কাজ প্রত্যাশিত O(log n). Segment tree (পর্ব ৩৪) রেঞ্জের প্রশ্নে দ্রুত, কিন্তু মাঝে ঢোকানো, মোছা বা উল্টানো পারে না; implicit treap সব পারে। লম্বা লেখা সম্পাদনার জন্য এমন কাঠামোকে বলে rope. কনটেস্টে “একটি অ্যারের [l, r] অংশ উল্টাও, তারপর জিজ্ঞেস করো i-তম উপাদান কী” — এটি implicit treap-এর ক্লাসিক সমস্যা।

// implicit treap: no key stored; position = number of nodes to the left
struct T { char val; uint32_t pri; int sz = 1; bool rev = false; T *l = nullptr, *r = nullptr; };
int sz(T* t) { return t ? t->sz : 0; }
void push(T* t) {                                  // apply a pending "reverse" one level down
    if (t && t->rev) {
        swap(t->l, t->r);
        if (t->l) t->l->rev ^= 1;
        if (t->r) t->r->rev ^= 1;
        t->rev = false;
    }
}
void split(T* t, int k, T*& a, T*& b) {             // a = first k elements, b = the rest
    if (!t) { a = b = nullptr; return; }
    push(t);
    if (sz(t->l) < k) { split(t->r, k - sz(t->l) - 1, t->r, b); a = t; }
    else              { split(t->l, k, a, t->l); b = t; }
    t->sz = 1 + sz(t->l) + sz(t->r);
}
// merge(a, b) is the same as in the keyed treap, with push(a) / push(b) first
void reverseRange(T*& t, int l, int r) {            // reverse positions l..r (0-based, inclusive)
    T *a, *b, *m, *c;
    split(t, l, a, b); split(b, r - l + 1, m, c);
    m->rev ^= 1;                                    // O(1): the work is done lazily later
    t = merge(a, merge(m, c));
}

যেমন, sequence a b c d e f-এ reverseRange(1, 3) দিলে: split(t, 1) → a আর b c d e f; তারপর split(…, 3) → b c d আর e f; মাঝের অংশে চিহ্ন; জোড়া দিলে inorder a d c b e f.

পুরো কোড — fixed seed-এর treap, split/merge দিয়ে

নিচের প্রোগ্রাম আটটি key ঢোকায়, একটি মোছে, তারপর inorder, আকার, উচ্চতা আর তৃতীয় ছোট key দেখায়। এরপর আসল পরীক্ষা: 1 থেকে 10000 সাজানো ক্রমে ঢোকানো — সাধারণ BST-র সবচেয়ে খারাপ ইনপুট — তারপর 3-এর সব গুণিতক মোছা, আর ফলটি একটি সাজানো রেফারেন্স তালিকার সাথে মেলানো। Priority আসে xorshift32 নামের একটি ছোট pseudorandom জেনারেটর থেকে, একটি নির্দিষ্ট seed (1491) দিয়ে। C++ আর Python-এ একই সূত্র, তাই দুই ভাষায় হুবহু একই priority, একই tree আর একই আউটপুট।

#include <algorithm>
#include <cstdint>
#include <initializer_list>
#include <iostream>
#include <vector>
using namespace std;
uint32_t state = 1491;                                    // fixed seed: same priorities on every run
uint32_t rnd() { state ^= state << 13; state ^= state >> 17; state ^= state << 5; return state; }  // xorshift32
struct Node { int key; uint32_t pri; int sz = 1; Node *l = nullptr, *r = nullptr; };
int sz(Node* t) { return t ? t->sz : 0; }
Node* pull(Node* t) { t->sz = 1 + sz(t->l) + sz(t->r); return t; }
void split(Node* t, int k, Node*& a, Node*& b) {          // a: keys < k, b: keys >= k
    if (!t) { a = b = nullptr; return; }
    if (t->key < k) { split(t->r, k, t->r, b); a = pull(t); }
    else            { split(t->l, k, a, t->l); b = pull(t); }
}
Node* merge(Node* a, Node* b) {                           // every key of a < every key of b
    if (!a || !b) return a ? a : b;
    if (a->pri > b->pri) { a->r = merge(a->r, b); return pull(a); }
    b->l = merge(a, b->l); return pull(b);
}
Node* insert(Node* t, int k) { Node *a, *b; split(t, k, a, b); return merge(merge(a, new Node{k, rnd()}), b); }
Node* erase(Node* t, int k) { Node *a, *b, *m, *c; split(t, k, a, b); split(b, k + 1, m, c); delete m; return merge(a, c); }
int kth(Node* t, int k) {                                 // 1-based k-th smallest, using subtree sizes
    while (sz(t->l) + 1 != k) if (k <= sz(t->l)) t = t->l; else { k -= sz(t->l) + 1; t = t->r; }
    return t->key;
}
int height(Node* t) { return t ? 1 + max(height(t->l), height(t->r)) : 0; }
void inorder(Node* t, vector<int>& out) { if (t) { inorder(t->l, out); out.push_back(t->key); inorder(t->r, out); } }
int main() {
    Node* t = nullptr;
    for (int k : {50, 30, 70, 20, 40, 60, 80, 10}) t = insert(t, k);
    t = erase(t, 30);
    vector<int> v; inorder(t, v); cout << "inorder:"; for (int x : v) cout << ' ' << x;
    cout << "\nsize " << sz(t) << ", height " << height(t) << ", 3rd smallest " << kth(t, 3) << '\n';
    const int N = 10000; Node* s = nullptr; vector<int> ref, w;   // sorted input: a plain BST would be a chain
    for (int k = 1; k <= N; ++k) { s = insert(s, k); if (k % 3) ref.push_back(k); }
    for (int k = 3; k <= N; k += 3) s = erase(s, k);
    bool kok = true; for (size_t i = 0; i < ref.size(); i += 97) kok = kok && kth(s, int(i) + 1) == ref[i];
    inorder(s, w);
    cout << "n = " << sz(s) << ", height " << height(s) << " (plain BST: " << N << ")\n";
    cout << "matches sorted reference: " << (w == ref ? "yes" : "no") << " | kth ok: " << (kok ? "yes" : "no") << '\n';
}

inorder: 10 20 40 50 60 70 80
size 7, height 4, 3rd smallest 40
n = 6667, height 29 (plain BST: 10000)
matches sorted reference: yes | kth ok: yes

class Node:
    __slots__ = ("key", "pri", "sz", "l", "r")
    def __init__(self, key, pri): self.key, self.pri, self.sz, self.l, self.r = key, pri, 1, None, None
state = 1491                               # fixed seed: same priorities on every run
def rnd():                                 # xorshift32, bit-for-bit the same as the C++ version
    global state
    state ^= (state << 13) & 0xFFFFFFFF; state ^= state >> 17; state ^= (state << 5) & 0xFFFFFFFF
    return state
def sz(t): return t.sz if t else 0
def pull(t): t.sz = 1 + sz(t.l) + sz(t.r); return t
def split(t, k):                           # returns (keys < k, keys >= k)
    if t is None: return None, None
    if t.key < k:
        t.r, b = split(t.r, k); return pull(t), b
    a, t.l = split(t.l, k); return a, pull(t)
def merge(a, b):                           # every key of a < every key of b
    if a is None or b is None: return a or b
    if a.pri > b.pri:
        a.r = merge(a.r, b); return pull(a)
    b.l = merge(a, b.l); return pull(b)
def insert(t, k): a, b = split(t, k); return merge(merge(a, Node(k, rnd())), b)
def erase(t, k): a, b = split(t, k); _, c = split(b, k + 1); return merge(a, c)
def kth(t, k):                             # 1-based k-th smallest, using subtree sizes
    while sz(t.l) + 1 != k:
        if k <= sz(t.l): t = t.l
        else: k, t = k - sz(t.l) - 1, t.r
    return t.key
def height(t): return 1 + max(height(t.l), height(t.r)) if t else 0
def inorder(t, out):
    if t: inorder(t.l, out); out.append(t.key); inorder(t.r, out)
    return out
t = None
for k in (50, 30, 70, 20, 40, 60, 80, 10): t = insert(t, k)
t = erase(t, 30)
print("inorder:", *inorder(t, []))
print(f"size {sz(t)}, height {height(t)}, 3rd smallest {kth(t, 3)}")
N, s = 10000, None                         # sorted input: a plain BST would become a chain
for k in range(1, N + 1): s = insert(s, k)
for k in range(3, N + 1, 3): s = erase(s, k)
ref = [k for k in range(1, N + 1) if k % 3]
kok = all(kth(s, i + 1) == ref[i] for i in range(0, len(ref), 97))
print(f"n = {sz(s)}, height {height(s)} (plain BST: {N})")
print("matches sorted reference:", "yes" if inorder(s, []) == ref else "no", "| kth ok:", "yes" if kok else "no")

inorder: 10 20 40 50 60 70 80
size 7, height 4, 3rd smallest 40
n = 6667, height 29 (plain BST: 10000)
matches sorted reference: yes | kth ok: yes

৬ · Skip list — কয়েক তলার linked list আর মুদ্রা নিক্ষেপ

সাজানো linked list-এ খোঁজা O(n), কারণ binary search চলে না — মাঝখানে লাফ দেওয়ার উপায় নেই। William Pugh-এর প্রশ্ন ছিল: যদি কিছু node-এর একটি বাড়তি pointer থাকে, যা অনেক দূরে লাফ দেয়?

যদি ঠিক প্রতি দ্বিতীয় node level 1-এ, প্রতি চতুর্থ node level 2-এ, এভাবে থাকে, তাহলে এটি binary search-এর মতো log₂ n তলা আর O(log n) খোঁজা দেয়। কিন্তু insert আর delete-এ সেই নিখুঁত বিন্যাস রাখতে পুরো কাঠামো বদলাতে হতো। Pugh-এর চতুর সমাধান: নিখুঁত বিন্যাস নয়, শুধু সঠিক অনুপাত. নতুন key ঢোকানোর সময় একটি মুদ্রা ছুড়ুন: heads হলে এক তলা উঁচু করুন, আবার ছুড়ুন; tails হলেই থামুন। তাহলে প্রায় অর্ধেক key level 1-এ, প্রায় এক-চতুর্থাংশ level 2-এ — গড়ে ঠিক সেই অনুপাত, কোনো পুনর্গঠন ছাড়াই। একটি key-র তলার সংখ্যা একটি geometric distribution মানে।

খোঁজার নিয়ম: সবচেয়ে ওপরের তলায় head (H) থেকে শুরু করুন। সামনের node-এর key খোঁজা key-র চেয়ে ছোট হলে সামনে এগোন; না হলে এক তলা নামুন। Level 0-তে থামার পর ঠিক পরের node-টিই হয় খোঁজা key, নয়তো key-টি নেই। নিচের ডায়াগ্রামে দশটি key, আর মুদ্রার ফল ঠিক এই পর্বের প্রোগ্রামের seed থেকে আসা (H = heads, T = tails):

Insert: খোঁজার মতো নামুন, আর প্রতি তলায় যে node-এ থামলেন (update[i]) তা মনে রাখুন। মুদ্রা ছুড়ে তলার সংখ্যা lv ঠিক করুন। তারপর প্রতিটি তলা i < lv-তে নতুন node-কে update[i]-এর পরে জুড়ুন — linked list-এর সাধারণ insert, প্রতি তলায় দুটি pointer. Delete: একইভাবে update[i] জমা করুন, আর key-টি যে যে তলায় আছে, সেখানে update[i].next[i]-কে তার পরেরটিতে সরিয়ে দিন। কোনো rotation নেই, কোনো রং নেই; শুধু স্থানীয় pointer বদল।

বিশ্লেষণ — কেন প্রত্যাশিত O(log n) সময় আর O(n) জায়গা

জায়গা. প্রতিটি key কমপক্ষে level 0-তে; level i-তেও থাকার সম্ভাবনা (1/2)ⁱ. তাই একটি key-র প্রত্যাশিত pointer-সংখ্যা 1 + 1/2 + 1/4 + … = 2 — একটি geometric series (পর্ব ৬)। n টি key-তে প্রত্যাশিত 2n pointer: জায়গা প্রত্যাশিত O(n). সাধারণভাবে, পরের তলায় ওঠার সম্ভাবনা p হলে প্রতি key-তে 1/(1 − p) pointer; Pugh নিজে অনেক ক্ষেত্রে p = 1/4 সুপারিশ করেন — প্রায় ১.৩৩ pointer, খোঁজা সামান্য ধীর।

উচ্চতা. একটি নির্দিষ্ট key-র তলা h-এর বেশি হওয়ার সম্ভাবনা (1/2)^h. Union bound-এ, n টির যেকোনো একটির তলা h-এর বেশি হওয়ার সম্ভাবনা ≤ n/2^h. h = 2 log₂ n বসালে এটি ≤ 1/n. তাই with high probability উচ্চতা ≤ 2 log₂ n, আর প্রত্যাশিত উচ্চতা ≤ log₂ n + 2. (বাস্তবে একটি সর্বোচ্চ তলা MAXL বেঁধে দেওয়া হয়, যেমন ১৬ বা ৩২.)

খোঁজার পথ — উল্টো দিক থেকে দেখুন. এই যুক্তির নাম backward analysis. খোঁজা শেষ হয় level 0-র একটি node-এ। সেখান থেকে পথটি উল্টো দিকে হাঁটুন: প্রতিটি node-এ, যদি সেই node-এর আরও ওপরের তলা থাকে, পথটি সেখানে ওপর থেকে নেমেছিল — উল্টো দিকে আমরা ওপরে উঠি; না থাকলে পথটি বাঁ দিক থেকে এসেছিল — উল্টো দিকে আমরা বাঁয়ে যাই। প্রতিটি node-এর ওপরের তলা আছে কি না, তা একটি স্বাধীন মুদ্রা, সম্ভাবনা 1/2. তাই প্রতিটি এক তলা ওঠার আগে গড়ে ২টি ধাপ। প্রায় log₂ n তলা উঠতে প্রত্যাশিত প্রায় 2 log₂ n ধাপ, আর ওপরের কয়েকটি তলায় মাত্র কয়েকটি key থাকে বলে বাকি অংশ O(1). সুতরাং search প্রত্যাশিত O(log n); insert আর delete তার সাথে প্রতি তলায় O(1) কাজ যোগ করে — একই O(log n).

Pseudocode — skip list (levels 0 .. MAXL-1, head H on every level)

search(k):  x = H
            for i = top down to 0:
                while x.next[i] != NIL and x.next[i].key < k:  x = x.next[i]
                update[i] = x                          // last node before k on level i
            y = x.next[0];  return y != NIL and y.key == k
insert(k):  search(k); if found: return
            lv = 1;  while lv < MAXL and coin() == heads:  lv = lv + 1
            for i = 0 to lv-1:  new.next[i] = update[i].next[i];  update[i].next[i] = new
delete(k):  search(k); if not found: return
            for i = 0 to (levels of y) - 1:  update[i].next[i] = y.next[i]

পুরো কোড — fixed seed-এর skip list, তলা আর খোঁজার পথসহ

প্রোগ্রামটি ডায়াগ্রামের দশটি key একই ক্রমে ঢোকায়, প্রতিটি তলা ছাপে, দুটি খোঁজার পথ দেখায় (L2@17 মানে “level 2-এ খোঁজা থেমেছে 17-এ, তারপর নেমেছে”), তারপর আরও ২০০০টি এলোমেলো key ঢুকিয়ে একটি set-এর সাথে মেলায়। Node-গুলো অ্যারেতে, pointer মানে index, আর −1 মানে NIL.

#include <cstdint>
#include <iostream>
#include <set>
#include <string>
#include <vector>
using namespace std;
const int MAXL = 16;
uint32_t state = 1491;                                    // fixed seed: same levels on every run
uint32_t rnd() { state ^= state << 13; state ^= state >> 17; state ^= state << 5; return state; }  // xorshift32
vector<int> key = {-1};                                   // node 0 is the head H
vector<vector<int>> nxt = {vector<int>(MAXL, -1)};        // nxt[x][i] = next node on level i, -1 = NIL
vector<int> walk(int k, vector<string>* path = nullptr) { // last node before k on every level, top to bottom
    vector<int> upd(MAXL); int x = 0;
    for (int i = MAXL - 1; i >= 0; --i) {
        while (nxt[x][i] != -1 && key[nxt[x][i]] < k) x = nxt[x][i];
        upd[i] = x;
        if (path && nxt[0][i] != -1) path->push_back("L" + to_string(i) + "@" + (x ? to_string(key[x]) : "H"));
    }
    return upd;
}
bool contains(int k, vector<string>* path = nullptr) { int y = nxt[walk(k, path)[0]][0]; return y != -1 && key[y] == k; }
void insert(int k) {
    vector<int> upd = walk(k); int y = nxt[upd[0]][0];
    if (y != -1 && key[y] == k) return;                   // already present
    int lv = 1; while (lv < MAXL && (rnd() & 1)) ++lv;    // coin flips: heads = one more level
    int me = key.size(); key.push_back(k); nxt.push_back(vector<int>(lv, -1));
    for (int i = 0; i < lv; ++i) { nxt[me][i] = nxt[upd[i]][i]; nxt[upd[i]][i] = me; }
}
int main() {
    set<int> ref; int demo[] = {12, 3, 25, 7, 19, 9, 17, 21, 6, 26}, queries[] = {19, 10};
    for (int k : demo) { insert(k); ref.insert(k); }
    for (int i = MAXL - 1; i >= 0; --i) if (nxt[0][i] != -1) {
        cout << "L" << i << ": H"; for (int x = nxt[0][i]; x != -1; x = nxt[x][i]) cout << ' ' << key[x]; cout << '\n'; }
    for (int k : queries) {
        vector<string> path; bool ok = contains(k, &path);
        cout << "search " << k << ":"; for (auto& p : path) cout << ' ' << p; cout << " -> " << (ok ? "found" : "absent") << '\n'; }
    for (int r = 0; r < 2000; ++r) { int k = rnd() % 5000; insert(k); ref.insert(k); }
    vector<int> level0; size_t ptrs = 0, top = 0;
    for (int x = nxt[0][0]; x != -1; x = nxt[x][0]) { level0.push_back(key[x]); ptrs += nxt[x].size(); if (nxt[x].size() > top) top = nxt[x].size(); }
    bool agree = true; for (int k = 0; k < 5000; ++k) agree = agree && contains(k) == (ref.count(k) > 0);
    cout << "keys " << level0.size() << " | pointers " << ptrs << " | levels used " << top << '\n';
    cout << "level 0 matches sorted reference: " << (level0 == vector<int>(ref.begin(), ref.end()) ? "yes" : "no") << '\n';
    cout << "all searches agree: " << (agree ? "yes" : "no") << '\n';
}

L3: H 21
L2: H 17 21 26
L1: H 3 6 9 17 21 26
L0: H 3 6 7 9 12 17 19 21 25 26
search 19: L3@H L2@17 L1@17 L0@17 -> found
search 10: L3@H L2@H L1@9 L0@9 -> absent
keys 1679 | pointers 3381 | levels used 10
level 0 matches sorted reference: yes
all searches agree: yes

MAXL = 16
state = 1491                               # fixed seed: same levels on every run
def rnd():                                 # xorshift32, bit-for-bit the same as the C++ version
    global state
    state ^= (state << 13) & 0xFFFFFFFF; state ^= state >> 17; state ^= (state << 5) & 0xFFFFFFFF
    return state
key, nxt = [-1], [[-1] * MAXL]             # node 0 is the head H; nxt[x][i] = next on level i, -1 = NIL
def walk(k, path=None):                    # last node before k on every level, top to bottom
    upd, x = [0] * MAXL, 0
    for i in range(MAXL - 1, -1, -1):
        while nxt[x][i] != -1 and key[nxt[x][i]] < k: x = nxt[x][i]
        upd[i] = x
        if path is not None and nxt[0][i] != -1: path.append(f"L{i}@{key[x] if x else 'H'}")
    return upd
def contains(k, path=None):
    y = nxt[walk(k, path)[0]][0]
    return y != -1 and key[y] == k
def insert(k):
    upd = walk(k); y = nxt[upd[0]][0]
    if y != -1 and key[y] == k: return     # already present
    lv = 1
    while lv < MAXL and rnd() & 1: lv += 1 # coin flips: heads = one more level
    key.append(k); nxt.append([-1] * lv); me = len(key) - 1
    for i in range(lv): nxt[me][i], nxt[upd[i]][i] = nxt[upd[i]][i], me
ref = set()
for k in (12, 3, 25, 7, 19, 9, 17, 21, 6, 26): insert(k); ref.add(k)
for i in range(MAXL - 1, -1, -1):
    x, row = nxt[0][i], []
    while x != -1: row.append(key[x]); x = nxt[x][i]
    if row: print(f"L{i}: H", *row)
for k in (19, 10):
    path = []; ok = contains(k, path)
    print(f"search {k}:", *path, "->", "found" if ok else "absent")
for _ in range(2000): k = rnd() % 5000; insert(k); ref.add(k)
level0, x = [], nxt[0][0]
while x != -1: level0.append(key[x]); x = nxt[x][0]
print(f"keys {len(level0)} | pointers {sum(len(v) for v in nxt[1:])} | levels used {max(len(v) for v in nxt[1:])}")
print("level 0 matches sorted reference:", "yes" if level0 == sorted(ref) else "no")
print("all searches agree:", "yes" if all(contains(k) == (k in ref) for k in range(5000)) else "no")

L3: H 21
L2: H 17 21 26
L1: H 3 6 9 17 21 26
L0: H 3 6 7 9 12 17 19 21 25 26
search 19: L3@H L2@17 L1@17 L0@17 -> found
search 10: L3@H L2@H L1@9 L0@9 -> absent
keys 1679 | pointers 3381 | levels used 10
level 0 matches sorted reference: yes
all searches agree: yes

৭ · বাস্তবে — concurrency, Redis, LevelDB আর নির্দিষ্ট seed

কেন concurrent সিস্টেমে skip list

যখন একসাথে অনেক thread একই কাঠামো পড়ে আর লেখে — একটি concurrent data structure — তখন balanced tree-র rotation বড় সমস্যা: একটি rotation একসাথে কয়েকটি node-এর সম্পর্ক বদলায়, আর red-black tree-র মেরামত root পর্যন্ত ছড়াতে পারে। পুরো tree-তে একটি lock দিলে সব thread লাইনে দাঁড়ায়, যেন একটি ব্যস্ত বাজারে একটিমাত্র ক্যাশ কাউন্টার। Skip list-এ একটি insert শুধু কয়েকটি পাশাপাশি pointer বদলায়, আর প্রতিটি তলার linked list আলাদাভাবে, নিচ থেকে ওপরে, জোড়া যায়। এতে সূক্ষ্ম lock বা পুরোপুরি lock-free নকশা (compare-and-swap দিয়ে) তুলনামূলক সহজ। Java-র ConcurrentSkipListMap (Java 6 থেকে) এর একটি পরিচিত উদাহরণ।

• Redis-এর sorted set: Redis-এর sorted set (ZSET) ডেটা টাইপ বড় হলে ভেতরে একটি skip list (score অনুযায়ী সাজানো) আর একটি hash table (সদস্য থেকে score) একসাথে রাখে; ছোট sorted set রাখা হয় আরও সংক্ষিপ্ত একটি তালিকায়। লিডারবোর্ডে “১০০ থেকে ১২০তম কে” বা “এই score-এর রেঞ্জে কারা” — skip list-এর level 0 ধরে হাঁটলেই। Redis নিজে একটি thread-এ কমান্ড চালায়, তাই সেখানে পছন্দের কারণ concurrency নয় — সরলতা আর রেঞ্জ ধরে হাঁটার সুবিধা।
• LevelDB আর RocksDB-এর memtable: এই LSM-tree ভিত্তিক key-value ডেটাবেসে নতুন লেখা প্রথমে মেমরির একটি সাজানো কাঠামোয় জমে — memtable, যার ডিফল্ট রূপ একটি skip list. LevelDB-র skip list-এ লেখার জন্য বাইরে থেকে সমন্বয় লাগে, কিন্তু লেখা চলার সময়ও পড়ার জন্য lock লাগে না; RocksDB-র skip list memtable একাধিক thread-এর একসাথে লেখাও সমর্থন করে।

তবে বিনামূল্যে কিছু নেই। Skip list-এর node-গুলো মেমরিতে ছড়ানো, আর প্রতিটি পদক্ষেপ একটি pointer অনুসরণ — cache locality খারাপ। একই কাজে একটি B-tree ধাঁচের কাঠামো (পর্ব ৩০) অনেক সময় দ্রুততর, বিশেষ করে শুধু একটি thread থাকলে।

নির্দিষ্টতা আর পুনরুৎপাদন — seed কেন নির্দিষ্ট রাখবেন

Randomized কোডে বাগ ধরা কঠিন: একবার ভুল আসে, পরের বার আসে না, কারণ মুদ্রা অন্যভাবে পড়েছে। তাই পরীক্ষার সময় জেনারেটরকে একটি নির্দিষ্ট seed দিন — তখন প্রতিবার হুবহু একই সংখ্যার ধারা, একই tree, একই আউটপুট। এটিই reproducibility: যে ইনপুটে বাগ এসেছিল, সেটি আবার চালিয়ে আবার একই বাগ দেখা যায়। এই পর্বের দুটি প্রোগ্রামই তাই seed 1491 দিয়ে চলে, আর তাদের আউটপুট আপনার কম্পিউটারেও হুবহু ওপরের মতো হবে।

কিন্তু প্রোডাকশনে বা কনটেস্টে উল্টো চিন্তা লাগে। Seed যদি সবার জানা হয়, তাহলে priority-গুলোও সবার জানা — কেউ ঠিক সেই ক্রমে key পাঠাতে পারেন, যাতে treap শিকল হয়ে যায়। এটি পর্ব ৩২-এর hash flooding-এর মতোই একটি adversarial input. তাই বাস্তবে seed নেওয়া হয় অনুমান করা যায় না এমন উৎস থেকে — যেমন C++-এ random_device বা ঘড়ির সময়, Python-এ seed না দিলেই random মডিউল অপারেটিং সিস্টেমের এলোমেলো উৎস ব্যবহার করে। ভালো অভ্যাস: seed প্রোগ্রামের শুরুতে লগ করুন, যাতে দরকার হলে সেই চালানোটি আবার তৈরি করা যায়।

৮ · তুলনা আর ইতিহাস — কখন কোনটি

সংক্ষেপে: প্রতিটি কাজের কঠোর সীমা লাগলে (real-time সিস্টেম, লাইব্রেরি) red-black বা AVL; ডিস্ক হলে B-tree; নিজে দ্রুত নির্ভুল লিখতে হবে, সাথে split/merge বা sequence-এর কাজ লাগলে treap; অনেক thread একসাথে বা রেঞ্জ ধরে হাঁটা সহজ চাইলে skip list. শুধু set বা map লাগলে কনটেস্টে আগে std::set/std::map ভাবুন — নিজের treap লিখবেন তখনই, যখন লাইব্রেরি যা পারে না তা লাগবে: k-তম উপাদান, রেঞ্জ কাটা, sequence উল্টানো।

৯ · AI-এর যুগে treap আর skip list — এলোমেলো কোড, নির্দিষ্ট যাচাই

“Treap লিখে দাও” — AI সহকারী মিনিটে চল্লিশ লাইন দেবে, আর ছোট উদাহরণে প্রায়ই ঠিক উত্তরও আসবে। কিন্তু randomized কাঠামোর ভুল সবচেয়ে চতুরভাবে লুকায়: একটি ভুল priority-তুলনা tree-কে শুধু ধীর করে, ভুল নয় — inorder তবু সাজানো আসে। Complexity-র প্রশ্নে AI প্রায়ই “treap সবসময় O(log n)” বলে, “প্রত্যাশিত” শব্দটি বাদ দিয়ে।

Treap আর skip list-এর কোডে AI সাধারণত যেসব ভুল করে

Treap আর skip list যাচাইয়ের চেকলিস্ট

• প্রতিটি কাজের পর inorder (বা level 0) একটি brute force রেফারেন্সের (সাজানো vector বা std::set) সাথে মিলিয়েছি
• Invariant assert করেছি: BST নিয়ম, heap নিয়ম (প্রতিটি parent-এর priority সন্তানের চেয়ে বড়), আর sz-এর হিসাব
• সাজানো আর উল্টো সাজানো বড় ইনপুটে উচ্চতা বা তলার সংখ্যা ছেপে দেখেছি — log n-এর ছোট গুণিতক কি না
• Edge case: খালি tree-তে split/merge, একই key দুবার, নেই এমন key মোছা, k = 1 আর k = n
• পরীক্ষায় নির্দিষ্ট seed, আর কয়েকটি ভিন্ন seed-এ একই stress test — সব seed-এ উত্তর একই, শুধু আকৃতি ভিন্ন
• AI-এর complexity দাবিতে “প্রত্যাশিত” আছে কি না, আর worst case আলাদা করে জিজ্ঞেস করেছি