Table of Contents
ভারসাম্যযুক্ত বাইনারি সন্ধান গাছ হচ্ছে উপাত্ত গঠন এবং কার্যকর কাজের জন্য তথ্য, যেমন অনুসন্ধান, সন্নিবেশ এবং মুছে ফেলা। দুটি সাধারণ ধরন এভএল গাছ এবং রেড ব্ল্যাক গাছ, যা বিভিন্ন অনন্য নীতি দিয়ে তৈরি করা হয়।
এভল ট্রি
এভিএল গাছ স্বত:শৈঙ্গিক সার্চ গাছের মধ্যে রয়েছে, যেখানে বাম ও ডানের সারির যে কোন নোডের মাঝখানে পার্থক্য রয়েছে। এই কঠোর ভারসাম্য দ্রুত অনুসন্ধানের সময় নিশ্চিত করে কিন্তু তা প্রবেশের সময় দ্রুত গতি বজায় রাখে।
এই আবর্তনের অন্তর্ভুক্ত একক ও দ্বৈত আবর্তন, যা উচ্চতাকে নিয়ন্ত্রণে রাখতে সাহায্য করে ।
রেড-ব্লাড ট্রি
লাল-কালো গাছ হচ্ছে এমন একটি ধরনের আত্ম-বিশ্লেষণী গাছ যা প্রতিটি নোডের জন্য রঙ (রেড বা কালো) বরাদ্দ করে । এই নিয়মের নিয়ম প্রায় ভারসাম্য বজায় রাখে, যেখানে মূল থেকে কোন অংশ নেই যতক্ষণ না অন্য যে কোন সময় ফল পাওয়া যাবে।
কি-র বৈশিষ্ট্য
- প্রত্যেকটা নোড হয় লাল বা কালো।
- আসলটা সবসময় কালো।
- লাল নোডের কোনো লাল শিশুরই কোন অধিকার নেই।
- একটি নোড থেকে প্রত্যেক রাস্তা তার বংশধরের পাতা থেকে একই নাম্বার আছে.
এই বৈশিষ্ট্যের ফলে লাল কালো গাছকে ঢোকানোর এবং ভারসাম্য বজায় রাখার সময় খাপ খাওয়ানোর কাজে লাগিয়ে তা পরিষ্কার করা যায়।
AVL ও রেড-ব্লাড ট্রির তুলনা
এভিএল এবং রেড ব্ল্যাক গাছ উভয়ে গাছকে সঠিক কাজের ভারসাম্য বজায় রাখতে চেষ্টা করে।