Tango tree
ট্যাঙ্গো গাছ হল এক ধরনের বাইনারি সার্চ ট্রি যা 2004 সালে এরিক ডি. ডেমাইন, ডিওন হারমন, জন আইয়াকো এবং মিহাই প্যাট্রাস্কু দ্বারা প্রস্তাবিত হয়েছিল। এটি বুয়েনোস আইরেসের নামে নামকরণ করা হয়েছে, যার মধ্যে ট্যাঙ্গো প্রতীকী। এটি একটি অনলাইন বাইনারি সার্চ ট্রি যা অফলাইন অপ্টিমাল বাইনারি সার্চ ট্রি-র তুলনায় প্রতিযোগিতামূলক অনুপাত অর্জন করে, শুধুমাত্র প্রতি নোডে অতিরিক্ত বিট মেমরি ব্যবহার করে। এটি পূর্ববর্তী সর্বাধিক পরিচিত প্রতিযোগিতামূলক অনুপাতের তুলনায় উন্নত হয়েছে, যা ছিল। কাঠামো ট্যাঙ্গো গাছগুলি একটি বাইনারি অনুসন্ধান গাছকে পছন্দসই পথের একটি সেটে বিভক্ত করে কাজ করে, যা নিজেই সহায়ক গাছগুলিতে সংরক্ষণ করা হয় (তাই ট্যাঙ্গো গাছকে গাছের গাছ হিসাবে উপস্থাপন করা হয়)। একটি ট্যাঙ্গো ট্রি তৈরি করতে, আমরা রেফারেন্স ট্রি নামে একটি সম্পূর্ণ বাইনারি সার্চ ট্রি অনুকরণ করি, যা কেবল সমস্ত উপাদান সম্বলিত একটি ঐতিহ্যবাহী বাইনারি সার্চ ট্রি। এই গাছটি প্রকৃত বাস্তবায়নে কখনই দেখা যায় না, তবে এটি একটি ট্যাঙ্গো গাছের নিম্নলিখিত টুকরোগুলির পিছনে ধারণাগত ভিত্তি। বিশেষ করে, রেফারেন্স গাছের উচ্চতা হল। এটি দীর্ঘতম পথের দৈর্ঘ্যের সমান এবং তাই বৃহত্তম সহায়ক গাছের আকারের সমান। সহায়ক গাছগুলিকে যুক্তিসঙ্গতভাবে ভারসাম্যপূর্ণ রেখে, সহায়ক গাছের উচ্চতা সীমাবদ্ধ করা যেতে পারে এটি অ্যালগরিদমের কার্যকারিতা গ্যারান্টির উৎস। পছন্দের পথ প্রথমে, আমরা প্রতিটি নোডের জন্য তার পছন্দের চাইল্ডকে সংজ্ঞায়িত করি, যা অনানুষ্ঠানিকভাবে একটি ঐতিহ্যবাহী বাইনারি সার্চ ট্রি অনুসন্ধানের দ্বারা সাম্প্রতিকতম পরিদর্শন করা চাইল্ড। আরও আনুষ্ঠানিকভাবে, একটি উপ-বৃক্ষ টি বিবেচনা করুন, যার শিকড় পি-তে রয়েছে, যেখানে শিশু এল (বাম) এবং আর (ডান) রয়েছে। আমরা r কে p-এর পছন্দের চাইল্ড হিসাবে সেট করি যদি T-তে সাম্প্রতিকতম অ্যাক্সেস করা নোডটি r-এ মূলযুক্ত সাবট্রিতে থাকে এবং অন্যথায় l পছন্দের চাইল্ড হিসাবে থাকে। লক্ষ্য করুন যে, যদি টি-এর সাম্প্রতিকতম অ্যাক্সেস করা নোডটি নিজেই পি হয়, তবে সংজ্ঞা অনুসারে এল হল পছন্দের চাইল্ড। একটি পছন্দের পথ মূল থেকে শুরু করে এবং পছন্দের শিশুদের অনুসরণ করে একটি পাতার নোডে না পৌঁছানো পর্যন্ত সংজ্ঞায়িত করা হয়। এই পথের নোডগুলি সরিয়ে ফেললে গাছের অবশিষ্টাংশকে বেশ কয়েকটি সাবট্রিতে বিভক্ত করা হয় এবং আমরা প্রতিটি সাবট্রিতে পুনর্ব্যবহার করি (এর মূল থেকে একটি পছন্দের পথ তৈরি করে, যা সাবট্রিকে আরও সাবট্রিতে বিভক্ত করে)। সহায়ক গাছ একটি পছন্দের পথের প্রতিনিধিত্ব করার জন্য, আমরা এর নোডগুলি একটি ভারসাম্যপূর্ণ বাইনারি অনুসন্ধান গাছে, বিশেষত একটি লাল-কালো গাছে সংরক্ষণ করি। পছন্দের পথ পি-তে প্রতিটি পাতাবিহীন নোডের জন্য, এটির একটি পছন্দবিহীন চাইল্ড সি রয়েছে, যা একটি নতুন সহায়ক গাছের মূল। আমরা এই অন্যান্য সহায়ক গাছের মূল (সি) পি-তে এন-এর সাথে সংযুক্ত করি, এইভাবে সহায়ক গাছগুলিকে একসাথে সংযুক্ত করি। আমরা প্রতিটি নোডে সেই নোডের নীচে সাবট্রির নোডগুলির ন্যূনতম এবং সর্বাধিক গভীরতা (রেফারেন্স ট্রি-র গভীরতা, অর্থাৎ) সংরক্ষণ করে অক্জিলিয়ারি ট্রি বৃদ্ধি করি। অ্যালগরিদম অনুসন্ধান ট্যাঙ্গো ট্রি-তে একটি উপাদান অনুসন্ধান করতে, আমরা কেবল রেফারেন্স ট্রি অনুসন্ধানের অনুকরণ করি। আমরা মূলের সাথে সংযুক্ত পছন্দের পথটি অনুসন্ধান করে শুরু করি, যা সেই পছন্দের পথের সাথে সম্পর্কিত সহায়ক গাছটি অনুসন্ধান করে অনুকরণ করা হয়। যদি সহায়ক গাছে কাঙ্ক্ষিত উপাদান না থাকে, তবে অনুসন্ধানটি কাঙ্ক্ষিত উপাদান (অন্য পছন্দের পথের শুরু) সহ সাবট্রির মূলের মূলের উপর শেষ হয়, তাই আমরা কেবল সেই পছন্দের পথের জন্য সহায়ক গাছ অনুসন্ধান করে এগিয়ে যাই, ইত্যাদি। হালনাগাদ করা ট্যাঙ্গো গাছের কাঠামো বজায় রাখার জন্য (সহায়ক গাছগুলি পছন্দের পথের সাথে সামঞ্জস্যপূর্ণ), অনুসন্ধানের ফলে যখনই পছন্দের শিশুরা পরিবর্তিত হয় তখন আমাদের অবশ্যই কিছু হালনাগাদ করার কাজ করতে হবে। যখন কোনও পছন্দের শিশু পরিবর্তিত হয়, তখন পছন্দের পথের উপরের অংশটি নীচের অংশ থেকে বিচ্ছিন্ন হয়ে যায় (যা তার নিজের পছন্দের পথ হয়ে যায়) এবং অন্য পছন্দের পথে পুনরায় সংযুক্ত হয় (যা নতুন নীচের অংশে পরিণত হয়)। এটি দক্ষতার সাথে করার জন্য, আমরা আমাদের সহায়ক গাছগুলিতে কাটা এবং যোগদানের ক্রিয়াকলাপগুলি সংজ্ঞায়িত করব। আমাদের জয়েন অপারেশনে যোগ দিন দুটি অক্জিলিয়ারি ট্রি একত্রিত হবে যতক্ষণ না তাদের সম্পত্তি থাকে যে একটির উপরের নোড (রেফারেন্স ট্রি-তে) অন্যটির নীচের নোডের একটি চাইল্ড (মূলত, যে সংশ্লিষ্ট পছন্দসই পথগুলি একত্রিত করা যেতে পারে)। এটি লাল-কালো গাছের সংহত ক্রিয়াকলাপের উপর ভিত্তি করে কাজ করবে, যা দুটি গাছকে একত্রিত করে যতক্ষণ না তাদের সম্পত্তি থাকে যে একটির সমস্ত উপাদান অন্যটির সমস্ত উপাদানের চেয়ে কম এবং বিভক্ত হয়, যা বিপরীত কাজ করে। রেফারেন্স ট্রি-তে, লক্ষ্য করুন যে উপরের পথে দুটি নোড রয়েছে যাতে একটি নোড নীচের পথে থাকে যদি এবং শুধুমাত্র যদি তার কী-মান তাদের মধ্যে থাকে। এখন, উপরের পথের নীচের পথে যোগ দেওয়ার জন্য, আমরা কেবল সেই দুটি নোডের মধ্যে উপরের পথটি বিভক্ত করি, তারপরে নীচের পথের সহায়ক গাছের উভয় পাশে দুটি ফলস্বরূপ সহায়ক গাছগুলিকে একত্রিত করি এবং আমাদের চূড়ান্ত, সংযুক্ত সহায়ক গাছ রয়েছে। আমাদের কাট অপারেশন একটি পছন্দের পথকে একটি প্রদত্ত নোডে দুটি অংশে বিভক্ত করবে, একটি উপরের অংশ এবং একটি নীচের অংশ। আরও আনুষ্ঠানিকভাবে, এটি একটি সহায়ক গাছকে দুটি সহায়ক গাছে বিভক্ত করবে, যাতে একটিতে রেফারেন্স গাছের একটি নির্দিষ্ট গভীরতায় বা তার উপরে সমস্ত নোড থাকে এবং অন্যটিতে সেই গভীরতার নীচে সমস্ত নোড থাকে। জয়েনের মতো, লক্ষ্য করুন যে উপরের অংশে দুটি নোড রয়েছে যা নীচের অংশটিকে বন্ধনী দেয়। সুতরাং, আমরা কেবল এই দুটি নোডের প্রত্যেকটিতে বিভক্ত হয়ে পথটিকে তিনটি অংশে বিভক্ত করতে পারি, তারপরে দুটি বাইরের অংশকে একত্রিত করতে পারি যাতে আমরা পছন্দ মতো দুটি অংশ, উপরে এবং নীচে দিয়ে শেষ করি। বিশ্লেষণ ট্যাঙ্গো গাছের প্রতিযোগিতামূলক অনুপাতকে সীমাবদ্ধ করার জন্য, আমাদের অবশ্যই সর্বোত্তম অফলাইন গাছের কার্যকারিতার উপর একটি নিম্ন সীমা খুঁজে বের করতে হবে যা আমরা একটি মানদণ্ড হিসাবে ব্যবহার করি। একবার আমরা ট্যাঙ্গো গাছের কার্যকারিতার উপর একটি উচ্চ সীমা খুঁজে পেলে, আমরা প্রতিযোগিতামূলক অনুপাতের জন্য তাদের ভাগ করতে পারি। ইন্টারলিভ বাউন্ড সর্বোত্তম অফলাইন বাইনারি সার্চ ট্রি দ্বারা করা কাজের উপর একটি নিম্ন সীমা খুঁজে পেতে, আমরা আবার পছন্দের শিশুদের ধারণাটি ব্যবহার করি। একটি অ্যাক্সেস সিকোয়েন্স (অনুসন্ধানের একটি ক্রম) বিবেচনা করার সময়, আমরা একটি রেফারেন্স ট্রি নোডের পছন্দের চাইল্ড কতবার স্যুইচ করে তার উপর নজর রাখি। সুইচগুলির মোট সংখ্যা (সমস্ত নোডের উপর সংক্ষিপ্ত) প্রদত্ত অ্যাক্সেস সিকোয়েন্সে যে কোনও বাইনারি সার্চ ট্রি অ্যালগরিদম দ্বারা করা কাজের উপর একটি অ্যাসিম্পটোটিক নিম্ন সীমা দেয়। একে ইন্টারলিভ লোয়ার বাউন্ড বলা হয়। ট্যাঙ্গো গাছ এটিকে ট্যাঙ্গো গাছের সাথে সংযুক্ত করার জন্য, আমরা একটি প্রদত্ত প্রবেশাধিকার ক্রমের জন্য ট্যাঙ্গো গাছের দ্বারা করা কাজের উপর একটি উপরের সীমা খুঁজে পাব। আমাদের উপরের সীমা হবে, যেখানে k হল আন্তঃপাতার সংখ্যা। মোট খরচকে দুটি ভাগে ভাগ করা হয়েছে, উপাদানটির সন্ধান করা এবং সঠিক অপরিবর্তনীয় বজায় রাখার জন্য ট্যাঙ্গো গাছের কাঠামো আপডেট করা (পছন্দের শিশুদের পরিবর্তন করা এবং পছন্দের পথগুলি পুনরায় সাজানো)। অনুসন্ধান করা হচ্ছে অনুসন্ধানটি (আপডেট না করা) এই সীমানার সাথে খাপ খায় কিনা তা দেখতে, কেবল লক্ষ্য করুন যে প্রতিবার একটি সহায়ক ট্রি অনুসন্ধান ব্যর্থ হয় এবং আমাদের পরবর্তী সহায়ক ট্রি-তে যেতে হয়, যার ফলে একটি পছন্দসই চাইল্ড সুইচ হয় (যেহেতু পিতামাতার পছন্দের পথটি এখন সন্তানের পছন্দের পথে যোগ দেওয়ার জন্য দিকনির্দেশ পরিবর্তন করে)। যেহেতু শেষ অনুসন্ধানটি ছাড়া সমস্ত সহায়ক গাছের অনুসন্ধান ব্যর্থ হয় (স্বাভাবিকভাবেই অনুসন্ধান সফল হলে আমরা থেমে যাই), তাই আমরা সহায়ক গাছের অনুসন্ধান করি। প্রতিটি অনুসন্ধান লাগে, কারণ একটি সহায়ক গাছের আকার রেফারেন্স গাছের উচ্চতা দ্বারা সীমাবদ্ধ। আপডেট করার খরচ এই সীমার মধ্যেও ফিট করে, কারণ আমাদের প্রতিটি পরিদর্শন করা সহায়ক গাছের জন্য শুধুমাত্র একটি কাট এবং একটি জয়েন করতে হবে। একটি একক কাট বা জয়েন অপারেশনে শুধুমাত্র ধ্রুবক সংখ্যক অনুসন্ধান, বিভাজন এবং কনক্যাটেনেট লাগে, যার প্রত্যেকটিতে সহায়ক গাছের আকারে লগারিদমিক সময় লাগে, তাই আমাদের আপডেটের খরচ হল। প্রতিযোগিতামূলক অনুপাত ট্যাঙ্গো গাছগুলি-প্রতিযোগিতামূলক, কারণ সর্বোত্তম অফলাইন বাইনারি সার্চ ট্রি দ্বারা করা কাজ কমপক্ষে কে-তে রৈখিক (পছন্দসই চাইল্ড সুইচগুলির মোট সংখ্যা), এবং ট্যাঙ্গো ট্রি দ্বারা করা কাজ সর্বাধিক। আরও দেখুন প্লে ট্রি অপটিমাল বাইনারি সার্চ ট্রি রেড-ব্ল্যাক ট্রি (তথ্য কাঠামো) রেফারেন্স বাইনারি ট্রি সার্চ ট্রি