Top tree
একটি শীর্ষ গাছ হল একটি তথ্য কাঠামো যা একটি বাইনারি গাছের উপর ভিত্তি করে শিকড়হীন গতিশীল গাছের জন্য যা মূলত বিভিন্ন পথ-সম্পর্কিত ক্রিয়াকলাপের জন্য ব্যবহৃত হয়। এটি সহজ বিভাজন এবং জয় অ্যালগরিদমের অনুমতি দেয়। তারপর থেকে এটি একটি গাছের গতিশীল বিভিন্ন বৈশিষ্ট্য যেমন ব্যাস, কেন্দ্র এবং মধ্যমা বজায় রাখার জন্য বর্ধিত করা হয়েছে। একটি উপরের গাছকে একটি অন্তর্নিহিত গাছের জন্য সংজ্ঞায়িত করা হয় এবং সর্বাধিক দুটি শীর্ষের একটি সেট যাকে এক্সটার্নাল বাউন্ডারি ভার্টিসেস গ্লোসারি বাউন্ডারি নোড বলা হয় একটি সংযুক্ত সাবট্রির একটি শীর্ষ একটি বাউন্ডারি ভার্টেক্স হয় যদি এটি একটি প্রান্ত দ্বারা সাবট্রির বাইরের কোনও শীর্ষের সাথে সংযুক্ত থাকে। উপরের গাছের এক জোড়া শীর্ষ পর্যন্ত বাহ্যিক সীমানা ভার্টিস বলা যেতে পারে, এগুলিকে ক্লাস্টারের সীমানা ভার্টিস হিসাবে বিবেচনা করা যেতে পারে যা পুরো উপরের গাছের প্রতিনিধিত্ব করে। একটি ক্লাস্টার হল একটি সংযুক্ত সাবট্রি যার সর্বাধিক দুটি বাউন্ডারি ভার্টিস রয়েছে। একটি প্রদত্ত ক্লাস্টারের বাউন্ডারি ভার্টিসের সেটকে চিহ্নিত করা হয় প্রতিটি ক্লাস্টারের সাথে ব্যবহারকারী কিছু মেটা তথ্য সংযুক্ত করতে পারে এবং বিভিন্ন অভ্যন্তরীণ ক্রিয়াকলাপের অধীনে এটি বজায় রাখার পদ্ধতি দিতে পারে। পাথ ক্লাস্টার যদি কমপক্ষে একটি প্রান্ত থাকে তবে এটিকে পাথ ক্লাস্টার বলা হয়। পয়েন্ট ক্লাস্টার দেখুন লিফ ক্লাস্টার লিফ ক্লাস্টার যদি কোনও প্রান্ত না থাকে অর্থাৎ। শুধুমাত্র একটি বাউন্ডারি ভার্টেক্স থাকলে তাকে লিফ ক্লাস্টার বলা হয়। এজ ক্লাস্টার একটি একক প্রান্তযুক্ত ক্লাস্টারকে এজ ক্লাস্টার বলা হয়। লিফ এজ ক্লাস্টার মূল ক্লাস্টারে একটি লিফ শুধুমাত্র একটি বাউন্ডারি ভার্টেক্স সহ একটি ক্লাস্টার দ্বারা প্রতিনিধিত্ব করা হয় এবং এটিকে লিফ এজ ক্লাস্টার বলা হয়। দুটি বাউন্ডারি নোড সহ পাথ এজ ক্লাস্টারগুলিকে পাথ এজ ক্লাস্টার বলা হয়। অভ্যন্তরীণ নোডের মধ্যে একটি নোডকে ক্লাস্টার পথের অভ্যন্তরীণ নোড বলা হয় এর সীমানা উল্লম্বগুলির মধ্যে পথটিকে ক্লাস্টার পথ বলা হয় এবং এটি মার্জেবল ক্লাস্টার দুটি ক্লাস্টার দ্বারা চিহ্নিত করা হয় এবং যদি একটি সিঙ্গলটন সেট হয় (তাদের ঠিক একটি নোড সাধারণ থাকে) এবং একটি ক্লাস্টার হয় তবে এটি মার্জেবল। ভূমিকা শীর্ষ গাছগুলি লিঙ্ক এবং কাটা ক্রিয়াকলাপের অধীনে একটি গতিশীল বন (গাছের সেট) রক্ষণাবেক্ষণের জন্য ব্যবহৃত হয়। মূল ধারণাটি হল মূল গাছের নোডের সংখ্যার মধ্যে লগারিদমিক উচ্চতার একটি ভারসাম্যপূর্ণ বাইনারি গাছ বজায় রাখা (অর্থাৎ। সময়ে); উপরের গাছটি মূলত মূল গাছের পুনরাবৃত্তিমূলক উপবিভাগকে গুচ্ছগুলিতে উপস্থাপন করে। সাধারণত গাছের প্রান্তে ওজন থাকতে পারে। মূল গাছের প্রান্ত এবং উপরের গাছের পাতার নোডগুলির সাথে এক-থেকে-এক যোগাযোগ রয়েছে এবং এর প্রতিটি অভ্যন্তরীণ নোড একটি গুচ্ছকে উপস্থাপন করে যা তার সন্তান গুচ্ছগুলির মিলনের কারণে গঠিত হয়। শীর্ষ গাছের তথ্য কাঠামো সময়মতো শুরু করা যেতে পারে। অতএব ()-এর উপরের গাছটি এমন একটি বাইনারি গাছ যার নোডগুলি হল ()-এর গুচ্ছ; এর পাতাগুলি হল ভাইবোন গুচ্ছগুলির প্রান্তগুলি এই অর্থে প্রতিবেশী যে তারা একটি একক শীর্ষে ছেদ করে, এবং তারপর তাদের মূল গুচ্ছ হল তাদের মিলন। সর্বাধিক দুটি বাহ্যিক সীমানা উল্লম্বের একটি সেট সহ গাছের মূল নিজেই। একটি একক শীর্ষযুক্ত গাছের একটি খালি শীর্ষ গাছ থাকে এবং কেবল একটি প্রান্তযুক্ত গাছটি কেবল একটি নোড। এই গাছগুলি অবাধে বৃদ্ধি করা যায় যা ব্যবহারকারীকে ডেটা কাঠামোর অভ্যন্তরীণ ক্রিয়াকলাপের বিশদে না গিয়ে বিভিন্ন ধরণের নমনীয়তা এবং উত্পাদনশীলতার অনুমতি দেয়, যা ব্ল্যাক বক্স হিসাবেও উল্লেখ করা হয়। গতিশীল ক্রিয়াকলাপ নিম্নলিখিত তিনটি হল ব্যবহারকারীর অনুমোদিত ফরেস্ট আপডেট। লিঙ্ক (ভি, ডাব্লু): বিভিন্ন গাছ 1 এবং 2-এ কোথায় এবং কোথায় অবস্থিত। এটি vw কাট (v, w)-এর প্রতিনিধিত্বকারী একটি একক শীর্ষ গাছ ফিরিয়ে দেয়ঃ উপরের গাছ সহ একটি গাছ থেকে প্রান্তটি সরিয়ে দেয় যার ফলে এটি দুটি গাছে পরিণত হয় v এবং w এবং দুটি শীর্ষ গাছ v এবং w ফিরিয়ে দেয়। এক্সপোজ (S): একটি উপরের গাছে বেশিরভাগ প্রশ্ন বাস্তবায়নের জন্য একটি সাব-রুটিন হিসাবে বলা হয়। সর্বাধিক 2টি শীর্ষ রয়েছে। এটি মূল বাহ্যিক শীর্ষগুলিকে স্বাভাবিক শীর্ষে পরিণত করে এবং উপরের গাছের নতুন বাহ্যিক সীমানা থেকে শীর্ষ তৈরি করে। যদি খালি না থাকে তবে এটি এক্সপোজ ({v, w}) সহ নতুন মূল গুচ্ছটি ফেরত দেয় যদি শীর্ষগুলি বিভিন্ন গাছ থেকে হয়। অভ্যন্তরীণ ক্রিয়াকলাপ বন আপডেটগুলি বেশিরভাগ অভ্যন্তরীণ ক্রিয়াকলাপের একটি ক্রম দ্বারা পরিচালিত হয়, যার ক্রম পরবর্তী সময়ে গণনা করা হয়। এটি ঘটতে পারে যে একটি ট্রি আপডেটের সময়, একটি পাতার গুচ্ছ একটি পথ গুচ্ছ এবং বিপরীত দিকে পরিবর্তিত হতে পারে। টপ ট্রি-র আপডেটগুলি কেবলমাত্র এই অভ্যন্তরীণ ক্রিয়াকলাপগুলির দ্বারা করা হয়। প্রতিটি অভ্যন্তরীণ ক্রিয়াকলাপের সাথে যুক্ত একটি ব্যবহারকারী সংজ্ঞায়িত ফাংশনকে কল করে আপডেট করা হয়। এখানে একত্রিত করুন এবং মার্জেবল ক্লাস্টারগুলি, এটি মূল ক্লাস্টার হিসাবে ফিরে আসে এবং এবং বাউন্ডারি ভার্টিসেস সহ কম্পিউটসের বাউন্ডারি ভার্টিসেস হিসাবে ব্যবহার করে এবং স্প্লিট এখানে রুট ক্লাস্টার এটি আপডেট করে এবং ব্যবহার করে এবং ক্লাস্টারটিকে মুছে দেয়। স্প্লিট সাধারণত ক্লিন পদ্ধতি ব্যবহার করে প্রয়োগ করা হয় যা ব্যবহারকারী পদ্ধতির আপডেট এবং ব্যবহার এবং আপডেটের জন্য কল করে যাতে এটি জানা যায় যে এর শিশুদের মধ্যে কোনও মুলতুবি আপডেটের প্রয়োজন নেই। ব্যবহারকারী সংজ্ঞায়িত ফাংশনগুলিকে কল না করে বাতিল করা হয়। বিভক্ত করার প্রয়োজন ছাড়াই প্রায়শই প্রশ্নের জন্য ক্লিন প্রয়োজন হয়। যদি স্প্লিট ক্লিন সাবরুটিন ব্যবহার না করে, এবং ক্লিন প্রয়োজন হয়, তবে এর প্রভাব মার্জ এবং স্প্লিটকে একত্রিত করে ওভারহেড দিয়ে অর্জন করা যেতে পারে। পরবর্তী দুটি ফাংশন উপরের দুটির অনুরূপ এবং বেস ক্লাস্টারের জন্য ব্যবহৃত হয়। প্রান্তের জন্য একটি ক্লাস্টার তৈরি করুন সেটগুলি স্ক্র্যাচ থেকে গণনা করা হয়। ইরেডিকেট হল প্রান্তের ক্লাস্টার ব্যবহারকারী সংজ্ঞায়িত ফাংশনটিকে প্রক্রিয়া করার জন্য বলা হয় এবং ক্লাস্টারটি উপরের গাছ থেকে মুছে ফেলা হয়। অ-স্থানীয় অনুসন্ধান ব্যবহারকারী 'চয়েজ অপারেশন' সংজ্ঞায়িত করতে পারেন যা একটি মূল (অ-পাতাযুক্ত) গুচ্ছের জন্য তার একটি শিশু গুচ্ছ নির্বাচন করে। টপ ট্রি ব্ল্যাকবক্স সার্চ রুটিন প্রদান করে, যা বাছাই প্রশ্ন এবং উপরের গাছের পুনর্গঠন (অভ্যন্তরীণ ক্রিয়াকলাপ ব্যবহার করে) এমনভাবে সংগঠিত করে যাতে এটি সমস্ত নির্বাচিত ক্লাস্টারের ছেদস্থলে একমাত্র প্রান্তটি সনাক্ত করে। কখনও কখনও অনুসন্ধান একটি পথের মধ্যে সীমাবদ্ধ থাকা উচিত। এই ধরনের উদ্দেশ্যে অ-স্থানীয় অনুসন্ধানের একটি রূপ রয়েছে। যদি মূল গুচ্ছের মধ্যে দুটি বাহ্যিক সীমানা শীর্ষ থাকে, তবে প্রান্তটি কেবল পথেই অনুসন্ধান করা হয়। নিম্নলিখিত পরিবর্তনগুলি করার জন্য এটি যথেষ্টঃ যদি রুট ক্লাস্টার শিশুদের মধ্যে শুধুমাত্র একটি পাথ ক্লাস্টার হয়, তবে এটি চয়েজ অপারেশনে কল না করেই ডিফল্টরূপে নির্বাচিত হয়। অ-স্থানীয় অনুসন্ধানের উদাহরণগুলি = এক্সপোজ ({v, w}) এর পরে উপযুক্ত চয়েস সহ সার্চ () দ্বারা করা যেতে পারে। চয়েজ বাস্তবায়নের জন্য আমরা গ্লোবাল ভেরিয়েবল রিপ্রেজেন্টিং ব্যবহার করি এবং গ্লোবাল ভেরিয়েবল রিপ্রেজেন্টিং চয়েজ অন্তত আইএফএফ দৈর্ঘ্য সহ ক্লাস্টার নির্বাচন করে। অপারেশনকে সমর্থন করার জন্য দৈর্ঘ্য বজায় রাখতে হবে। অ-একক দৈর্ঘ্যের প্রান্তযুক্ত গ্রাফের জন্য অনুরূপ কাজ প্রণয়ন করা যেতে পারে। সেক্ষেত্রে দূরত্বটি দুটি প্রান্তের মধ্যে একটি প্রান্ত বা একটি শীর্ষকে সম্বোধন করতে পারে। আমরা 'চয়েজ'-কে এমনভাবে সংজ্ঞায়িত করতে পারি যাতে পরবর্তী ক্ষেত্রে শীর্ষে যাওয়ার প্রান্তটি ফিরে আসে। একটি ধ্রুবক দ্বারা একটি পথ বরাবর সমস্ত প্রান্তের দৈর্ঘ্য বৃদ্ধি করে সংজ্ঞায়িত আপডেট হতে পারে। এই পরিস্থিতিতে এই আপডেটগুলি কেবল রুট ক্লাস্টারে স্থির সময়ে করা হয়। বিলম্বিত আপডেট শিশুদের মধ্যে বিতরণ করার জন্য ক্লিন প্রয়োজন। চয়েজ আহ্বান করার আগে ক্লিনকে কল করা উচিত। দৈর্ঘ্য বজায় রাখার জন্য সেই ক্ষেত্রে একক দৈর্ঘ্যও বজায় রাখতে হবে। দ্বিস্তরীয় প্রান্ত বা প্রান্ত খুঁজে বের করে শীর্ষযুক্ত গাছের কেন্দ্র খুঁজে বের করা যেতে পারে যার কেন্দ্রটি একটি শেষবিন্দু হিসাবে রয়েছে। প্রান্তটি খুঁজে পাওয়া যেতে পারে = এক্সপোজ ({v}) এর পরে উপযুক্ত চয়েজ সহ সার্চ ()। পছন্দটি উচ্চতর সর্বাধিক দূরত্ব সহ সন্তানের সাথে শিশুদের মধ্যে নির্বাচন করে। অপারেশনকে সমর্থন করার জন্য একটি সীমানা শীর্ষ থেকে ক্লাস্টার সাবট্রির সর্বাধিক দূরত্ব বজায় রাখতে হবে। এর জন্য ক্লাস্টার পথের দৈর্ঘ্যের রক্ষণাবেক্ষণও প্রয়োজন। আকর্ষণীয় ফলাফল এবং প্রয়োগ মূলত অন্যান্য পদ্ধতি দ্বারা বাস্তবায়িত বেশ কয়েকটি আকর্ষণীয় অ্যাপ্লিকেশন উপরের গাছের ইন্টারফেস ব্যবহার করে সহজেই প্রয়োগ করা হয়েছে। এর মধ্যে কয়েকটির মধ্যে রয়েছে ([স্লেটর এবং টার্জন 1983])। আমরা প্রতি লিঙ্ক এবং কাটার সময়ে ওজনযুক্ত গাছের একটি গতিশীল সংগ্রহ বজায় রাখতে পারি, সময়ের মধ্যে যে কোনও দুটি শীর্ষের মধ্যে সর্বাধিক প্রান্তের ওজন সম্পর্কে প্রশ্নগুলিকে সমর্থন করতে পারি। প্রুফ আউটলাইনঃ এটি প্রতিটি নোডে তার ক্লাস্টার পথে সর্বাধিক ওজন (ম্যাক্স _ ডাব্লুটি) বজায় রাখার সাথে জড়িত, যদি এটি একটি পয়েন্ট ক্লাস্টার হয় তবে ম্যাক্স _ ডাব্লুটি () হিসাবে শুরু করা হয় যখন একটি ক্লাস্টার দুটি ক্লাস্টারের মিলন হয় তখন এটি দুটি সংযুক্ত ক্লাস্টারের সর্বোচ্চ মান। যদি আমাদের এবং এর মধ্যে সর্বোচ্চ ডাব্লুটি খুঁজে বের করতে হয় তবে আমরা এক্সপোজ করি এবং রিপোর্ট করি ম্যাক্স _ ডাব্লুটি ([স্লিটার এবং টারজান 1983])। উপরের প্রয়োগের দৃশ্যে আমরা একটি নির্দিষ্ট পথের সমস্ত প্রান্তে একটি সাধারণ ওজন যোগ করতে পারি। প্রমাণের রূপরেখাঃ আমরা সমস্ত প্রান্তে যোগ করার জন্য অতিরিক্ত () নামক একটি ওজন প্রবর্তন করি যা যথাযথভাবে রক্ষণাবেক্ষণ করা হয়; বিভক্ত () এর জন্য প্রয়োজন যে, প্রতিটি পথের চাইল্ডের জন্য আমরা ম্যাক্স _ ডব্লিউটি (এ): = ম্যাক্স _ ডব্লিউটি () + অতিরিক্ত () এবং অতিরিক্ত (): = অতিরিক্ত () + অতিরিক্ত () সেট করি। এর জন্যঃ = যোগদান (), আমরা ম্যাক্স _ ডাব্লুটি (): = ম্যাক্স {ম্যাক্স _ ডাব্লুটি (), ম্যাক্স _ ডাব্লুটি ()} এবং অতিরিক্ত (): = 0 সেট করি। পরিশেষে, পথের সর্বোচ্চ ওজন খুঁজে বের করতে আমরা নির্ধারণ করিঃ = এক্সপোজ এবং রিটার্ন ম্যাক্স _ ডব্লিউটি ()। ([গোল্ডবার্গ এট আল। 1991])। আমরা নির্দিষ্ট সময়ে একটি প্রদত্ত শীর্ষযুক্ত অন্তর্নিহিত গাছের সর্বাধিক ওজন চাইতে পারি। প্রুফ আউটলাইনঃ এর জন্য মার্জ অ্যান্ড স্প্লিট অপারেশনের অধীনে একটি ক্লাস্টারে সর্বাধিক ওজনের নন-ক্লাস্টার পথের প্রান্ত সম্পর্কে অতিরিক্ত তথ্য বজায় রাখা প্রয়োজন। দুটি শীর্ষের মধ্যে দূরত্ব এবং দৈর্ঘ্য হিসাবে সময় পাওয়া যায় (এক্সপোজ)। প্রুফ আউটলাইনঃ আমরা ক্লাস্টার পথের দৈর্ঘ্য () বজায় রাখব। দৈর্ঘ্যটি সর্বাধিক ওজন হিসাবে বজায় রাখা হয়, তবে যদি একটি জয়েন (মার্জ) দ্বারা তৈরি করা হয়, তবে দৈর্ঘ্য () তার পথের শিশুদের সাথে সঞ্চিত দৈর্ঘ্যের যোগফল। একটি গাছের ব্যাস এবং তার পরবর্তী রক্ষণাবেক্ষণ সম্পর্কে প্রশ্ন করতে সময় লাগে। সেন্টার এবং মিডিয়ান কি লিঙ্ক (মার্জ) এবং কাট (স্প্লিট) ক্রিয়াকলাপের অধীনে রক্ষণাবেক্ষণ করতে পারে এবং সময়মতো অ-স্থানীয় অনুসন্ধানের মাধ্যমে জিজ্ঞাসা করতে পারে। শীর্ষ গাছগুলি গতিশীল দ্বি-প্রান্ত সংযোগের জন্য অত্যাধুনিক অ্যালগরিদমগুলিতে ব্যবহৃত হয়। এই সমস্যায়, একইভাবে গতিশীল সংযোগের ক্ষেত্রে, গ্রাফটি প্রান্ত মুছে ফেলা এবং সন্নিবেশের সাপেক্ষে, পাশাপাশি প্রশ্ন করা হয় যে এক জোড়া শীর্ষবিন্দু দুই প্রান্ত সংযুক্ত কিনা, নাকি তাদের আলাদা করার জন্য একটি সেতু রয়েছে। হোম, ডি লিচটেনবার্গ এবং থোরুপ একটি নির্ধারণমূলক অ্যালগরিদম প্রদান করে যার সাথে পরিশোধিত আপডেট সময় এবং অনুসন্ধানের সময় রয়েছে। হোম, রটেনবার্গ এবং থোরাপের পরবর্তী কাজটি এটিকে একটি পরিশোধিত আপডেটের সময়ে উন্নত করে, এছাড়াও শীর্ষ গাছগুলি ব্যবহার করে গ্রাফটি বজায় রাখা যেতে পারে যাতে প্রান্ত সেটটি আপডেট করা যায় এবং ভার্টেক্স 2-সংযোগ সম্পর্কে প্রশ্ন জিজ্ঞাসা করা যায়। হালনাগাদের ঋণ পরিশোধের জটিলতা হল। প্রশ্নগুলি আরও দ্রুত বাস্তবায়িত করা যেতে পারে। অ্যালগরিদমটি তুচ্ছ নয়, স্থান ব্যবহার করে। উপরের গাছগুলি এমনভাবে গাছগুলিকে সংকুচিত করতে ব্যবহার করা যেতে পারে যা ডিএজি সংকোচনের চেয়ে খুব বেশি খারাপ নয়, তবে তাত্পর্যপূর্ণভাবে আরও ভাল হতে পারে। বাস্তবায়ন শীর্ষ গাছগুলি বিভিন্ন উপায়ে প্রয়োগ করা হয়েছে, তাদের মধ্যে কয়েকটি মাল্টিলেভেল পার্টিশন (শীর্ষ গাছ এবং গতিশীল গ্রাফ অ্যালগরিদম জ্যাকব হোম এবং ক্রিস্টিয়ান ডি লিচটেনবার্গ) ব্যবহার করে বাস্তবায়ন অন্তর্ভুক্ত। প্রযুক্তিগত প্রতিবেদন), এবং এমনকি স্লেটর-টার্জন এস-টি ট্রি (সাধারণত ঋণ পরিশোধিত সময়সীমা সহ), ফ্রেডেরিকসন টপোলজি ট্রি (সবচেয়ে খারাপ সময় সীমা সহ) (অ্যালস্ট্রুপ এট আল। শীর্ষ গাছ সহ সম্পূর্ণ গতিশীল গাছগুলিতে তথ্য বজায় রাখা)। পরিশোধিত বাস্তবায়নগুলি আরও সহজ, এবং সময় জটিলতার ক্ষেত্রে ছোট গুণক উপাদান সহ। অন্যদিকে, সবচেয়ে খারাপ ক্ষেত্রে প্রয়োগগুলি অনুসন্ধানের সময় অপ্রয়োজনীয় তথ্য আপডেটগুলি বন্ধ করে প্রশ্নের গতি বাড়ানোর অনুমতি দেয় (অধ্যবসায় কৌশল দ্বারা বাস্তবায়িত)। প্রশ্নের উত্তর দেওয়ার পরে উপরের গাছের মূল অবস্থা ব্যবহার করা হয় এবং প্রশ্নের সংস্করণটি বাতিল করা হয়। মাল্টিলেভেল পার্টিশনিং ব্যবহার করে একটি গাছের গুচ্ছের যে কোনও বিভাজনকে একটি ক্লাস্টার পার্টিশন ট্রি সিপিটি দ্বারা গাছের প্রতিটি গুচ্ছকে একটি প্রান্ত দ্বারা প্রতিস্থাপন করে উপস্থাপন করা যেতে পারে। যদি আমরা পার্টিশন করার জন্য একটি কৌশল পি ব্যবহার করি তবে সিপিটি সিপিটিপি হবে এটি পুনরাবৃত্তিমূলকভাবে করা হয় যতক্ষণ না শুধুমাত্র একটি প্রান্ত থাকে। আমরা লক্ষ্য করব যে সংশ্লিষ্ট শীর্ষ গাছের সমস্ত নোডগুলি এই বহু-স্তরের বিভাজনের প্রান্তে অনন্যভাবে ম্যাপ করা হয়েছে। মাল্টিলেভেল পার্টিশনে কিছু প্রান্ত থাকতে পারে যা উপরের গাছের কোনও নোডের সাথে সামঞ্জস্যপূর্ণ নয়, এগুলি এমন প্রান্ত যা এর নীচের স্তরে কেবল একটি একক সন্তানের প্রতিনিধিত্ব করে, অর্থাৎ। একটি সহজ ক্লাস্টার। শুধুমাত্র যৌগিক গুচ্ছের সাথে সামঞ্জস্যপূর্ণ প্রান্তগুলি উপরের গাছের নোডের সাথে সামঞ্জস্যপূর্ণ একটি বিভাজন কৌশল গুরুত্বপূর্ণ যখন আমরা গাছটিকে গুচ্ছগুলিতে বিভক্ত করি। শুধুমাত্র একটি সতর্ক কৌশল নিশ্চিত করে যে আমরা একটি উচ্চতার মাল্টিলেভেল পার্টিশনে (এবং তাই উপরের গাছ) শেষ করি। পরবর্তী স্তরে প্রান্তের সংখ্যা একটি ধ্রুবক ফ্যাক্টর দ্বারা হ্রাস করা উচিত। যদি একটি নিম্ন স্তর একটি আপডেট দ্বারা পরিবর্তিত হয় তবে আমাদের সর্বাধিক স্থির সংখ্যক সন্নিবেশ এবং মুছে ফেলা ব্যবহার করে তার উপরের স্তরটি অবিলম্বে আপডেট করতে সক্ষম হওয়া উচিত। উপরের বিভাজন কৌশলটি সময়মতো উপরের গাছের রক্ষণাবেক্ষণ নিশ্চিত করে। আরও দেখুন লিঙ্ক/কাট ট্রি অয়লার ট্যুর ট্রি ডায়নামিক অ্যালগরিদম ডায়নামিক কানেক্টিভিটি রেফারেন্স স্টিফেন আলস্ট্রুপ, জ্যাকব হোম, ক্রিস্টিয়ান ডি লিচটেনবার্গ এবং মিকেল থোরুপ, শীর্ষ গাছগুলির সাথে সম্পূর্ণ গতিশীল গাছগুলিতে তথ্য বজায় রাখা, অ্যালগরিদমগুলিতে এসিএম লেনদেন (টিএএলজি), খণ্ড। 1 (2005), 243-264, স্টিফেন আলস্ট্রুপ, জ্যাকব হোম, ক্রিস্টিয়ান ডি লিচটেনবার্গ, এবং মিকেল থোরুপ, সংযোগের জন্য পলি-লগারিদমিক নির্ধারক গতিশীল অ্যালগরিদম, ন্যূনতম স্প্যানিং ট্রি, 2-এজ, এবং বাইকনেক্টিভিটি, জার্নাল অফ দ্য এসিএম, খণ্ড। 48 সংখ্যা 4 (জুলাই 2001), 723-760, ডোনাল্ড নুথ। দ্য আর্ট অফ কম্পিউটার প্রোগ্রামিংঃ ফান্ডামেন্টাল অ্যালগরিদমস, তৃতীয় সংস্করণ। অ্যাডিসন-ওয়েসলি, 1997। বিভাগ 2.3: গাছ, পৃ. 308-423। টমাস এইচ. করমেন, চার্লস ই. লেইসারসন, রোনাল্ড এল. রিভেস্ট এবং ক্লিফোর্ড স্টেইন। অ্যালগরিদমের ভূমিকা, দ্বিতীয় সংস্করণ। এমআইটি প্রেস এবং ম্যাকগ্রা-হিল, 2001। বিভাগ 10.4: শিকড়যুক্ত গাছের প্রতিনিধিত্ব করা, পৃ. 214-217। অধ্যায় 12-14 (বাইনারি সার্চ ট্রি, রেড-ব্ল্যাক ট্রি, অগমেন্টিং ডেটা স্ট্রাকচার), পৃ. 253-320। বাইরের লিঙ্কগুলি শীর্ষ গাছগুলির সাথে সম্পূর্ণ গতিশীল গাছগুলিতে তথ্য বজায় রাখা। আলস্ট্রুপ এবং অন্যান্য স্ব-সামঞ্জস্য শীর্ষ গাছ। টারজান এবং ওয়ার্নেক, প্রোক। 16তম সোডা, 2005 বাইনারি গাছ