এই বিভাগে আমরা ব্যাখ্যা করি কিভাবে (2,4)-বৃক্ষগুলি স্তরের লিঙ্কগুলির প্রবর্তনের মাধ্যমে দক্ষ আঙুল অনুসন্ধানগুলিকে সমর্থন করতে পারে। এই বিভাগে ব্যাখ্যা করা ধারণাগুলি b ≥ 2a-এর জন্য (a, b)-বৃক্ষ নির্দেশিত উচ্চতা-ভারসাম্যযুক্ত গাছগুলির আরও সাধারণ শ্রেণিতে প্রয়োগ করে৷
A (2,4)-বৃক্ষকে একটি উচ্চতা-ভারসাম্যপূর্ণ অনুসন্ধান গাছ হিসাবে সংজ্ঞায়িত করা হয়েছে যেখানে সমস্ত পাতার গভীরতা একই এবং সমস্ত অভ্যন্তরীণ নোডের ডিগ্রি দুই, তিন বা চারটি। উপাদানগুলি পাতায় সংরক্ষণ করা হয়, এবং অভ্যন্তরীণ নোডগুলি কেবল অনুসন্ধান কীগুলিকে গাইড করার জন্য সংরক্ষণ করে৷ যেহেতু প্রতিটি অভ্যন্তরীণ নোডের কমপক্ষে দুটি ডিগ্রি রয়েছে, এটি অনুসরণ করে যে একটি (2,4)-বৃক্ষের উচ্চতা O(log n) এবং O(log n) সময়ে অনুসন্ধান সমর্থন করে। (2,4)-বৃক্ষের একটি গুরুত্বপূর্ণ বৈশিষ্ট্য হল যে একটি আঙুল দ্বারা প্রদত্ত সন্নিবেশ এবং মুছে ফেলার জন্য অমর্টাইজড O(1) সময় লাগে (এই সম্পত্তিটি (2, 3)-বৃক্ষ দ্বারা ভাগ করা হয় না, যেখানে m সন্নিবেশের ক্রম বিদ্যমান থাকে এবং মুছে ফেলার জন্য Θ(m log m) সময় প্রয়োজন)। অধিকন্তু একটি (2,4)-m পাতা সহ গাছটিকে অমর্টাইজড O(লগ মিন(m1, m2)) সময়ে m1 এবং m2 আকারের দুটি গাছে বিভক্ত করা যেতে পারে। একইভাবে দুটি (2,4)-m1 এবং m2 আকারের গাছকে অমর্টাইজড O(লগ মিনিট(m1, m2)) সময়ে যুক্ত করা যেতে পারে।
আঙ্গুলের অনুসন্ধানগুলিকে সমর্থন করার জন্য, (2,4)-বৃক্ষগুলিকে স্তরের লিঙ্কগুলির সাথে বর্ধিত করা হয়, যেমন সমান গভীরতার সাথে সমস্ত নোডগুলি একটি ডাবল লিঙ্কযুক্ত তালিকায় একসাথে লিঙ্ক করা হয়৷ নিম্নোক্ত চিত্রটি লেভেল লিঙ্ক সহ বর্ধিত একটি (2,4)-বৃক্ষ প্রদর্শন করে। মনে রাখবেন সমস্ত প্রান্ত দ্বি-নির্দেশিত লিঙ্কগুলিকে প্রতিনিধিত্ব করে। অতিরিক্ত স্তরের লিঙ্কগুলি (2,4)-বৃক্ষের সন্নিবেশ, মুছে ফেলা, বিভাজন এবং যোগদানের সময় সংরক্ষণের জন্য সহজবোধ্য৷
X থেকে Y পর্যন্ত আঙ্গুলের অনুসন্ধান সম্পন্ন করার জন্য আমরা প্রথমে পরীক্ষা করি যে Y X-এর বাম দিকে নাকি ডানদিকে। সাধারণতা না হারিয়ে ধরে নিন যে Y হল X-এর ডানদিকে। তারপর পরীক্ষা করার সময় আমরা X থেকে মূলের দিকে যাওয়ার পথ পরিদর্শন করি। নোড V এর পাথ এবং তাদের ডান প্রতিবেশীদের যতক্ষণ না এটি প্রতিষ্ঠিত হয় যে V বা V এর ডান প্রতিবেশীর শিকড়যুক্ত সাবট্রির মধ্যে Y রয়েছে। ঊর্ধ্বমুখী অনুসন্ধানটি তখন বন্ধ করা হয় এবং y-এর জন্য সর্বাধিক দুটি নীচের দিকে অনুসন্ধান যথাক্রমে V এবং/অথবা V এর ডান প্রতিবেশীতে শুরু হয়। চিত্র 1-এ j থেকে t পর্যন্ত আঙুল অনুসন্ধানের সময় অনুসরণ করা পয়েন্টারগুলিকে মোটা রেখা দ্বারা চিহ্নিত করা হয়েছে৷
O(লগ d) অনুসন্ধানের সময়টি পর্যবেক্ষণ থেকে অনুসরণ করে যে আমরা যদি উপরের দিকে অনুসন্ধানটি V নোডের অভিভাবকের দিকে অগ্রসর করি তাহলে Y হল V′-এর ডান প্রতিবেশীর বাঁদিকের উপবৃক্ষের ডানদিকে, অর্থাৎ d হল কমপক্ষে সূচকীয় উচ্চতা এ পর্যন্ত পৌঁছেছে।
চিত্র 1-এ আমরা "l n" লেবেলযুক্ত অভ্যন্তরীণ নোড থেকে "h" লেবেলযুক্ত নোডে অগ্রসর হলাম কারণ "s" থেকে আমরা জানি যে Y নোড "q r" এ সাবট্রিরুর্টের ডানদিকে রয়েছে৷
লেভেল লিঙ্কড (2,4)-বৃক্ষের নির্মাণ সরাসরি লেভেল লিঙ্কড (a, b)-বৃক্ষের সাথে সাধারণীকরণ করে যা বহিরাগত মেমরিতে প্রয়োগ করা যেতে পারে। a =2b এবং b নির্বাচন করে যাতে একটি অভ্যন্তরীণ নোড বাহ্যিক মেমরিতে একটি ব্লকে ফিট করে, আমরা O(1) মেমরি স্থানান্তরে সন্নিবেশ এবং মুছে ফেলার সমর্থনকারী বাহ্যিক মেমরি আঙুল অনুসন্ধান ট্রি অর্জন করি এবং O(logb n) মেমরি স্থানান্তর সহ আঙুল অনুসন্ধান করি .
