২-৩ ট্রি ডেটা স্ট্রাকচারে একটি ধরনের ট্রি যাতে ট্রির প্রতিটি নোড হয় একটি ২ নোড
অথবা ৩ নোড। এটি অর্ডার ৩ সহ একটি বিশেষ ধরনের বি-ট্রি (B-Tree)।
ট্রিতে একটি ২ নোড হল যেটিতে একটি ডেটা অংশ এবং দুটি চাইল্ড নোড থাকে।
ট্রিতে একটি ৩ নোড হল যেটিতে দুটি ডেটা অংশ এবং তিনটি চাইল্ড নোড থাকে।
চিত্র:- একটি ২-৩ ট্রি
২-৩ ট্রির বৈশিষ্ট্য:-
- প্রতিটি ইন্টারনাল নোড হয় একটি ২ নোড অথবা একটি ৩ নোড।
- একটি ডেটা অংশ ধারণকারী একটি নোড হতে পারে একটি ২ নোড যাতে ঠিক দুটি চাইল্ড থাকে অথবা একটি লীফ নোড যাতে কোনো চাইল্ড নেই।
- দুটি ডেটা অংশ ধারণকারী একটি নোড শুধুমাত্র হতে পারে একটি ৩ নোড যাতে ঠিক তিনটি চাইল্ড থাকে।
- সকল লীফ নোড সবসময় একই লেভেলে থাকে।
- একটি ২-৩ ট্রি সবসময় একটি হাইট-ব্যালেন্সড ট্রি।
- ২-৩ ট্রিতে সার্চ অপারেশন দ্রুত এবং দক্ষ।
২ নোড:-
- ঠিক দুটি চাইল্ড।
- বাম চাইল্ড ছোট ওজন সহ।
- ডান চাইল্ড বড় ওজন সহ।
- হতে পারে কোনো চাইল্ড ছাড়া একটি লীফ নোড।
৩ নোড:-
- ঠিক তিনটি চাইল্ড।
- ২টি ডেটা মান।
- বাম চাইল্ড বাম ডেটা মানের চেয়ে ছোট ওজন সহ।
- মাঝপথের চাইল্ড দুটি ডেটা মানের মাঝপথে ওজন সহ।
- ডান চাইল্ড ডান ডেটা মানের চেয়ে বড় ওজন সহ।
- কখনো লীফ নোড হতে পারে না।
২-৩ ট্রিতে অপারেশন:-
১. ২-৩ ট্রিতে সার্চিং
- বাইনারি সার্চ ট্রিতে সার্চ অপারেশনের মতোই কারণ ডেটা সর্টেড থাকে।
- ২-৩ ট্রিতে X সার্চ করতে।
- যদি ট্রি খালি হয় → False রিটার্ন করুন
- যদি রুট নোডে পৌঁছান তবে False রিটার্ন করুন (নहीं পাওয়া গেল)
- যদি X বাম ডেটা অংশের চেয়ে কম হয়, তবে বাম সাবট্রি সার্চ করুন
- যদি X বাম ডেটা থেকে বড় এবং ডান ডেটা থেকে বড় হয়, মাঝপথের সাবট্রি সার্চ করুন।
- যদি X ডান ডেটা অংশের চেয়ে বড় হয়, তবে ডান সাবট্রি সার্চ করুন।
২. ২-৩ ট্রিতে একটি নোড ইনসার্ট করা
- ২-৩ ট্রিতে X ইনসার্ট করতে।
- যদি ট্রি খালি হয় → X কে রুট হিসেবে যোগ করুন।
- X-এর সঠিক পজিশন সার্চ করুন এবং সেটি লীফ নোড হিসেবে যোগ করুন।
- যদি একটি লীফ নোড থাকে যাতে একটি ডেটা অংশ আছে, X যোগ করুন এবং লীফ নোডটি ২-নোড হয়ে যায়।
- যদি লীফ নোডে দুটি ডেটা অংশ থাকে, X যোগ করুন। অস্থায়ী ৩-নোডগুলো বিভক্ত করুন এবং সর্টিং অর্ডার অনুযায়ী ডেটা প্যারেন্ট নোডে সরান।
২-৩ ট্রি তৈরি করুন এবং নোড যোগ করুন ক্রমে → 10, 5, 8, 15, 23, 21
৩. ২-৩ ট্রিতে একটি নোড ডিলিশন
- ২-৩ ট্রিতে X ডিলিট করতে।
- যদি ট্রি খালি হয় false রিটার্ন করুন।
- X-এর পজিশন সার্চ করুন এবং সেটি ডিলিট করুন, তারপর ট্রি অ্যাডজাস্ট করুন।
- যদি X ৩ নোডের অংশ হয় তবে X ডিলিট করুন এবং বাম মান এবং মাঝপথের মান অ্যাডজাস্ট করুন। প্রয়োজনে নোডের ancestor-এর বাম এবং মাঝপথের মানও অ্যাডজাস্ট করুন।
- যদি X ২ নোডের অংশ হয় তবে রিকার্সিভভাবে ট্রি অ্যাডজাস্ট এবং বিভক্ত করুন সর্টেড অর্ডারে নোড সাজিয়ে।
