ডেটা স্ট্রাকচারে ভারসাম্যপূর্ণ বাইনারি অনুসন্ধান গাছ

এখানে আমরা দেখব সুষম বাইনারি সার্চ ট্রি কি। বাইনারি সার্চ ট্রি (বিএসটি) হল বাইনারি ট্রি, যার বাঁদিকের শিশুতে কম উপাদান থাকে এবং ডান শিশুতে বেশি উপাদান থাকে।

BST-এ উপাদান অনুসন্ধানের গড় সময় জটিলতা হল O(log n)। এটি বাইনারি অনুসন্ধান গাছের উচ্চতার উপর নির্ভর করে। বাইনারি অনুসন্ধান গাছের বৈশিষ্ট্য বজায় রাখতে, কখনও কখনও গাছটি তির্যক হয়ে যায়। তাই তির্যক গাছটি দেখতে এরকম হবে −

এটি আসলে একটি গাছ, কিন্তু এটি একটি লিঙ্ক তালিকা মত দেখাচ্ছে. এই ধরনের গাছের জন্য, অনুসন্ধানের সময় হবে O(n)। এটি বাইনারি গাছের জন্য কার্যকর নয়।

এই সমস্যাগুলো থেকে উত্তরণের জন্য আমরা এমন একটি গাছ তৈরি করতে পারি যার উচ্চতা সুষম। তাই গাছ মারা হবে না। জোর করে, আমরা তারপর ভারসাম্য করা হবে. সুতরাং একটি নোডের প্রতিটি পাশে একটি সাবট্রি থাকবে যার উচ্চতা প্রায় একই হবে

ভারসাম্য বজায় রাখার জন্য বিভিন্ন কৌশল রয়েছে। তাদের মধ্যে কিছু হল -

• AVL গাছ

• লাল-কালো গাছ

উপরের উদাহরণের উচ্চতা ভারসাম্যপূর্ণ ফর্মটি এইরকম হবে −