AVL tree — নিজে নিজে ভারসাম্য রাখা

১ · কেন ভারসাম্য — সাজানো ইনপুটে BST-এর বিপদ

পর্ব ২৭-এ binary search tree দেখেছেন: প্রতিটি node-এর বাঁ দিকের সব key তার চেয়ে ছোট, ডান দিকের সব key বড়। খুঁজতে গেলে প্রতিটি ধাপে একটি দিক বাদ পড়ে — ঠিক binary search-এর মতো। কিন্তু খরচ আসলে নির্ভর করে tree-র উচ্চতা-র ওপর: খোঁজা, insert, delete — সবই root থেকে একটি পথ ধরে নামে, তাই সময় O(h). Tree ঝাঁকড়া আর বেঁটে হলে h ≈ log₂ n; কিন্তু tree যদি এক দিকে হেলে লম্বা হয়ে যায়?

একটি বাস্তব দৃশ্য ভাবুন। একটি কলেজের ভর্তি অফিস প্রতিদিন নতুন শিক্ষার্থীর রোল নম্বর একটি BST-তে রাখে। রোল নম্বর তো বাড়তে থাকা ক্রমেই আসে: 1, 2, 3, 4, … প্রতিটি নতুন রোল আগের সবার চেয়ে বড়, তাই সে সবসময় সবচেয়ে ডানের node-এর ডান সন্তান হয়। দশজন ভর্তির পর tree দেখতে এরকম:

1
 \
  2
   \
    3
     \
      4            ... এভাবে 10 পর্যন্ত
       \
        5          উচ্চতা = n − 1 = 9
         \
          6        খুঁজতে 10টি তুলনা পর্যন্ত লাগে

এটি একটি degenerate tree — নামে tree, কাজে একটি linked list. দশ লাখ শিক্ষার্থী হলে একটি রোল খুঁজতে দশ লাখ ধাপ পর্যন্ত লাগতে পারে, যেখানে ভারসাম্যপূর্ণ tree-তে লাগত মাত্র ২০টির মতো। আর ইনপুট সাজানো হয়ে আসা মোটেই বিরল ঘটনা নয়: তারিখ, ক্রমিক নম্বর, লেনদেনের ID, আগে থেকে সাজানো ফাইল — বাস্তবের অনেক ডেটাই প্রায়-সাজানো। কনটেস্টে problem setter-রা ইচ্ছে করেই এমন test রাখেন, যাতে সাধারণ BST-এর কোড time limit ছাড়িয়ে যায়।

সমাধান কী? ইনপুট এলোমেলো করে নেওয়া সবসময় সম্ভব নয় — ডেটা একটার পর একটা আসে (online), আগে থেকে সব হাতে থাকে না। তাই দরকার এমন BST, যা প্রতিটি insert বা delete-এর পর নিজেই নিজের আকার ঠিক করে নেয়, যাতে উচ্চতা সবসময় O(log n) থাকে। একে বলে self-balancing BST. এর প্রথম উদাহরণ, আর আজও সবচেয়ে কড়া ভারসাম্যের জনপ্রিয় রূপটি হলো AVL tree.

২ · Balance factor আর AVL-এর একমাত্র নিয়ম

প্রথমে উচ্চতার সংজ্ঞা পাকা করি, কারণ বইভেদে এখানে ১-এর পার্থক্য থাকে। এই পর্বে (আর কোডে) কোনো node-এর উচ্চতা মানে সেই node থেকে তার নিচের সবচেয়ে গভীর leaf পর্যন্ত edge-এর সংখ্যা। তাই একটি leaf-এর উচ্চতা 0, আর খালি tree-র উচ্চতা −1 ধরা হয় — যাতে “উচ্চতা = 1 + দুই সন্তানের উচ্চতার বড়টি” সূত্রটি leaf-এর জন্যও খাটে: 1 + max(−1, −1) = 0. (অনেক বই আর কোড খালি tree-কে 0, leaf-কে 1 ধরে। তাতে সব উচ্চতা ১ করে বাড়ে, কিন্তু নিচের পার্থক্যগুলো একই থাকে।)

প্রতিটি node-এর একটি subtree বাঁয়ে, একটি ডানে। এদের উচ্চতার পার্থক্যই balance factor:

bf ধনাত্মক মানে বাঁ দিক উঁচু (বাঁয়ে ভারী), ঋণাত্মক মানে ডান দিক উঁচু। (কিছু বই উল্টো চিহ্ন ব্যবহার করে — ডান − বাঁ; পরীক্ষায় প্রশ্ন কোন সংজ্ঞা ধরেছে, আগে দেখে নিন।) এবার AVL-এর পুরো সংজ্ঞাটি এক লাইনে:

