ডেটা স্ট্রাকচরে রেড-ব্ল্যাক ট্রি

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

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

• রুট সবসময় ব্ল্যাক থাকবে।

• কোনো দুটি আসলনিয়ে রেড নোড থাকবে না।

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

রেড-ব্ল্যাক ট্রির উদাহরণ

লিফে NULL নোডসহ রেড-ব্ল্যাক ট্রি

AVL ট্রির সাথে তুলনা

AVL ট্রি রেড-ব্ল্যাক ট্রির চেয়ে বেশি ব্যালেন্সড। কিন্তু বড় ডিসঅ্যাডভান্টেজ হল, ইন্সারশন এবং ডিলিশনের সময় বেশি রোটেশন হয়। একাধিক ইন্সারশন এবং ডিলিশনের জন্য রেড-ব্ল্যাক ট্রি সাহায্যকারী।