একটি 2-3 গাছ হল ডেটা স্ট্রাকচারের এক ধরণের গাছ যেখানে গাছের প্রতিটি নোড হয় 2 নোড হয়
বা 3 নোড। এটি একটি বিশেষ ধরনের বি-ট্রি অর্ডার 3 সহ।
গাছের মধ্যে একটি 2 নোড হল একটি যার একটি ডেটা অংশ এবং দুটি চাইল্ড নোড রয়েছে৷
গাছের মধ্যে একটি 3 নোড হল একটি যার দুটি ডেটা অংশ এবং তিনটি চাইল্ড নোড রয়েছে৷
চিত্র:- একটি 2-3টি গাছ
একটি 2-3টি গাছের বৈশিষ্ট্য:-
-
প্রতিটি অভ্যন্তরীণ নোড হয় 2 নোড বা একটি 3 নোড৷
-
একটি ডাটা অংশ সম্বলিত একটি নোড ঠিক 2টি শিশু সহ একটি 2টি নোড হতে পারে বা শিশুবিহীন একটি লিফ নোড হতে পারে৷
-
দুটি ডেটা অংশ সমন্বিত একটি নোড ঠিক 3টি শিশু সহ একটি 3টি নোড হতে পারে৷
-
সমস্ত লিফ নোড সবসময় একই স্তরে থাকে৷
-
একটি 2-3 গাছ সবসময় একটি উচ্চতা ভারসাম্যপূর্ণ গাছ।
-
2-3টি গাছে অনুসন্ধান কার্যক্রম দ্রুত এবং দক্ষ।
2 নোড:-
-
ঠিক দুটি শিশু।
-
বাম শিশুর ওজন কম।
-
বেশি ওজনের অধিকারী শিশু।
-
কোন সন্তান ছাড়াই একটি লিফ নোড হতে পারে৷
3 নোড:-
-
ঠিক তিন সন্তান।
-
2 ডেটা মান।
-
বাম শিশুর ওজন বাম ডেটা মানের থেকে কম।
-
উভয় ডেটা মানের মধ্যে ওজন সহ মধ্য শিশু।
-
ডান শিশুর ওজন সঠিক ডেটা মানের চেয়ে বেশি।
-
কখনই লিফ নোড হতে পারে না।
একটি 2-3টি গাছে অপারেশন:-
1. একটি 2-3 গাছে অনুসন্ধান করা হচ্ছে
-
একটি বাইনারি সার্চ ট্রিতে অনুসন্ধান অপারেশনের অনুরূপ যেমন ডেটা সাজানো হয়।
-
একটি 2-3 গাছে X অনুসন্ধান করতে।
-
যদি গাছ খালি থাকে → রিটার্ন ফলস
-
যদি আমরা রুট নোডে পৌঁছাই তাহলে False রিটার্ন করুন (পাওয়া যায়নি)
-
যদি X বাম ডেটা অংশ থেকে কম হয়, তাহলে বাম সাবট্রি অনুসন্ধান করুন
-
যদি X বাম ডেটার চেয়ে বেশি এবং ডান ডেটার চেয়ে বেশি হয়, তাহলে মধ্যবর্তী সাবট্রি অনুসন্ধান করুন৷
-
যদি X সঠিক ডেটা অংশের চেয়ে বড় হয়, তাহলে ডান সাবট্রি অনুসন্ধান করুন।
2. একটি 2-3 গাছে একটি নোড সন্নিবেশ করান
-
একটি 2-3 গাছে X সন্নিবেশ করান।
-
যদি গাছটি খালি থাকে → মূল হিসাবে X যোগ করুন।
-
X এর সঠিক অবস্থানের জন্য অনুসন্ধান করুন এবং এটিকে একটি লিফ নোড হিসাবে যুক্ত করুন৷
-
যদি একটি ডেটা পার্ট সহ একটি লিফ নোড থাকে, তাহলে এর সাথে X যোগ করুন এবং লিফ নোড 2 - নোড হয়ে যাবে৷
-
যদি লিফ নোডে দুটি ডেটা অংশ থাকে, তাহলে X যোগ করুন। অস্থায়ী 3-নোডগুলিকে বিভক্ত করুন এবং সাজানোর ক্রম অনুসারে প্যারেন্ট নোডে ডেটা স্থানান্তর করুন।
2-3টি গাছ তৈরি করুন এবং ক্রমানুসারে নোড যোগ করুন → 10, 5, 8, 15, 23, 21
3. একটি 2-3 গাছে একটি নোড মুছে ফেলা
-
একটি 2-3 গাছে X মুছে ফেলার জন্য।
-
যদি গাছটি খালি থাকে তবে মিথ্যা ফেরত দিন।
-
X-এর অবস্থানের জন্য অনুসন্ধান করুন এবং এটি মুছুন, তারপর ট্রি সামঞ্জস্য করুন।
-
যদি X 3 নোডের অংশ হয় তবে X মুছে ফেলুন এবং বাম মান এবং মধ্যম মান সামঞ্জস্য করুন। প্রয়োজনে নোডের পূর্বপুরুষের বাম এবং মধ্যম মান সমন্বয় করুন।
-
যদি X 2 নোডের অংশ হয়, তাহলে সাজানো ক্রমে নোডগুলি সাজিয়ে পুনরাবৃত্ত পদ্ধতিতে ট্রি সামঞ্জস্য করুন এবং বিভক্ত করুন৷