“প্রতিটি node-এ” কথাটি গুরুত্বপূর্ণ। শুধু root-এর দুই দিক সমান উচ্চতার হলেই চলবে না — নিচের দুটি দিকই আলাদা আলাদা লম্বা শিকল হতে পারে, যেখানে root-এর bf 0 অথচ উচ্চতা প্রায় n/2. তিনটি ছোট উদাহরণ দেখুন (বন্ধনীতে bf):

   (ক) AVL              (খ) AVL নয়            (গ) AVL নয়
     8(+1)                8(+2)                 8(0)
    /    \               /                     /    \
  4(0)   9(0)          4(+1)                 4(+2)   12(-2)
  / \                  /                     /          \
 2   6               2(0)                  2(+1)        14(-1)
                                           /               \
                                          1                 15

(গ)-তে প্রতিটি মান নিজে মিলিয়ে নিন। 4-এর বাঁয়ে 2 → 1 শিকল, উচ্চতা 1; ডানে কিছু নেই, উচ্চতা −1; তাই bf(4) = 1 − (−1) = +2. একই হিসাবে bf(12) = −1 − 1 = −2. Root-এর দুই দিকের উচ্চতা 2 আর 2 — bf 0, তবু tree-টি AVL নয়। চোখে দেখে “প্রায় সমান” মনে হলেও প্রতিটি node-এর bf নিচ থেকে ওপরে উচ্চতা গুনে বের করুন — এটিই নিরাপদ পদ্ধতি, আর কোডেও ঠিক তা-ই করা হবে।

লক্ষ করুন, +3 বা −3 কখনো আসে না। একটি insert বা delete কোনো subtree-র উচ্চতা সর্বোচ্চ ১ বদলায়, আর মেরামত সঙ্গে সঙ্গে হয় — তাই নিয়ম ভাঙলেও bf ঠিক ±2-তেই থামে। কোডে এই তথ্যটি সাহায্য করে: শুধু দুটি অবস্থা (bf > 1, bf < −1) সামলালেই হয়।

৩ · উচ্চতা কেন O(log n) — minimal AVL tree আর Fibonacci

|bf| ≤ 1 নিয়মটি শিথিল — নিখুঁত ভারসাম্য চায় না। তাহলে উচ্চতা কতটা খারাপ হতে পারে? প্রশ্নটি উল্টো করে ধরলে সহজ হয়: উচ্চতা h-এর একটি AVL tree-তে সবচেয়ে কম কয়টি node থাকতে পারে? এই সংখ্যাকে বলি N(h). যদি দেখাতে পারি N(h) সূচকীয় হারে বাড়ে, তাহলে n টি node-এ উচ্চতা log-এর বেশি হতে পারবে না।

সবচেয়ে কম node-এ উচ্চতা h বানাতে হলে root-এর এক দিকে উচ্চতা h − 1-এর subtree লাগবেই (নইলে root-এর উচ্চতা h হবে না)। অন্য দিকটি যত ছোট সম্ভব রাখতে চাই — কিন্তু |bf| ≤ 1-এর জন্য সেটি h − 2-এর নিচে নামতে পারে না। আর দুই subtree নিজেরাও AVL, তাই তারাও নিজ নিজ উচ্চতার সবচেয়ে ছোট AVL tree হলেই node সবচেয়ে কম। এভাবে যে tree পাওয়া যায় তাকে বলে minimal AVL tree (বা Fibonacci tree). নিচের ডায়াগ্রামে @ হলো root, a চিহ্নের node-গুলো উচ্চতা h − 1-এর minimal tree, b চিহ্নেরগুলো উচ্চতা h − 2-এর:

প্রমাণ — Fibonacci থেকে 1.44 log₂ n

ডায়াগ্রাম থেকে recurrence পাওয়া গেল (পর্ব ০৮-এর ভাষায় একটি recurrence):

দুই দিকে 1 যোগ করুন: N(h) + 1 = (N(h−1) + 1) + (N(h−2) + 1). অর্থাৎ M(h) = N(h) + 1 ঠিক Fibonacci-র নিয়ম মানে, আর M(0) = 2 = F(3), M(1) = 3 = F(4) (এখানে F(1) = F(2) = 1, F(3) = 2, …). Induction দিয়ে সরাসরি: যদি M(h−1) = F(h+2) আর M(h−2) = F(h+1), তাহলে M(h) = F(h+2) + F(h+1) = F(h+3). তাই

পর্ব ০৮-এ দেখেছেন, Fibonacci সংখ্যা golden ratio φ = (1 + √5)/2 ≈ 1.618-এর সূচকের মতো বাড়ে: F(k) হলো φ^k/√5-এর নিকটতম পূর্ণসংখ্যা। এবার যেকোনো AVL tree নিন, যার n টি node আর উচ্চতা h. minimal tree-র সংজ্ঞা অনুযায়ী n ≥ N(h) = F(h+3) − 1, তাই n + 2 > F(h+3) + ½ > φ^h+3/√5. দুই দিকে log_φ নিন:

