ডেটা স্ট্রাকচারে লাল-কালো গাছ

এই বিভাগে আমরা দেখব লাল-কালো গাছ কী। লাল-কালো গাছ হল স্ব-ভারসাম্য রক্ষাকারী বাইনারি অনুসন্ধান গাছ। প্রতিটি নোডের জন্য কিছু শর্ত আছে। এগুলো নিচের মত -

• প্রতিটি নোডের রঙ আছে। যেটি হয় লাল বা কালো

• মূল সবসময় কালো থাকবে

• কোন দুটি সংলগ্ন লাল নোড থাকবে না

• একটি নোড (রুট সহ) থেকে তার যে কোনো ডিসেন্ডেন্ট NULL নোড পর্যন্ত প্রতিটি পাথে একই সংখ্যক কালো নোড রয়েছে।

লাল-কালো গাছের উদাহরণ

পাতে নাল নোড সহ লাল-কালো গাছ

AVL গাছের সাথে তুলনা

AVL গাছ লাল-কালো গাছের চেয়ে বেশি ভারসাম্যপূর্ণ। কিন্তু প্রধান অসুবিধা হল, সন্নিবেশ এবং মুছে ফেলার সময় আরও ঘূর্ণন হবে। একাধিক সন্নিবেশ এবং মুছে ফেলার জন্য, লাল-কালো গাছ সহায়ক হবে।