পরিচয়
২-৩ ট্রি (2-3 Tree) হলো একটি ট্রি ডেটা স্ট্রাকচার যেখানে প্রতিটি ইন্টারনাল নোডের হয় ২টি চাইল্ড (২-নোড) এবং ১টি ডেটা এলিমেন্ট, অথবা ৩টি চাইল্ড (৩-নোড) এবং ২টি ডেটা এলিমেন্ট থাকে।
সংজ্ঞা
- ২-নোড: ১টি ডেটা এলিমেন্ট এবং ২টি চাইল্ড।
- ৩-নোড: ২টি ডেটা এলিমেন্ট এবং ৩টি চাইল্ড।
- T হলো ২-৩ ট্রি যদি নিচের শর্তগুলো মেনে চলে:
- T খালি।
- T হলো ২-নোড ডেটা a সহ। লেফট চাইল্ড L, রাইট চাইল্ড R। L ও R সমান হাইটের নন-এমপ্টি ২-৩ ট্রি। a, L-র সব এলিমেন্ট থেকে বড় এবং R-র সব এলিমেন্ট থেকে ছোট বা সমান।
- T হলো ৩-নোড ডেটা a, b সহ (a < b)। লেফট L, মিডল M, রাইট R। L, M, R সমান হাইটের নন-এমপ্টি ২-৩ ট্রি। a, L-র সব এলিমেন্ট থেকে বড় এবং M-র সব এলিমেন্ট থেকে ছোট বা সমান। b, M-র সব এলিমেন্ট থেকে বড় এবং R-র সব এলিমেন্ট থেকে ছোট বা সমান।
বৈশিষ্ট্য
- প্রতিটি ইন্টারনাল নোড ২-নোড বা ৩-নোড।
- সকল লীফ একই লেভেলে।
- সকল ডেটা সো্র্টেড অর্ডারে থাকে।
অপারেশন
সার্চিং (Searching)
বাইনারি সার্চ ট্রি-র মতোই। ডেটা এলিমেন্টগুলো অর্ডার্ড থাকায় সার্চ ফাংশন সঠিক সাবট্রি-তে দিয়ে নির্দিষ্ট নোডে পৌঁছায়।
- T খালি হলে d নেই।
- r = T-এর রুট।
- r লীফ হলে: d r-তে নেইলে T-তেও নেই। থাকে তবে পাওয়া গেল।
- r ২-নোড হলে (লেফট L, রাইট R, ডেটা e):
- d == e হলে পাওয়া গেল।
- d < e হলে T = L সেট করে ধাপ ২-এ ফিরুন।
- d > e হলে T = R সেট করে ধাপ ২-এ ফিরুন।
- r ৩-নোড হলে (লেফট L, মিডল M, রাইট R, ডেটা a < b):
- d == a বা b হলে পাওয়া গেল।
- d < a হলে T = L।
- a < d < b হলে T = M।
- d > b হলে T = R।
ইনসার্শন (Insertion)
কি-এর সঠিক লোকেশন খুঁজে সেটি অ্যাড করা হয়। নোড ৪-নোড হলে দুটি ২-নোডে ভাগ করে মিডল কি প্যারেন্টে পাঠানো হয়। প্যারেন্টও ৪-নোড হলে সেটিও ভাগ হয়, রুট পর্যন্ত প্রোপাগেট হতে পারে। এই প্রক্রিয়া O(log n) টাইম নেয় কারণ ট্রি পারফেক্টলি बैলেন্সড।
নিচের ডায়াগ্রামে ৩টি সম্ভাব্য কেস দেখানো হয়েছে।