এখানে log_φ x = log₂ x / log₂ φ ≈ 1.4404 · log₂ x, আর log_φ √5 ≈ 1.672. মোদ্দা কথা: AVL tree-র উচ্চতা কখনো 1.44 log₂ n-এর চেয়ে উল্লেখযোগ্যভাবে বেশি হয় না — নিখুঁত ভারসাম্যের চেয়ে বড়জোর প্রায় ৪৪% বেশি। আর minimal tree-গুলো নিজেরাই বৈধ AVL tree, তাই এই সীমা আঁটসাঁট (tight): এর চেয়ে ভালো সীমা প্রমাণ করা যায় না।

AVL-এর কলামটি সূত্র থেকে নয়, সরাসরি N(h) থেকে: সবচেয়ে বড় h, যার জন্য N(h) ≤ n. যেমন N(27) = 832,039 ≤ 10⁶ < N(28) = 1,346,268, তাই দশ লাখ node-এর AVL tree-র উচ্চতা কখনো 27 ছাড়ায় না। দশ লাখ রোল নম্বরের যেকোনোটি খুঁজতে সর্বোচ্চ ২৮টি তুলনা — degenerate BST-এর দশ লাখের জায়গায়।

৪ · Rotation — তিনটি pointer বদলে ভারসাম্য

ভারসাম্য ফেরানোর একমাত্র যন্ত্র rotation. ধারণাটি একটি অফিসের পদ বদলের মতো: বিভাগের প্রধান y অবসরে যাচ্ছেন না, শুধু তাঁর সহকারী x তাঁর জায়গায় উঠে আসছেন, আর y হয়ে যাচ্ছেন x-এর অধীন। কিন্তু সবার বাঁ-ডান ক্রম (কে কার চেয়ে ছোট) একই থাকে। নিচে right rotation (y-এ, যার বাঁ সন্তান x) ধাপে ধাপে দেখুন। A, B, C হলো তিনটি subtree — খালিও হতে পারে, বিশাল-ও হতে পারে; rotation-এ এদের ভেতরে কিছুই বদলায় না।

কেন BST-র নিয়ম ভাঙে না. BST-র শর্তটি আসলে in-order ক্রমের শর্ত: tree-কে বাঁ থেকে ডানে পড়লে (in-order traversal, পর্ব ২৬) key-গুলো সাজানো ক্রমে আসে। Rotation-এর আগে ক্রম A, x, B, y, C; পরে x-এর বাঁয়ে A, ডানে y — আর y-এর বাঁয়ে B, ডানে C — অর্থাৎ আবারও A, x, B, y, C. যেহেতু ক্রম একই, BST-ও বৈধ। আর A, B, C-এর বাইরের কোনো node (p ও তার ওপরের সবাই) কোনো পরিবর্তন দেখে না, শুধু p-এর একটি pointer ছাড়া।

Left rotation হুবহু আয়নার প্রতিবিম্ব: x-এ, যার ডান সন্তান y — x.right = y.left, y.left = x, আগে x তারপর y-এর উচ্চতা, আর parent-এর pointer y-তে। Right rotation বাঁয়ে ভারী অবস্থা সারায় (বাঁ সন্তানকে ওপরে তোলে), left rotation ডানে ভারী অবস্থা।

Node* rotRight(Node* y) {          // y's left child x moves up
    Node* x = y->l;
    y->l = x->r;                    // subtree B changes parent: x -> y
    x->r = y;
    fix(y); fix(x);                 // heights: lower node first
    return x;                       // caller links the new subtree root
}
Node* rotLeft(Node* x) {           // mirror image: x's right child y moves up
    Node* y = x->r;
    x->r = y->l;
    y->l = x;
    fix(x); fix(y);
    return y;
}

৫ · চার ধরনের ভারসাম্যহীনতা — LL, RR, LR, RL

ধরুন কোনো node z-এর bf হয়ে গেল ±2. কোন rotation লাগবে, তা ঠিক করে কোন পথে ভারী: z থেকে উঁচু সন্তানের দিকে এক ধাপ, তারপর সেই সন্তানের উঁচু দিকে আরেক ধাপ। দুই ধাপের দিক মিলিয়ে চারটি নাম — L মানে বাঁয়ে, R মানে ডানে।

“≥ 0” আর “≤ 0”-এর সমান চিহ্নটি এখনই খেয়াল রাখুন: insert-এর পর সন্তানের bf কখনো 0 হয় না (অংশ ৬), কিন্তু delete-এর পর হতে পারে — আর তখন single rotation-ই ঠিক উত্তর (অংশ ৭). সোজা লাইনের দুটি অবস্থা আগে দেখি — ছোট তিনটি key দিয়ে:

এবার আঁকাবাঁকা অবস্থা। এখানে একটি rotation যথেষ্ট নয় — আর কেন নয়, তা নিজের চোখে দেখা দরকার:

RL হুবহু আয়না। কিন্তু তিন node-এর ছোট উদাহরণে একটি জিনিস চোখে পড়ে না: নাতির নিজের দুটি subtree কোথায় যায়? সাধারণ রূপে দেখুন — z-এর ডান সন্তান y, y-এর বাঁ সন্তান x, আর A, B, C, D চারটি subtree:

