এখানে আমরা দেখব ব্যালেন্সড বাইনারি সার্চ ট্রি কী। বাইনারি সার্চ ট্রি (BST) হল বাইনারি ট্রি যেগুলোর বাম চাইল্ডে ছোট উপাদান এবং ডান চাইল্ডে বড় উপাদান থাকে।
BST-এ উপাদান সার্চ করার গড় সময় জটিলতা O(log n)। এটি বাইনারি সার্চ ট্রির উচ্চতায় নির্ভর করে। বাইনারি সার্চ ট্রির বৈশিষ্ট্য বজায় রাখতে কখনও কখনও ট্রি স্কিউড হয়ে যায়। তাহলে স্কিউড ট্রি নিচের মতো দেখাবে:
এটি আসলে একটি ট্রি, কিন্তু এটি লিঙ্কড লিস্টের মতো দেখাচ্ছে। এই ধরনের ট্রির জন্য সার্চিং টাইম হবে O(n)। যা বাইনারি ট্রির জন্য কার্যকর নয়।
এই সমস্যা সমাধানের জন্য আমরা একটি ট্রি তৈরি করতে পারি যা হাইট-ব্যালেন্সড। তাহলে ট্রি স্কিউড হবে না। বাধ্যতামূলকভাবে আমরা সেগুলো ব্যালেন্সড করব। তাই একটি নোডের প্রতিটি পাশে সাব-ট্রি থাকবে যাদের হাইট প্রায় একই হবে।
ব্যালেন্সিংয়ের বিভিন্ন কৌশল রয়েছে। 그중 কিছু:
AVL ট্রি
রেড-ব্ল্যাক ট্রি
উপরোক্ত উদাহরণের হাইট-ব্যালেন্সড রূপ নিচের মতো দেখাবে:
