একটি সাধারণ BST একটি লিঙ্কড তালিকায় অবনত হতে পারে (O(n) অপারেশন) যদি কীগুলি সাজানো ক্রমে আসে। স্ব-সুষম BST — যেমন AVL এবং লাল-কালো গাছ — স্বয়ংক্রিয়ভাবে ঢোকানো/মুছে ফেলার পরে নোডগুলিকে ঘোরায় উচ্চতা ~log n রাখতে, O(log n) অপারেশন নিশ্চিত করে।
একটি সাধারণ BST একটি লিঙ্কড তালিকায় অবনত হতে পারে (O(n) অপারেশন) যদি কীগুলি সাজানো ক্রমে আসে। স্ব-সুষম BST — যেমন AVL এবং লাল-কালো গাছ — স্বয়ংক্রিয়ভাবে ঢোকানো/মুছে ফেলার পরে নোডগুলিকে ঘোরায় উচ্চতা ~log n রাখতে, O(log n) অপারেশন নিশ্চিত করে।
Unbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| AVL গাছ | লাল-কালো গাছ | |
|---|---|---|
| ভারসাম্য কঠোরতা | কঠোর (উচ্চতা-সুষম) | আরও নমনীয় |
| অনুসন্ধান | দ্রুততর (ছোট) | সামান্য ধীর |
| ঢোকানো/মুছে ফেলা | আরও ঘূর্ণন | কম ঘূর্ণন |
| সেরা জন্য | পড়া-ভারী কর্মভার | লেখা-ভারী কর্মভার |
| অপারেশন | সময় |
|---|---|
| অনুসন্ধান | O(log n) |
| ঢোকানো | O(log n) |
| মুছে ফেলা | O(log n) |
উভয়ই ঘূর্ণনের মাধ্যমে ভারসাম্য বজায় রাখে — স্থানীয় O(1) পুনর্গঠন যা BST ক্রম সংরক্ষণ করে ঐচ্ছিক উচ্চতা হ্রাস করে।
সুষম গাছগুলি মান লাইব্রেরিতে অর্ডার করা মানচিত্র এবং সেট সমর্থন করে (যেমন Java TreeMap, C++ std::map লাল-কালো গাছ ব্যবহার করে), সাজানো পুনরাবৃত্তি এবং গ্যারান্টিযুক্ত লগারিদমিক অপারেশন প্রদান করে।
তারা উত্তর যখন আপনার BST-এর অর্ডারকরণ এবং প্রতিকূল ইনপুটের বিরুদ্ধে কঠোর কর্মক্ষমতা গ্যারান্টি প্রয়োজন।
বিস্তারিত উত্তরসহ IT ইন্টারভিউ প্রশ্নের একটি লাইব্রেরি — জুনিয়র থেকে সিনিয়র পর্যন্ত।
দান করুন