৬ · Insert — ফেরার পথে প্রথম ভারসাম্যহীন পূর্বপুরুষে মেরামত

AVL insert দুই ভাগে চলে। নামার পথ: সাধারণ BST-এর মতো root থেকে নেমে খালি জায়গায় নতুন leaf বসানো (পর্ব ২৭). ফেরার পথ: নতুন leaf থেকে root-এর দিকে উঠতে উঠতে প্রতিটি পূর্বপুরুষের উচ্চতা আর bf হালনাগাদ করা — একে বলে retracing. Recursive কোডে এটি আপনাআপনি হয়: recursive call থেকে ফেরার পর প্রতিটি স্তরে rebalance চলে। (পর্ব ০৭-এর recursion-এর call stack-ই এখানে “ফেরার পথ” মনে রাখে।)

Pseudocode — AVL insert (height of an empty tree = -1)

height(t):  if t is empty: return -1  else: return t.h
bf(t):      return height(t.left) - height(t.right)

rebalance(t):                          // both children are valid AVL trees
    t.h = 1 + max(height(t.left), height(t.right))
    if bf(t) = +2:                                        // left side too tall
        if bf(t.left) < 0: t.left = rotateLeft(t.left)     // LR: straighten first
        return rotateRight(t)                             // LL
    if bf(t) = -2:                                        // right side too tall
        if bf(t.right) > 0: t.right = rotateRight(t.right) // RL: straighten first
        return rotateLeft(t)                              // RR
    return t

insert(t, k):
    if t is empty: return new leaf(k)            // h = 0, bf = 0
    if k < t.key:      t.left  = insert(t.left, k)
    else if k > t.key: t.right = insert(t.right, k)
    return rebalance(t)                          // runs on the way back up

একটি বড় উদাহরণে retracing দেখুন। বৈধ AVL tree-তে 25 যোগ করা হচ্ছে:

প্রমাণ — কেন insert-এ একটি মেরামতই যথেষ্ট

শেষ ধাপে যা ঘটল, তা কাকতালীয় নয়। দাবি: insert-এর পর প্রথম ভারসাম্যহীন পূর্বপুরুষ z-এ rotation করলে z-এর subtree-র উচ্চতা ঠিক insert-এর আগের উচ্চতায় ফিরে আসে. LL ক্ষেত্রে হিসাবটি দেখুন। insert-এর আগে z-এর উচ্চতা h+2 ধরি, বাঁ সন্তান y-এর h+1, ডান subtree C-এর h (z-এর bf তখন +1 ছিল — নইলে একটি insert-এ +2 হতো না)। y-এর বাঁ subtree A আর ডান B দুটোই উচ্চতা h (insert-এর আগে y-এর bf 0 ছিল — +1 হলে y নিজেই প্রথম ভারসাম্যহীন হতো, আর −1 হলে A বাড়লেও y-এর উচ্চতা বাড়ত না)। নতুন key A-তে গিয়ে A-কে h+1 করল; তখন y = h+2, z = h+3, bf(z) = +2. Right rotation-এর পর: z-এর সন্তান B (h) আর C (h), তাই z = h+1; y-এর সন্তান A (h+1) আর z (h+1), তাই y = h+2 — আগের মতোই h+2.

LR ক্ষেত্রে: আগে z = h+2, y = h+1 (A = h, নাতি x = h), D = h. insert x-এর কোনো subtree-কে বাড়িয়ে x-কে h+1 করে (x-এর দুই subtree তখন h আর h − 1, বা x নিজেই নতুন leaf). Double rotation-এর পর x root, তার বাঁয়ে y (A আর B — দুটোর উচ্চতা ≤ h, অন্তত একটি h), ডানে z (C আর D) — দুজনেরই উচ্চতা h+1, তাই x = h+2. আবারও আগের উচ্চতা। RR আর RL আয়না।

তাহলে z-এর ওপরের সব পূর্বপুরুষ দেখে, তাদের নিচের subtree-র উচ্চতা একটুও বদলায়নি — তাদের bf আগের মতোই বৈধ। তাই একটি insert-এ সর্বোচ্চ একটি single বা একটি double rotation (অর্থাৎ ≤ ২টি মৌলিক rotation). আরও একটি থামার শর্ত আছে: ফেরার পথে কোনো node-এর উচ্চতা যদি না বাড়ে (তার bf ±1 থেকে 0 হলো), তাহলেও ওপরে আর কিছু বদলাবে না। Iterative কোডে এই দুই জায়গায় loop ভেঙে বেরিয়ে আসা যায়; recursive কোডে বাকি স্তরগুলো শুধু উচ্চতা হিসাব করে, কিছু বদলায় না।

আর একটি সূক্ষ্ম কথা: insert-এর পর z-এর উঁচু সন্তানের bf কখনো 0 হয় না। সন্তানটির উচ্চতা এইমাত্র বেড়েছে, আর উচ্চতা বাড়ে কেবল একটি দিক বাড়লে — তাই তার bf ±1. এজন্যই insert-এ শুধু চারটি অবস্থা।

