Top tree
ટોપ ટ્રી એ બિનજરૂરી ગતિશીલ વૃક્ષો માટે દ્વિસંગી વૃક્ષ પર આધારિત માહિતી માળખું છે જેનો ઉપયોગ મુખ્યત્વે વિવિધ પાથ-સંબંધિત કામગીરીઓ માટે થાય છે. તે સરળ વિભાજન અને જીત અલ્ગોરિધમ્સને મંજૂરી આપે છે. ત્યારથી તે વૃક્ષના વ્યાસ, કેન્દ્ર અને મધ્ય જેવા ગતિશીલ વિવિધ ગુણધર્મો જાળવવા માટે વધારવામાં આવ્યું છે. ટોચનું વૃક્ષ અંતર્ગત વૃક્ષ માટે વ્યાખ્યાયિત કરવામાં આવે છે અને બાહ્ય બાઉન્ડ્રી વર્ટિસ ગ્લોસરી બાઉન્ડ્રી નોડ તરીકે ઓળખાતા મહત્તમ બે શિરોબિંદુઓના સમૂહ માટે વ્યાખ્યાયિત કરવામાં આવે છે. બાહ્ય સીમા શિરોબિંદુઓ ટોચના વૃક્ષમાં શિરોબિંદુઓની જોડી સુધી બાહ્ય સીમા શિરોબિંદુઓ તરીકે ઓળખાય છે, તેમને ક્લસ્ટરની સીમા શિરોબિંદુઓ તરીકે વિચારી શકાય છે જે સમગ્ર ટોચના વૃક્ષનું પ્રતિનિધિત્વ કરે છે. ક્લસ્ટર એ મહત્તમ બે બાઉન્ડ્રી વર્ટીસ સાથે જોડાયેલ સબટ્રી છે. આપેલ ક્લસ્ટરની બાઉન્ડ્રી વર્ટીસનો સમૂહ સૂચવવામાં આવે છે કે દરેક ક્લસ્ટર સાથે વપરાશકર્તા કેટલીક મેટા માહિતીને સાંકળી શકે છે અને તેને વિવિધ આંતરિક કામગીરી હેઠળ જાળવવા માટેની પદ્ધતિઓ આપી શકે છે. પાથ ક્લસ્ટર જો તેમાં ઓછામાં ઓછી એક ધાર હોય તો તેને પાથ ક્લસ્ટર કહેવામાં આવે છે. પોઇન્ટ ક્લસ્ટર જુઓ લીફ ક્લસ્ટર લીફ ક્લસ્ટર જો તેમાં કોઈ ધાર ન હોય તો એટલે કે માત્ર એક જ બાઉન્ડ્રી વર્ટેક્સ હોય તો તેને લીફ ક્લસ્ટર કહેવામાં આવે છે. એક જ ધાર ધરાવતા સમૂહને ધાર સમૂહ કહેવામાં આવે છે. લીફ એજ ક્લસ્ટર મૂળ ક્લસ્ટરમાં લીફને માત્ર એક જ બાઉન્ડ્રી વર્ટેક્સ સાથે ક્લસ્ટર દ્વારા રજૂ કરવામાં આવે છે અને તેને લીફ એજ ક્લસ્ટર કહેવામાં આવે છે. બે બાઉન્ડ્રી નોડ્સવાળા પાથ એજ ક્લસ્ટરને પાથ એજ ક્લસ્ટર કહેવામાં આવે છે. આંતરિક નોડ એ નોડને ક્લસ્ટર પાથનો આંતરિક નોડ કહેવામાં આવે છે બાઉન્ડ્રી વર્ટીસ વચ્ચેના માર્ગને ક્લસ્ટર પાથ કહેવામાં આવે છે અને તેને મર્જ કરી શકાય તેવા ક્લસ્ટર્સ બે ક્લસ્ટર્સ દ્વારા સૂચવવામાં આવે છે અને જો તે સિંગલટન સેટ હોય (તેમની પાસે બરાબર એક નોડ સામાન્ય હોય) અને તે ક્લસ્ટર હોય તો તે મર્જ કરી શકાય છે. પરિચય ટોચના વૃક્ષોનો ઉપયોગ કડી અને કાપવાની કામગીરી હેઠળ ગતિશીલ જંગલ (વૃક્ષોનો સમૂહ) જાળવવા માટે થાય છે. મૂળભૂત વિચાર એ છે કે મૂળ વૃક્ષમાં ગાંઠોની સંખ્યામાં લઘુગણક ઊંચાઈનું સંતુલિત દ્વિસંગી વૃક્ષ જાળવવું (એટલે કે. સમય અનુસાર); ટોચનું વૃક્ષ આવશ્યકપણે મૂળ વૃક્ષના પુનરાવર્તિત પેટાવિભાગને સમૂહમાં રજૂ કરે છે. સામાન્ય રીતે વૃક્ષની ધાર પર વજન હોઈ શકે છે. મૂળ વૃક્ષની ધાર અને ટોચના વૃક્ષના પાંદડાના ગાંઠો સાથે એક-થી-એક પત્રવ્યવહાર હોય છે અને વૃક્ષના દરેક આંતરિક નોડ એક ક્લસ્ટરનું પ્રતિનિધિત્વ કરે છે જે તેના બાળકો એવા ક્લસ્ટરોના જોડાણને કારણે રચાય છે. ટોચનું વૃક્ષ માહિતી માળખું સમયસર શરૂ કરી શકાય છે. તેથી () ઉપરનું ટોચનું વૃક્ષ એક દ્વિસંગી વૃક્ષ છે જેમ કે નોડ્સ () ના ક્લસ્ટરો છે; તેના પાંદડા એ ભાઈ-બહેનના ક્લસ્ટરોની ધાર છે તે અર્થમાં પડોશીઓ છે કે તેઓ એક જ શિરોબિંદુમાં છેદે છે, અને પછી તેમનું મૂળ ક્લસ્ટર તેમનું જોડાણ છે. વૃક્ષનું મૂળ પોતે જ છે, જેમાં મહત્તમ બે બાહ્ય સીમા શિરોબિંદુઓનો સમૂહ હોય છે. એક જ શિરોબિંદુ ધરાવતા વૃક્ષની ટોચ પર ખાલી વૃક્ષ હોય છે, અને માત્ર એક ધાર ધરાવતું વૃક્ષ માત્ર એક જ નોડ હોય છે. આ વૃક્ષો મુક્તપણે વૃદ્ધિ કરી શકાય તેવા છે, જે વપરાશકર્તાને ડેટા સ્ટ્રક્ચરની આંતરિક કામગીરીની વિગતોમાં ગયા વિના વિવિધ પ્રકારની લવચીકતા અને ઉત્પાદકતાની મંજૂરી આપે છે, જેને બ્લેક બોક્સ તરીકે પણ ઓળખવામાં આવે છે. ગતિશીલ કામગીરીઓ નીચેના ત્રણ વપરાશકર્તા માન્ય વન સુધારાઓ છે. કડી (વી, ડબલ્યુ): વિવિધ વૃક્ષો 1 અને 2 માં શિરોબિંદુઓ ક્યાં અને ક્યાં છે. તે વીડબલ્યુ કટ (વી, ડબલ્યુ) નું પ્રતિનિધિત્વ કરતું એક ટોચનું વૃક્ષ પાછું આપે છેઃ ટોચનાં વૃક્ષની ધારને દૂર કરે છે અને તેને બે વૃક્ષો વી અને ડબલ્યુમાં ફેરવે છે અને બે ટોચનાં વૃક્ષો વી અને ડબલ્યુમાં પાછું આપે છે. એક્સપોઝ (એસ): ટોચનાં વૃક્ષ પર મોટાભાગના પ્રશ્નોના અમલીકરણ માટે તેને સબરૂટિન કહેવામાં આવે છે. તેમાં વધુમાં વધુ 2 શિરોબિંદુઓ હોય છે. તે મૂળ બાહ્ય શિરોબિંદુઓને સામાન્ય શિરોબિંદુ બનાવે છે અને ટોચના વૃક્ષની નવી બાહ્ય સીમા શિરોબિંદુઓથી શિરોબિંદુ બનાવે છે. જો ખાલી ન હોય તો તે નવા રુટ ક્લસ્ટરને એક્સપોઝ ({v, w}) સાથે પરત કરે છે જો શિરોબિંદુઓ જુદા જુદા વૃક્ષોમાંથી હોય તો નિષ્ફળ જાય છે. આંતરિક કામગીરીઓ વન સુધારાઓ મોટાભાગની આંતરિક કામગીરીઓના ક્રમ દ્વારા હાથ ધરવામાં આવે છે, જેનો ક્રમ આગળના સમયમાં ગણવામાં આવે છે. એવું બની શકે છે કે વૃક્ષના સુધારા દરમિયાન, પાંદડાનો સમૂહ પાથ ક્લસ્ટર અને તેનાથી વિપરીતમાં બદલાઈ શકે છે. ટોપ ટ્રીમાં સુધારાઓ ફક્ત આ આંતરિક કામગીરીઓ દ્વારા કરવામાં આવે છે. દરેક આંતરિક કામગીરી સાથે સંકળાયેલ વપરાશકર્તા નિર્ધારિત કાર્યને કૉલ કરીને અપડેટ કરવામાં આવે છે. અહીં મર્જ કરો અને મર્જ કરી શકાય તેવા ક્લસ્ટર્સ છે, તે મૂળ ક્લસ્ટર તરીકે અને બાઉન્ડ્રી શિરોબિંદુઓ સાથે કમ્પ્યુટર્સના બાઉન્ડ્રી શિરોબિંદુઓ તરીકે અને સ્પ્લિટનો ઉપયોગ કરીને પરત આવે છે. સ્પ્લિટ સામાન્ય રીતે ક્લીન પદ્ધતિનો ઉપયોગ કરીને અમલમાં મૂકવામાં આવે છે જે વપરાશકર્તા પદ્ધતિને અપડેટ્સ અને ઉપયોગ અને અપડેટ્સ માટે કૉલ કરે છે જેથી તે જાણીતું હોય કે તેના બાળકોમાં કોઈ બાકી અપડેટ્સની જરૂર નથી. કરતાં વપરાશકર્તા નિર્ધારિત કાર્યોને કૉલ કર્યા વિના કાઢી નાખવામાં આવે છે. સ્પ્લિટની જરૂર વગર પ્રશ્નો માટે ઘણીવાર ક્લીન જરૂરી હોય છે. જો સ્પ્લિટ ક્લીન સબરૂટીનનો ઉપયોગ કરતું નથી, અને ક્લીન જરૂરી છે, તો તેની અસર મર્જ અને સ્પ્લિટને જોડીને ઓવરહેડ સાથે પ્રાપ્ત કરી શકાય છે. આગામી બે કાર્યો ઉપરોક્ત બે સમાન છે અને તેનો ઉપયોગ બેઝ ક્લસ્ટરો માટે થાય છે. ક્રિએટ એડ્જ માટે ક્લસ્ટર બનાવે છે સેટ્સની ગણતરી શરૂઆતથી કરવામાં આવે છે. ઇરેડિકેટ એ ધાર ક્લસ્ટર છે વપરાશકર્તા નિર્ધારિત કાર્યને પ્રક્રિયા કરવા માટે કહેવામાં આવે છે અને ક્લસ્ટરને ટોચના વૃક્ષમાંથી કાઢી નાખવામાં આવે છે. બિન-સ્થાનિક શોધ વપરાશકર્તા પસંદગીની કામગીરીને વ્યાખ્યાયિત કરી શકે છે જે મૂળ (બિન-પર્ણ) સમૂહ માટે તેના બાળ સમૂહમાંથી એકને પસંદ કરે છે. ટોપ ટ્રી બ્લેકબોક્સ સર્ચ રૂટિન પ્રદાન કરે છે, જે ચોઇસ ક્વેરીઝ અને ટોપ ટ્રીના પુનર્ગઠનનું આયોજન કરે છે (આંતરિક કામગીરીનો ઉપયોગ કરીને) જેથી તે તમામ પસંદ કરેલા ક્લસ્ટરોના આંતરછેદમાં એકમાત્ર ધારને શોધી શકે. કેટલીકવાર શોધ એક માર્ગ સુધી મર્યાદિત હોવી જોઈએ. આવા હેતુઓ માટે બિન-સ્થાનિક શોધનો એક પ્રકાર છે. જો રુટ ક્લસ્ટરમાં બે બાહ્ય સીમા શિરોબિંદુઓ હોય, તો ધાર માત્ર પાથ પર જ શોધવામાં આવે છે. તે નીચેના ફેરફારો કરવા માટે પૂરતું છેઃ જો રુટ ક્લસ્ટર ચિલ્ડ્રનમાંથી માત્ર એક જ પાથ ક્લસ્ટર હોય, તો તે ચૂઝ ઓપરેશનને કોલ કર્યા વિના મૂળભૂત રીતે પસંદ કરવામાં આવે છે. બિન-સ્થાનિક શોધના ઉદાહરણો લાંબા માર્ગ પર i-th ધાર શોધવી = એક્સપોઝ ({v, w}) દ્વારા કરી શકાય છે ત્યારબાદ યોગ્ય પસંદ સાથે સર્ચ () દ્વારા કરી શકાય છે. પસંદને અમલમાં મૂકવા માટે આપણે વૈશ્વિક ચલનું પ્રતિનિધિત્વ કરીએ છીએ અને વૈશ્વિક ચલનું પ્રતિનિધિત્વ કરીએ છીએ જે પસંદ કરે છે તે ઓછામાં ઓછી iff લંબાઈ સાથે ક્લસ્ટર પસંદ કરે છે. ઓપરેશનને ટેકો આપવા માટે લંબાઈમાં જાળવવી આવશ્યક છે. સમાન કાર્ય બિન-એકમ લંબાઈવાળા ધારવાળા આલેખ માટે ઘડવામાં આવી શકે છે. તે કિસ્સામાં અંતર બે ધાર વચ્ચેની ધાર અથવા શિરોબિંદુને સંબોધિત કરી શકે છે. આપણે પસંદને એવી રીતે વ્યાખ્યાયિત કરી શકીએ કે શિરોબિંદુ તરફ દોરી જતી ધાર પછીના કિસ્સામાં પરત કરવામાં આવે. એક સ્થિરાંક દ્વારા માર્ગની તમામ ધારની લંબાઈને વધારીને વ્યાખ્યાયિત સુધારા થઈ શકે છે. આવી સ્થિતિમાં આ સુધારાઓ માત્ર રુટ ક્લસ્ટરમાં સતત કરવામાં આવે છે. વિલંબિત અપડેટને બાળકોને વિતરિત કરવા માટે ક્લીન જરૂરી છે. 'ચૂઝ' બોલાવવામાં આવે તે પહેલાં 'ક્લીન' પર ફોન કરવો જોઈએ. લંબાઈ જાળવવા માટે તે કિસ્સામાં એકમ લંબાઈ પણ જાળવવાની જરૂર પડશે. શિરોબિંદુ ધરાવતા વૃક્ષનું કેન્દ્ર શોધવા માટે એક અંતિમ બિંદુ તરીકે કેન્દ્ર સાથે દ્વિ-કેન્દ્ર ધાર અથવા ધાર શોધી શકાય છે. ધારને = એક્સપોઝ ({v}) દ્વારા શોધી શકાય છે, ત્યારબાદ યોગ્ય પસંદ સાથે સર્ચ () દ્વારા અનુસરી શકાય છે. પસંદગી ઉચ્ચ મહત્તમ અંતર ધરાવતા બાળક સાથેના બાળકો વચ્ચેની પસંદગી કરે છે. કામગીરીને ટેકો આપવા માટે સીમા શિરોબિંદુથી ક્લસ્ટર સબટ્રીમાં મહત્તમ અંતર જાળવી રાખવું જોઈએ. તેના માટે ક્લસ્ટર પાથની લંબાઈની જાળવણી પણ જરૂરી છે. રસપ્રદ પરિણામો અને એપ્લિકેશન્સ મૂળરૂપે અન્ય પદ્ધતિઓ દ્વારા અમલમાં મુકવામાં આવેલી સંખ્યાબંધ રસપ્રદ એપ્લિકેશનો ટોપ ટ્રીના ઇન્ટરફેસનો ઉપયોગ કરીને સરળતાથી અમલમાં મૂકવામાં આવી છે. તેમાંના કેટલાકમાં ([સ્લીટર અને ટાર્જન 1983]) નો સમાવેશ થાય છે. અમે લિંક અને કટ દીઠ સમયસર વજનવાળા વૃક્ષોનો ગતિશીલ સંગ્રહ જાળવી શકીએ છીએ, જે સમયસર કોઈપણ બે શિરોબિંદુઓ વચ્ચેના મહત્તમ ધાર વજન વિશેના પ્રશ્નોને ટેકો આપે છે. સાબિતી રૂપરેખાઃ તેમાં દરેક નોડ પર તેના ક્લસ્ટર પાથ પર મહત્તમ વજન (મહત્તમ _ ડબલ્યુટી) જાળવવાનો સમાવેશ થાય છે, જો તે બિંદુ ક્લસ્ટર હોય તો મહત્તમ _ ડબલ્યુટી () ને આ રીતે શરૂ કરવામાં આવે છે જ્યારે ક્લસ્ટર બે ક્લસ્ટરોનું જોડાણ હોય ત્યારે તે બે મર્જ કરેલા ક્લસ્ટરનું મહત્તમ મૂલ્ય હોય છે. જો આપણે અને વચ્ચે મહત્તમ ડબલ્યુટી શોધવાનું હોય તો આપણે એક્સપોઝ કરીએ છીએ અને રિપોર્ટ કરીએ છીએ ([SLEATOR AND TARJAN 1983]). ઉપરોક્ત એપ્લિકેશનના દૃશ્યમાં આપણે આપેલ પાથ પરની તમામ ધાર પર એક સામાન્ય વજન પણ ઉમેરી શકીએ છીએ. સાબિતી રૂપરેખાઃ આપણે બધી ધાર પર ઉમેરવા માટે એક્સ્ટ્રા () નામનું વજન રજૂ કરીએ છીએ જેમાં યોગ્ય રીતે જાળવવામાં આવે છે; સ્પ્લિટ () માટે જરૂરી છે કે, આપણે દરેક પાથ ચાઇલ્ડ માટે મહત્તમ _ ડબલ્યુટી (એ): = મહત્તમ _ ડબલ્યુટી () + વધારાની () અને વધારાની (): = વધારાની () + વધારાની () સેટ કરીએ. માટેઃ = જોઇન (), આપણે મહત્તમ _ ડબલ્યુટી (): = મહત્તમ {મહત્તમ _ ડબલ્યુટી (), મહત્તમ _ ડબલ્યુટી ()} અને વધારાનું (): = 0 સેટ કરીએ છીએ. છેવટે, માર્ગ પર મહત્તમ વજન શોધવા માટે આપણે સુયોજિત કરીએ છીએઃ = એક્સપોઝ કરો અને મેક્સ _ ડબલ્યુટી () પરત કરો. ([ગોલ્ડબર્ગ એટ અલ. 1991]). આપણે સમયસર આપેલ શિરોબિંદુ ધરાવતા અંતર્ગત વૃક્ષમાં મહત્તમ વજન માટે પૂછી શકીએ છીએ. સાબિતી રૂપરેખાઃ આ માટે મર્જ અને સ્પ્લિટ કામગીરી હેઠળ ક્લસ્ટરમાં મહત્તમ વજન બિન-ક્લસ્ટર પાથ ધાર વિશે વધારાની માહિતી જાળવવાની જરૂર છે. બે શિરોબિંદુઓ વચ્ચેનું અંતર અને સમયની લંબાઈ (એક્સપોઝ) તરીકે શોધી શકાય છે. પ્રૂફ આઉટલાઇનઃ આપણે ક્લસ્ટર પાથની લંબાઈ () જાળવીશું. લંબાઈને મહત્તમ વજન તરીકે જાળવવામાં આવે છે સિવાય કે, જો જોડ (મર્જ) દ્વારા બનાવવામાં આવે, તો લંબાઈ () એ તેના પાથ ચિલ્ડ્રન સાથે સંગ્રહિત લંબાઈનો સરવાળો છે. વૃક્ષના વ્યાસ અને તેની અનુગામી જાળવણી અંગેના પ્રશ્નોમાં સમય લાગે છે. કેન્દ્ર અને મધ્યસ્થ મને લિંક (મર્જ) અને કટ (સ્પ્લિટ) કામગીરી હેઠળ જાળવી શકે છે અને સમયસર બિન-સ્થાનિક શોધ દ્વારા પૂછપરછ કરી શકે છે. ગતિશીલ દ્વિ-ધાર જોડાણ માટે અદ્યતન અલ્ગોરિધમ્સમાં ટોચના વૃક્ષોનો ઉપયોગ થાય છે. આ સમસ્યામાં, ગતિશીલ જોડાણની જેમ, આલેખ ધાર કાઢી નાખવા અને નિવેશને આધિન છે, તેમજ પ્રશ્નો પૂછે છે કે શું શિરોબિંદુઓની જોડી બે ધાર સાથે જોડાયેલ છે, અથવા તેમને અલગ કરતો પુલ છે. હોલ્મ, ડી લિક્ટનબર્ગ અને થોરુપ ઋણમુક્ત સુધારા સમય અને ક્વેરી સમય સાથે નિર્ધારક અલ્ગોરિધમ આપે છે. હોલ્મ, રોટેનબર્ગ અને થોરુપ દ્વારા અનુગામી કાર્ય આને સુધારેલા સુધારા સમય સુધી સુધારે છે, જેમાં ટોચના વૃક્ષોનો પણ ઉપયોગ કરવામાં આવે છે ગ્રાફને ધાર સમૂહને અપડેટ કરવાની અને શિરોબિંદુ 2-જોડાણ પર પ્રશ્નો પૂછવાની મંજૂરી આપીને જાળવી શકાય છે. સુધારાઓની ઋણમુક્ત જટિલતા છે. પ્રશ્નો વધુ ઝડપથી અમલમાં મૂકી શકાય છે. અલ્ગોરિધમ તુચ્છ નથી, તે જગ્યાનો ઉપયોગ કરે છે. ટોચના વૃક્ષોનો ઉપયોગ વૃક્ષોને એવી રીતે સંકુચિત કરવા માટે થઈ શકે છે કે જે ક્યારેય ડી. એ. જી. સંકોચન કરતાં વધુ ખરાબ ન હોય, પરંતુ તે ઝડપથી વધુ સારા હોઈ શકે છે. અમલીકરણ ટોચના વૃક્ષો વિવિધ રીતે અમલમાં મૂકવામાં આવ્યા છે, તેમાંના કેટલાકમાં બહુસ્તરીય વિભાજન (ટોચના વૃક્ષો અને ગતિશીલ ગ્રાફ અલ્ગોરિધમ્સ જેકબ હોલ્મ અને ક્રિસ્ટિયન ડી લિચટેનબર્ગ) નો ઉપયોગ કરીને અમલીકરણનો સમાવેશ થાય છે. તકનિકી અહેવાલ), અને સ્લેટર-ટાર્જન એસ-ટી વૃક્ષો (સામાન્ય રીતે ઋણમુક્ત સમય મર્યાદા સાથે), ફ્રેડરિકસનના ટોપોલોજી વૃક્ષો (સૌથી ખરાબ સમય મર્યાદા સાથે) (આલ્સ્ટ્રપ એટ અલ. ટોચના વૃક્ષો સાથે સંપૂર્ણ ગતિશીલ વૃક્ષોમાં માહિતી જાળવવી). ઋણમુક્ત અમલીકરણ વધુ સરળ છે, અને સમયની જટિલતામાં નાના ગુણાકાર પરિબળો સાથે. તેનાથી વિપરીત સૌથી ખરાબ કેસ અમલીકરણ ક્વેરી દરમિયાન બિનજરૂરી માહિતી અપડેટ્સને બંધ કરીને ક્વેરીઓને ઝડપી બનાવવાની મંજૂરી આપે છે (દ્રઢતા તકનીકો દ્વારા અમલમાં મૂકાય છે). ક્વેરીનો જવાબ આપ્યા પછી ટોચના વૃક્ષની મૂળ સ્થિતિનો ઉપયોગ કરવામાં આવે છે અને ક્વેરી સંસ્કરણને કાઢી નાખવામાં આવે છે. મલ્ટિલેવલ પાર્ટીશનિંગનો ઉપયોગ વૃક્ષના સમૂહોનું કોઈપણ પાર્ટીશનિંગ ક્લસ્ટર પાર્ટીશન ટ્રી CPT દ્વારા વૃક્ષના દરેક સમૂહને ધાર દ્વારા બદલીને રજૂ કરી શકાય છે. જો આપણે પાર્ટીશનિંગ માટે વ્યૂહરચના P નો ઉપયોગ કરીએ તો CPT CPTP હશે. આપણે જોશું કે અનુરૂપ ટોચના વૃક્ષના તમામ ગાંઠો આ બહુસ્તરીય પાર્ટીશનની ધારમાં અનન્ય રીતે મેપ કરવામાં આવ્યા છે. બહુસ્તરીય પાર્ટીશનમાં કેટલીક ધાર હોઈ શકે છે જે ટોચના વૃક્ષમાં કોઈપણ નોડને અનુરૂપ નથી, આ ધાર છે જે તેની નીચેના સ્તરમાં માત્ર એક જ બાળકનું પ્રતિનિધિત્વ કરે છે, એટલે કે. એક સરળ સમૂહ. જ્યારે આપણે વૃક્ષને સમૂહમાં વિભાજીત કરીએ છીએ ત્યારે માત્ર સંયુક્ત સમૂહને અનુરૂપ ધાર ટોચના વૃક્ષના ગાંઠોને અનુરૂપ હોય છે. વિભાજન વ્યૂહરચના મહત્વપૂર્ણ છે. માત્ર સાવચેતીપૂર્વકની વ્યૂહરચના એ સુનિશ્ચિત કરે છે કે આપણે ઊંચાઈ બહુસ્તરીય વિભાજન (અને તેથી ટોચનું વૃક્ષ) માં સમાપ્ત થઈએ છીએ. અનુગામી સ્તરોમાં ધારની સંખ્યામાં સતત પરિબળ દ્વારા ઘટાડો થવો જોઈએ. જો અપડેટ દ્વારા નીચલા સ્તરને બદલવામાં આવે તો આપણે વધુને વધુ સતત સંખ્યામાં નિવેશ અને કાઢી નાંખવાનો ઉપયોગ કરીને તેની ઉપરના સ્તરને તરત જ અપડેટ કરવામાં સક્ષમ બનવું જોઈએ. ઉપરોક્ત પાર્ટીશનિંગ વ્યૂહરચના સમયસર ટોચના વૃક્ષની જાળવણીની ખાતરી આપે છે. લિંક/કટ ટ્રી યુલર ટૂર ટ્રી ડાયનેમિક અલ્ગોરિધમ ડાયનેમિક કનેક્ટિવિટી સંદર્ભો સ્ટીફન આલ્સ્ટ્રપ, જેકબ હોલ્મ, ક્રિસ્ટિયન ડી લિચટેનબર્ગ અને મિકેલ થોરુપ, ટોચના વૃક્ષો સાથે સંપૂર્ણ ગતિશીલ વૃક્ષોમાં માહિતી જાળવવી, અલ્ગોરિધમ્સ પર ACM વ્યવહારો (TALG), વોલ્યુમ. 1 (2005), 243-264, સ્ટીફન આલ્સ્ટ્રપ, જેકબ હોલ્મ, ક્રિસ્ટિયન ડી લિચટેનબર્ગ, અને મિકેલ થોરુપ, કનેક્ટિવિટી માટે પોલી-લઘુગણક નિર્ધારક ગતિશીલ અલ્ગોરિધમ્સ, લઘુત્તમ સ્પૅનિંગ ટ્રી, 2-ધાર, અને બાયકનેક્ટિવિટી, જર્નલ ઓફ ધ એસીએમ, વોલ્યુમ. 48 અંક 4 (જુલાઈ 2001), 723-760, ડોનાલ્ડ ક્નુથ. ધ આર્ટ ઓફ કમ્પ્યુટર પ્રોગ્રામિંગઃ ફંડામેન્ટલ એલ્ગોરિધમ્સ, ત્રીજી આવૃત્તિ. એડિસન-વેસ્લી, 1997. વિભાગ 2.3: વૃક્ષો, પૃષ્ઠ. 308-423. થોમસ એચ. કોર્મન, ચાર્લ્સ ઇ. લિસરસન, રોનાલ્ડ એલ. રિવેસ્ટ અને ક્લિફોર્ડ સ્ટેઇન. અલ્ગોરિધમ્સનો પરિચય, બીજી આવૃત્તિ. એમઆઇટી પ્રેસ અને મેકગ્રો-હિલ, 2001. વિભાગ 10.4: મૂળ ધરાવતા વૃક્ષોનું પ્રતિનિધિત્વ, પૃષ્ઠ. 214-217. પ્રકરણો 12-14 (દ્વિસંગી શોધ વૃક્ષો, લાલ-કાળા વૃક્ષો, ડેટા સ્ટ્રક્ચર્સમાં વધારો), pp. 253-320. બાહ્ય કડીઓ ટોચના વૃક્ષો સાથે સંપૂર્ણ ગતિશીલ વૃક્ષોમાં માહિતી જાળવવી. આલ્સ્ટ્રુપ એટ અલ સેલ્ફ-એડજસ્ટિંગ ટોપ ટ્રીઝ. ટાર્જન અને વેર્નેક, પ્રો. 16મી એસ. ઓ. ડી. એ., 2005 દ્વિસંગી વૃક્ષો