ট্রিপড়তে ৭ মিনিট লাগবে

এভিএল ট্রি (AVL Tree)

নিজে থেকেই ব্যালান্স ঠিক রাখা ট্রি — যতই কাটাকাটি করুন, ও ঠিকই সোজা হয়ে দাঁড়াবে

search: O(log n)insert: O(log n)rotate: O(1)space: O(n)

এভিএল ট্রি (AVL tree) হলো একটা বাইনারি সার্চ ট্রি (BST), যার একটা কড়া নিয়ম আছে: প্রতিবার নতুন কিছু ঢোকানো বা ডিলিট করার পর একে নিজের ব্যালান্স বা ভারসম্য ঠিক রাখতেই হবে। এর আবিষ্কারক Adelson-Velsky এবং Landis (১৯৬২)-এর নামের আদ্যক্ষর মিলিয়ে এর নাম দেওয়া হয়েছে। ইতিহাসে এটাই হলো সর্বপ্রথম আবিষ্কৃত 'সেলফ-ব্যালান্সিং' (self-balancing) বা নিজে নিজে সোজা হওয়া ট্রি।

এর নিয়মটা একদম সোজা: ট্রির যেকোনো নোডের ক্ষেত্রে, তার বাঁ দিকের ডাল (left subtree) এবং ডান দিকের ডালের (right subtree) উচ্চতার পার্থক্য সর্বোচ্চ ১ হতে পারবে। এই গ্যারান্টির কারণেই ট্রির উচ্চতা কখনোই O(log n)-এর বেশি হতে পারে না — অর্থাৎ ট্রিটা কখনোই একপাশে হেলে পড়ে লম্বা সুতোর মতো (degenerate) হয়ে যায় না।

ব্যালান্স ফ্যাক্টর (The balance factor)

প্রতিটা নোড তার নিজের ব্যালান্স ফ্যাক্টর মনে রাখে:

pseudocode

ব্যালান্স ফ্যাক্টর = উচ্চতা(বাঁ দিকের ডাল) - উচ্চতা(ডান দিকের ডাল)

একটা ঠিকঠাক এভিএল ট্রিতে সব নোডের ব্যালান্স ফ্যাক্টর অবশ্যই এই তিনটার যেকোনো একটা হতে হবে: -১, ০, বা +১।

-১ — ডান দিকের ডাল এক ধাপ লম্বা
০ — এই নোডটা একদম পারফেক্টলি ব্যালান্সড বা সোজা আছে
+১ — বাঁ দিকের ডাল এক ধাপ লম্বা

যখনি নতুন কিছু বসানো বা মোছার ফলে কোনো নোডের ব্যালান্স ফ্যাক্টর ±২ হয়ে যায়, তখন ট্রিটাকে রোটেশন (Rotations) বা চরকির মতো ঘুরিয়ে আবার সোজা বা ব্যালান্সড করতে হয়।

◈ Watch AVL rotations

← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন

দ্রষ্টব্য: এভিএল ট্রির উচ্চতা সর্বোচ্চ 1.44 × log₂(n) হওয়ার গ্যারান্টি দেয়। এর মানে হলো, যদি আপনার ট্রিতে ১০ লাখ (1 million) নোডও থাকে এবং সেটা সবচেয়ে খারাপ অবস্থায় থাকে, তবুও তার উচ্চতা বা লেভেল হবে বড়জোর ২৯-এর মতো। তাই এতে খোঁজার স্পিড সবসময়ই মারাত্মক ফাস্ট।

রোটেশন (Rotations) — ট্রির মেরামতের টুল

ট্রিকে না ভেঙে বা বাইনারি সার্চ ট্রির নিয়ম নষ্ট না করে, এর ছোট একটা অংশকে ঘুরিয়ে আবার ব্যালান্সড করার নামই হলো রোটেশন। মূলত চার ধরনের রোটেশন আছে, কিন্তু বেসিক রোটেশন মাত্র দুটো:

লেফট রোটেশন (Left Rotation)

যখন ডান দিকের ডাল খুব বেশি লম্বা হয়ে যায় (ব্যালান্স ফ্যাক্টর = -2), সাধারণত ডান-ডান (right-right) ইনসার্টের কারণে, তখন এটা ব্যবহার হয়:

pseudocode

A              B
   \            / \
    B    →    A   C
     \
      C

এখানে B হয়ে যায় নতুন রুট (root) বা মাথা, A হয়ে যায় B-এর বাঁ দিকের বাচ্চা, এবং B-এর পুরোনো বাঁ দিকের বাচ্চা (যদি থাকে) সে A-এর ডান দিকের বাচ্চা হয়ে যায়।

রাইট রোটেশন (Right Rotation)

এটা ঠিক আগেরটার উল্টো — যখন বাঁ দিকের ডাল খুব লম্বা হয়ে যায় (ব্যালান্স ফ্যাক্টর = +2), সাধারণত বাঁ-বাঁ (left-left) ইনসার্টের কারণে:

pseudocode

C          B
   /          / \
  B    →    A   C
 /
A

ডাবল রোটেশন (Double rotations)

কখনো কখনো বাঁ-ডান বা ডান-বাঁ (left-right / right-left) ইনসার্ট হলে ট্রিটা একটা "জিগজ্যাগ (zigzag)" বা আঁকাবাঁকা শেপ নেয়। তখন একটা রোটেশনে কাজ হয় না, দুটো লাগে:

লেফট-রাইট (Left-Right): প্রথমে বাচ্চার ওপর লেফট রোটেশন, তারপর রুটের ওপর রাইট রোটেশন।
রাইট-লেফট (Right-Left): প্রথমে বাচ্চার ওপর রাইট রোটেশন, তারপর রুটের ওপর লেফট রোটেশন।

কখন AVL আর কখন Red-Black ব্যবহার করবেন?

এভিএল ট্রি, রেড-ব্ল্যাক (Red-Black) ট্রির চেয়ে অনেক বেশি কড়াভাবে ব্যালান্সড থাকে। তাই এতে ডেটা খোঁজার (lookup) স্পিড সামান্য একটু বেশি পাওয়া যায় (কারণ ম্যাক্সিমাম রাস্তাটা একটু ছোট হয়)। কিন্তু কড়াকড়ি বেশি হওয়ায়, ইনসার্ট বা ডিলিট করার সময় একে বেশি রোটেশন করতে হয়, তাই ডেটা লেখায় (write) একটু বেশি সময় লাগে। আপনার অ্যাপ্লিকেশনে যদি লেখার চেয়ে পড়ার কাজ (read-heavy) বেশি হয়, তবে এভিএল বেস্ট। বেশিরভাগ প্রোগ্রামিং ভাষার স্ট্যান্ডার্ড লাইব্রেরিগুলো (যেমন Java-র TreeMap, C++ এর std::map) ডেটা লেখায় ভালো স্পিড পাওয়ার জন্য রেড-ব্ল্যাক ট্রি ব্যবহার করে।