কোডে — কোন rotation কখন চলল, তা ছাপিয়ে দেখা

নিচের প্রোগ্রাম দশটি key একে একে insert করে, আর প্রতিটির পর ছাপায় কোন rotation চলল আর tree-টি কেমন দেখাচ্ছে। Tree ছাপানোর ছোট রূপ: (বাঁ key ডান), খালি subtree = ., leaf শুধু তার key. শেষে check পুরো tree ঘুরে তিনটি জিনিস assert করে: BST ক্রম, প্রতিটি node-এর |bf| ≤ 1, আর রাখা উচ্চতা আসল উচ্চতার সমান।

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <initializer_list>
#include <string>
using namespace std;
struct Node { int key, h = 0; Node *l = nullptr, *r = nullptr; };
int ht(Node* t) { return t ? t->h : -1; }                    // empty tree has height -1
void fix(Node* t) { t->h = 1 + max(ht(t->l), ht(t->r)); }
int bf(Node* t) { return ht(t->l) - ht(t->r); }              // balance factor
Node* rotRight(Node* y) { Node* x = y->l; y->l = x->r; x->r = y; fix(y); fix(x); return x; }
Node* rotLeft(Node* x) { Node* y = x->r; x->r = y->l; y->l = x; fix(x); fix(y); return y; }
string fired;                                                // which rotation this insert used
Node* insert(Node* t, int k) {
    if (!t) return new Node{k};
    if (k < t->key) t->l = insert(t->l, k); else if (k > t->key) t->r = insert(t->r, k);
    fix(t);                                                  // retracing: we are on the way back up
    if (bf(t) > 1) {                                         // left side too tall: LL or LR
        fired = string(bf(t->l) < 0 ? "LR" : "LL") + " at " + to_string(t->key);
        if (bf(t->l) < 0) t->l = rotLeft(t->l);
        t = rotRight(t);
    } else if (bf(t) < -1) {                                 // right side too tall: RR or RL
        fired = string(bf(t->r) > 0 ? "RL" : "RR") + " at " + to_string(t->key);
        if (bf(t->r) > 0) t->r = rotRight(t->r);
        t = rotLeft(t);
    }
    return t;
}
string show(Node* t) {                                       // "(left key right)", "." = empty
    if (!t) return ".";
    if (!t->l && !t->r) return to_string(t->key);
    return "(" + show(t->l) + " " + to_string(t->key) + " " + show(t->r) + ")";
}
int check(Node* t, long lo, long hi) {                       // returns height; asserts every rule
    if (!t) return -1;
    int a = check(t->l, lo, t->key), b = check(t->r, t->key, hi);
    assert(lo < t->key && t->key < hi && a - b <= 1 && b - a <= 1 && t->h == 1 + max(a, b));
    return t->h;
}
int main() {
    Node* root = nullptr;
    for (int k : {50, 40, 30, 60, 70, 20, 25, 80, 75, 10}) {
        fired = "none"; root = insert(root, k);
        printf("insert %2d  %-9s  %s\n", k, fired.c_str(), show(root).c_str());
    }
    printf("AVL invariant OK, height = %d\n", check(root, -1000000, 1000000));
}

insert 50  none       50
insert 40  none       (40 50 .)
insert 30  LL at 50   (30 40 50)
insert 60  none       (30 40 (. 50 60))
insert 70  RR at 50   (30 40 (50 60 70))
insert 20  none       ((20 30 .) 40 (50 60 70))
insert 25  LR at 30   ((20 25 30) 40 (50 60 70))
insert 80  none       ((20 25 30) 40 (50 60 (. 70 80)))
insert 75  RL at 70   ((20 25 30) 40 (50 60 (70 75 80)))
insert 10  none       (((10 20 .) 25 30) 40 (50 60 (70 75 80)))
AVL invariant OK, height = 3

class Node:
    def __init__(self, key): self.key, self.h, self.l, self.r = key, 0, None, None
def ht(t): return t.h if t else -1                 # empty tree has height -1
def fix(t): t.h = 1 + max(ht(t.l), ht(t.r))
def bf(t): return ht(t.l) - ht(t.r)                # balance factor
def rot_right(y): x = y.l; y.l, x.r = x.r, y; fix(y); fix(x); return x
def rot_left(x): y = x.r; x.r, y.l = y.l, x; fix(x); fix(y); return y
fired = "none"                                      # which rotation this insert used
def insert(t, k):
    global fired
    if t is None: return Node(k)
    if k < t.key: t.l = insert(t.l, k)
    elif k > t.key: t.r = insert(t.r, k)
    fix(t)                                          # retracing: on the way back up
    if bf(t) > 1:                                   # left side too tall: LL or LR
        fired = ("LR" if bf(t.l) < 0 else "LL") + f" at {t.key}"
        if bf(t.l) < 0: t.l = rot_left(t.l)
        t = rot_right(t)
    elif bf(t) < -1:                                # right side too tall: RR or RL
        fired = ("RL" if bf(t.r) > 0 else "RR") + f" at {t.key}"
        if bf(t.r) > 0: t.r = rot_right(t.r)
        t = rot_left(t)
    return t
def show(t):                                        # "(left key right)", "." = empty
    if t is None: return "."
    if t.l is None and t.r is None: return str(t.key)
    return f"({show(t.l)} {t.key} {show(t.r)})"
def check(t, lo, hi):                               # returns height; asserts every rule
    if t is None: return -1
    a, b = check(t.l, lo, t.key), check(t.r, t.key, hi)
    assert lo < t.key < hi and abs(a - b) <= 1 and t.h == 1 + max(a, b)
    return t.h
root = None
for k in [50, 40, 30, 60, 70, 20, 25, 80, 75, 10]:
    fired = "none"; root = insert(root, k)
    print(f"insert {k:2d}  {fired:<9}  {show(root)}")
print(f"AVL invariant OK, height = {check(root, -1000000, 1000000)}")

insert 50  none       50
insert 40  none       (40 50 .)
insert 30  LL at 50   (30 40 50)
insert 60  none       (30 40 (. 50 60))
insert 70  RR at 50   (30 40 (50 60 70))
insert 20  none       ((20 30 .) 40 (50 60 70))
insert 25  LR at 30   ((20 25 30) 40 (50 60 70))
insert 80  none       ((20 25 30) 40 (50 60 (. 70 80)))
insert 75  RL at 70   ((20 25 30) 40 (50 60 (70 75 80)))
insert 10  none       (((10 20 .) 25 30) 40 (50 60 (70 75 80)))
AVL invariant OK, height = 3

নিজে চালিয়ে দেখুন — 1 থেকে 10, আর rotation-গুলো

অংশ ১-এর ভর্তি অফিসের সমস্যায় ফিরি: রোল নম্বর 1, 2, 3, … ক্রমে আসছে। নিচের টুলে “চালিয়ে দেখুন” চাপুন — কোডটি নিজেই 1 থেকে 10 insert করবে। তারপর পরের সংখ্যা চেপে 11, 12, … যোগ করুন, বা নিজের মান লিখে insert চাপুন। প্রতিটি node-এর ওপরে ডানে ছোট সংখ্যাটি তার bf; লাল node-গুলো নতুন যোগ হওয়া node আর যেখানে rotation হলো। নিচের লাইনে AVL-এর উচ্চতার পাশে দেখাবে, একই ইনপুটে সাধারণ BST-এর উচ্চতা কত হতো।

const mk = k => ({ key: k, h: 0, l: null, r: null });
const ht = t => (t ? t.h : -1), bal = t => ht(t.l) - ht(t.r);
const fix = t => { t.h = 1 + Math.max(ht(t.l), ht(t.r)); return t; };
const rotR = y => { const x = y.l; y.l = x.r; x.r = y; fix(y); return fix(x); };
const rotL = x => { const y = x.r; x.r = y.l; y.l = x; fix(x); return fix(y); };
const $ = id => document.getElementById(id);
let root = null, plain = null, nextKey = 1, fired = [], hot = new Set();
function ins(t, k) {                                   // AVL insert, remembers which rotation fired
  if (!t) { hot.add(k); return mk(k); }
  if (k < t.key) t.l = ins(t.l, k); else if (k > t.key) t.r = ins(t.r, k); else return t;
  const b = bal(fix(t));
  if (Math.abs(b) < 2) return t;                       // still balanced here: keep retracing
  const kind = b > 1 ? (bal(t.l) < 0 ? "LR" : "LL") : (bal(t.r) > 0 ? "RL" : "RR");
  fired.push(kind + " at " + t.key); hot.add(t.key);
  if (kind === "LR") t.l = rotL(t.l); else if (kind === "RL") t.r = rotR(t.r);   // straighten first
  return b > 1 ? rotR(t) : rotL(t);
}
const bstIns = (t, k) => { if (!t) return mk(k); if (k < t.key) t.l = bstIns(t.l, k); else if (k > t.key) t.r = bstIns(t.r, k); return fix(t); };
function draw(msg) {                                   // x = in-order rank, y = depth
  const pos = new Map(); let i = 0, lines = "", html = "";
  (function walk(t, d) { if (t) { walk(t.l, d + 1); pos.set(t, [i++ * 38 + 24, d * 52 + 24]); walk(t.r, d + 1); } })(root, 0);
  for (const [t, [x, y]] of pos) {
    for (const c of [t.l, t.r]) if (c) lines += `<line x1="${x}" y1="${y}" x2="${pos.get(c)[0]}" y2="${pos.get(c)[1]}"/>`;
    html += `<div class="nd${hot.has(t.key) ? " hl" : ""}" style="left:${x - 17}px;top:${y - 17}px">${t.key}<sub>${bal(t) > 0 ? "+" : ""}${bal(t)}</sub></div>`;
  }
  const H = (ht(root) + 1) * 52 + 10; $("sv").setAttribute("width", i * 38 + 30); $("sv").setAttribute("height", H); $("wrap").style.height = H + "px";
  $("sv").innerHTML = lines; $("nd").innerHTML = html; $("msg").textContent = msg; console.log(msg);
}
function add(k) {
  fired = []; hot = new Set(); root = ins(root, k); plain = bstIns(plain, k);
  draw(`insert ${String(k).padStart(2)}: ${(fired[0] || "no rotation").padEnd(11)} AVL height ${ht(root)}, plain BST height ${ht(plain)}`);
}
$("bn").onclick = () => add(nextKey++); $("bi").onclick = () => add(Number($("av").value));
$("br").onclick = () => { root = plain = null; nextKey = 1; draw("empty tree"); };
for (let k = 1; k <= 10; k++) add(nextKey++);

insert  1: no rotation AVL height 0, plain BST height 0
insert  2: no rotation AVL height 1, plain BST height 1
insert  3: RR at 1     AVL height 1, plain BST height 2
insert  4: no rotation AVL height 2, plain BST height 3
insert  5: RR at 3     AVL height 2, plain BST height 4
insert  6: RR at 2     AVL height 2, plain BST height 5
insert  7: RR at 5     AVL height 2, plain BST height 6
insert  8: no rotation AVL height 3, plain BST height 7
insert  9: RR at 7     AVL height 3, plain BST height 8
insert 10: RR at 6     AVL height 3, plain BST height 9

৭ · Delete — মেরামত ছড়াতে পারে root পর্যন্ত

Delete-ও দুই ভাগে। প্রথমে পর্ব ২৭-এর সাধারণ BST delete: leaf হলে সরিয়ে দিন; একটি সন্তান থাকলে সেই সন্তানকে তার জায়গায় তুলুন; দুটি সন্তান থাকলে key-টির জায়গায় তার in-order successor (ডান subtree-র সবচেয়ে ছোট key) বসিয়ে successor-এর পুরোনো node মুছুন। তারপর, যেখান থেকে node আসলে সরানো হলো, সেখান থেকে root পর্যন্ত retracing — insert-এর হুবহু একই rebalance.

পার্থক্যটা থামার নিয়মে। Insert-এর rotation subtree-র উচ্চতা আগের মানে ফিরিয়ে দেয়। কিন্তু delete এমনিতেই একটি দিক ছোট করেছে; rotation সেই subtree-র ভারসাম্য ফেরায়, অথচ প্রায়ই তার উচ্চতা এক কমে যায় — আর তাতে ওপরের পূর্বপুরুষের ভারসাম্য নতুন করে ভাঙতে পারে। সবচেয়ে খারাপ উদাহরণ minimal AVL tree, যেখানে প্রতিটি node আগে থেকেই এক দিকে হেলে আছে:

তাই delete-এ rotation-এর সংখ্যা worst case-এ Θ(log n) — প্রায় প্রতি দুই স্তরে একটি। তবু মোট সময় O(log n), কারণ প্রতিটি rotation O(1) আর পথটির দৈর্ঘ্যই O(log n). থামার নিয়ম: ফেরার পথে কোনো node-এর উচ্চতা না বদলালে (rotation-সহ বা ছাড়া) থামা যায়।

Delete-এর একটি নতুন অবস্থাও আছে, যা insert-এ কখনো আসে না: z-এর bf ±2, কিন্তু উঁচু সন্তানের bf 0. যেমন z-এর ডান সন্তান y-এর দুই subtree-ই সমান উঁচু, আর z-এর বাঁ দিক থেকে একটি node মুছে গেল। তখন single rotation (RR) করুন — double নয়। Single rotation-এর পর z-এর bf −1 আর y-এর bf +1 হয়, আর subtree-র উচ্চতা বদলায় না — তাই retracing সেখানেই থামে। অংশ ৫-এর টেবিলের “≥ 0” আর “≤ 0” এই অবস্থার জন্যই। এখানে double rotation করলে উল্টো ফল: tree ভারসাম্যহীনই থেকে যেতে পারে। অনুশীলনের দ্বিতীয় প্রশ্নে এই অবস্থাটি নিজে হাতে দেখবেন।

৮ · উচ্চতা না bf, সব কাজের খরচ, আর AVL বনাম red-black

প্রতিটি node-এ কী রাখবেন — উচ্চতা, নাকি শুধু balance factor?

এই পর্বের কোড প্রতিটি node-এ পুরো উচ্চতা (একটি int) রাখে, আর bf দরকার হলে দুই সন্তানের উচ্চতা থেকে হিসাব করে। সুবিধা: কোড সরল আর ভুল হওয়ার সুযোগ কম — rotation-এর পর শুধু fix() ডাকলেই সব ঠিক। Adelson-Velsky আর Landis-এর মূল প্রবন্ধ আর Knuth-এর বই রাখত শুধু bf — তিনটি সম্ভাব্য মান, অর্থাৎ ২টি bit. মেমরি কম, কিন্তু উচ্চতা জানা নেই বলে প্রতিটি rotation-এর পর নতুন bf-গুলো কেস ধরে বের করতে হয়। যেমন double rotation (LR)-এর পর নতুন bf নির্ভর করে নাতি x-এর পুরোনো bf-এর ওপর:

এই টেবিল ভুল মনে রাখা AVL কোডের সবচেয়ে পরিচিত বাগগুলোর একটি — ছোট test-এ ধরা পড়ে না, হাজার insert-এর পর tree চুপচাপ ভারসাম্য হারায়। কনটেস্ট আর শেখার জন্য উচ্চতা রাখাই ভালো; মেমরি খুব সীমিত হলে (কোটি কোটি node) bf রাখার কথা ভাবা যায় — তখন অনেক বাস্তবায়ন ২টি bit pointer-এর অব্যবহৃত নিচের bit-এ লুকিয়ে রাখে, যেভাবে Linux kernel-এর red-black tree node-এর রং parent pointer-এর ভেতরে রাখে।

সব কাজের খরচ

একটি তুলনা মনে রাখুন: n টি key একে একে insert করে AVL বানাতে O(n log n), আর সেই tree-র in-order পড়লেই সাজানো ক্রম — তাই AVL দিয়েও O(n log n)-এ sort করা যায় (tree sort). Ω(n log n) তুলনার নিম্নসীমা (পর্ব ২৪) দেখায়, শুধু তুলনা-ভিত্তিক কোনো BST-তে insert O(log n)-এর চেয়ে দ্রুত হতে পারে না — যদি পারত, sort-ও দ্রুত হতো।

AVL বনাম red-black tree

পরের পর্বে (পর্ব ২৯) red-black tree বিস্তারিত দেখবেন। সংক্ষেপে: সেখানে প্রতিটি node লাল বা কালো, আর রঙের কয়েকটি নিয়ম মানলে উচ্চতা 2 log₂(n + 1)-এর বেশি হয় না। নিয়মটি AVL-এর চেয়ে শিথিল — tree বেশি হেলে থাকতে পারে, কিন্তু বদলে মেরামত কম লাগে।

সারকথা: AVL কড়া ভারসাম্য রাখে, তাই গড়ে tree একটু বেঁটে আর খোঁজা একটু দ্রুত; কিন্তু সেই কড়াকড়ি বজায় রাখতে delete-এ বেশি rotation লাগতে পারে। দুটিই worst case O(log n) — পার্থক্য ধ্রুবকে আর কাজের ধরনে। C++-এ নিজে না লিখে std::set/std::map ব্যবহার করুন (পর্ব ১৫-এর associative container); Python-এর standard library-তে কোনো balanced BST নেই — সেখানে প্রচলিত বিকল্প তৃতীয় পক্ষের sortedcontainers লাইব্রেরি, বা সমস্যা বুঝে bisect, heap বা Fenwick tree (পর্ব ৩৬).

৯ · AI-এর যুগে AVL tree — rotation ঠিক, হিসাব ভুল

“AVL tree-র insert আর delete লিখে দাও” — AI কয়েক সেকেন্ডে লিখবে, আর ছোট উদাহরণে চলবেও। AVL-এর বাগ সাধারণত দৃশ্যমান হয় না: tree ক্র্যাশ করে না, শুধু নীরবে ভারসাম্য হারায়, আর সব কিছু ধীর হয়ে যায় — অথচ উত্তর তখনো ঠিক আসে, কারণ BST-এর ক্রম অটুট থাকে। তাই আউটপুট মিলিয়ে নয়, invariant যাচাই করে AVL কোড পরীক্ষা করতে হয়।

AVL-এর কোডে AI সাধারণত যেসব ভুল করে

AVL কোড যাচাইয়ের চেকলিস্ট

• একটি check() লিখেছি যা BST ক্রম, প্রতিটি node-এর |bf| ≤ 1 আর রাখা উচ্চতা — তিনটিই assert করে
• চারটি অবস্থা আলাদা ছোট ইনপুটে হাতে trace করেছি: 30 20 10 (LL), 10 20 30 (RR), 30 10 20 (LR), 10 30 20 (RL)
• Edge case চালিয়েছি: খালি tree, এক node, একই key দুবার, root মোছা, দুই সন্তানওয়ালা node মোছা, সব মুছে খালি করা
• হাজার হাজার এলোমেলো insert/delete-এর পর std::set বা সাজানো list-এর সাথে মিলিয়ে stress testing করেছি, প্রতিটি ধাপে check() চালিয়ে
• সাজানো ইনপুটে (1 থেকে 10⁵) উচ্চতা ছাপিয়ে দেখেছি — 1.44 log₂ n-এর নিচে — n = 10⁵-এ কখনো ২২-এর বেশি নয় (সাজানো ইনপুটে আসলে ১৬)
• AI যে complexity বা rotation-সংখ্যা বলেছে, তা N(h)-এর যুক্তি আর minimal tree-র উদাহরণ দিয়ে নিজে যাচাই করেছি