Tango tree
ટેંગો વૃક્ષ એ દ્વિસંગી શોધ વૃક્ષનો એક પ્રકાર છે, જે 2004માં એરિક ડી. ડેમાઇન, ડીયોન હાર્મન, જ્હોન આઈકોનો અને મિહાઈ પેટ્રાક્કુ દ્વારા પ્રસ્તાવિત કરવામાં આવ્યું હતું. તેનું નામ બ્યુનોસ એરેસ પરથી રાખવામાં આવ્યું છે, જેમાંથી ટેંગો પ્રતિકાત્મક છે. તે એક ઓનલાઇન દ્વિસંગી શોધ વૃક્ષ છે જે ઓફલાઇન શ્રેષ્ઠ દ્વિસંગી શોધ વૃક્ષની તુલનામાં સ્પર્ધાત્મક ગુણોત્તર પ્રાપ્ત કરે છે, જ્યારે માત્ર નોડ દીઠ મેમરીના વધારાના બિટ્સનો ઉપયોગ કરે છે. આ અગાઉના સૌથી જાણીતા સ્પર્ધાત્મક ગુણોત્તરમાં સુધારો થયો છે, જે હતો. બંધારણ ટેંગોના વૃક્ષો દ્વિસંગી શોધ વૃક્ષને પસંદગીના માર્ગોના સમૂહમાં વિભાજિત કરીને કામ કરે છે, જે પોતે સહાયક વૃક્ષોમાં સંગ્રહિત થાય છે (તેથી ટેંગોના વૃક્ષને વૃક્ષોના વૃક્ષ તરીકે રજૂ કરવામાં આવે છે). સંદર્ભ વૃક્ષ ટેંગો વૃક્ષનું નિર્માણ કરવા માટે, આપણે સંદર્ભ વૃક્ષ તરીકે ઓળખાતા સંપૂર્ણ દ્વિસંગી શોધ વૃક્ષનું અનુકરણ કરીએ છીએ, જે ફક્ત તમામ ઘટકો ધરાવતું પરંપરાગત દ્વિસંગી શોધ વૃક્ષ છે. આ વૃક્ષ વાસ્તવિક અમલીકરણમાં ક્યારેય દેખાતું નથી, પરંતુ ટેંગો વૃક્ષના નીચેના ટુકડાઓ પાછળનો વૈચારિક આધાર છે. ખાસ કરીને, સંદર્ભ વૃક્ષની ઊંચાઈ છે. આ સૌથી લાંબા માર્ગની લંબાઈ બરાબર છે, અને તેથી સૌથી મોટા સહાયક વૃક્ષનું કદ. સહાયક વૃક્ષોને વ્યાજબી રીતે સંતુલિત રાખીને, સહાયક વૃક્ષોની ઊંચાઈને આ અલ્ગોરિધમની કામગીરીની બાંયધરીનો સ્રોત છે. પસંદગીના માર્ગો પ્રથમ, અમે દરેક નોડ માટે તેના પસંદગીના ચાઈલ્ડને વ્યાખ્યાયિત કરીએ છીએ, જે અનૌપચારિક રીતે પરંપરાગત દ્વિસંગી સર્ચ ટ્રી લુકઅપ દ્વારા તાજેતરમાં સૌથી વધુ મુલાકાત લેવાયેલ ચાઈલ્ડ છે. વધુ ઔપચારિક રીતે, બાળકો l (ડાબે) અને r (જમણે) સાથે, p પર મૂળ ધરાવતા સબટ્રી T ને ધ્યાનમાં લો. આપણે r ને p ના પસંદગીના બાળક તરીકે સેટ કરીએ છીએ જો T માં સૌથી તાજેતરમાં એક્સેસ કરેલ નોડ r પર મૂળ ધરાવતા સબટ્રીમાં હોય, અને અન્યથા l ને પસંદગીના બાળક તરીકે. નોંધ લો કે જો T નો સૌથી તાજેતરમાં એક્સેસ કરેલ નોડ p પોતે જ હોય, તો વ્યાખ્યા દ્વારા l એ પસંદગીનું ચાઈલ્ડ છે. એક પસંદગીનો માર્ગ મૂળથી શરૂ કરીને અને પાંદડાના નોડ સુધી પહોંચે ત્યાં સુધી પસંદગીના બાળકોને અનુસરીને વ્યાખ્યાયિત કરવામાં આવે છે. આ માર્ગ પરના ગાંઠોને દૂર કરવાથી વૃક્ષના બાકીના ભાગને સંખ્યાબંધ પેટા વૃક્ષોમાં વિભાજિત કરવામાં આવે છે, અને અમે દરેક પેટા વૃક્ષ પર પુનરાવર્તન કરીએ છીએ (તેના મૂળમાંથી પસંદગીનો માર્ગ બનાવીએ છીએ, જે પેટા વૃક્ષને વધુ પેટા વૃક્ષોમાં વિભાજિત કરે છે). સહાયક વૃક્ષો પસંદગીના માર્ગનું પ્રતિનિધિત્વ કરવા માટે, આપણે તેના ગાંઠોને સંતુલિત દ્વિસંગી શોધ વૃક્ષમાં, ખાસ કરીને લાલ-કાળા વૃક્ષમાં સંગ્રહિત કરીએ છીએ. પસંદગીના પાથ P માં દરેક બિન-પર્ણ નોડ n માટે, તેમાં બિન-પસંદગીનું ચાઈલ્ડ c હોય છે, જે નવા સહાયક વૃક્ષનું મૂળ છે. આપણે આ અન્ય સહાયક વૃક્ષના મૂળ (સી) ને પી માં એન સાથે જોડીએ છીએ, આમ સહાયક વૃક્ષોને એકસાથે જોડીએ છીએ. અમે દરેક નોડ પર તે નોડ હેઠળ સબટ્રીમાં ગાંઠોની લઘુત્તમ અને મહત્તમ ઊંડાઈ (સંદર્ભ વૃક્ષની ઊંડાઈ, એટલે કે) સંગ્રહિત કરીને સહાયક વૃક્ષને પણ વધારીએ છીએ. એલ્ગોરિધમ શોધ ટેંગો વૃક્ષમાં કોઈ તત્વ શોધવા માટે, આપણે ફક્ત સંદર્ભ વૃક્ષને શોધવાનું અનુકરણ કરીએ છીએ. આપણે મૂળ સાથે જોડાયેલા પસંદગીના માર્ગને શોધીને શરૂઆત કરીએ છીએ, જે તે પસંદગીના માર્ગને અનુરૂપ સહાયક વૃક્ષને શોધીને અનુકરણ કરવામાં આવે છે. જો સહાયક વૃક્ષમાં ઇચ્છિત તત્વ ન હોય, તો શોધ ઇચ્છિત તત્વ (અન્ય પસંદગીના માર્ગની શરૂઆત) ધરાવતા પેટા વૃક્ષના મૂળના મૂળ પર સમાપ્ત થાય છે, તેથી આપણે ફક્ત તે પસંદગીના માર્ગ માટે સહાયક વૃક્ષને શોધીને આગળ વધીએ છીએ, વગેરે. અપડેટ કરવું ટેંગો વૃક્ષની રચના જાળવવા માટે (સહાયક વૃક્ષો પસંદગીના માર્ગોને અનુરૂપ છે), જ્યારે પણ પસંદગીના બાળકો શોધના પરિણામે બદલાય છે ત્યારે આપણે કેટલાક અપડેટ કરવાનું કામ કરવું જોઈએ. જ્યારે પસંદગીનું બાળક બદલાય છે, ત્યારે પસંદગીના માર્ગનો ટોચનો ભાગ નીચેના ભાગથી અલગ થઈ જાય છે (જે તેનો પોતાનો પસંદગીનો માર્ગ બની જાય છે) અને બીજા પસંદગીના માર્ગ સાથે જોડાઈ જાય છે (જે નવો નીચેનો ભાગ બની જાય છે). આને અસરકારક રીતે કરવા માટે, અમે અમારા સહાયક વૃક્ષો પર કટ અને જોઇન કામગીરીને વ્યાખ્યાયિત કરીશું. અમારા જોડાઓ ઓપરેશનમાં જોડાઓ બે સહાયક વૃક્ષોને ત્યાં સુધી જોડશે જ્યાં સુધી તેમની પાસે એવી મિલકત હોય કે એકનો ટોચનો નોડ (સંદર્ભ વૃક્ષમાં) બીજાના તળિયાના નોડનો ચાઈલ્ડ હોય (આવશ્યકપણે, કે અનુરૂપ પસંદગીના માર્ગોને જોડી શકાય છે). આ લાલ-કાળા વૃક્ષોની સંયોજિત કામગીરીના આધારે કામ કરશે, જે બે વૃક્ષોને જોડે છે, જ્યાં સુધી તેમની પાસે મિલકત છે કે એકના તમામ ઘટકો બીજાના તમામ ઘટકો કરતા ઓછા છે, અને વિભાજિત થાય છે, જે વિપરીત કરે છે. સંદર્ભ વૃક્ષમાં, નોંધ લો કે ટોચના માર્ગમાં બે નોડ્સ અસ્તિત્વ ધરાવે છે જેમ કે નોડ તળિયાના માર્ગમાં હોય જો અને માત્ર ત્યારે જ જો તેની કી-વેલ્યુ તેમની વચ્ચે હોય. હવે, ટોચના માર્ગના તળિયાના માર્ગને જોડવા માટે, આપણે ફક્ત તે બે ગાંઠો વચ્ચેના ટોચના માર્ગને વિભાજિત કરીએ છીએ, પછી નીચેના માર્ગના સહાયક વૃક્ષની બંને બાજુએ બે પરિણામી સહાયક વૃક્ષોને જોડીએ છીએ, અને આપણી પાસે આપણું અંતિમ, જોડાયેલ સહાયક વૃક્ષ છે. આપણી કટ કામગીરી પસંદગીના માર્ગને આપેલ નોડ પર બે ભાગોમાં વિભાજિત કરશે, ટોચનો ભાગ અને નીચેનો ભાગ. વધુ ઔપચારિક રીતે, તે સહાયક વૃક્ષને બે સહાયક વૃક્ષોમાં વિભાજિત કરશે, જેમ કે એક સંદર્ભ વૃક્ષમાં ચોક્કસ ઊંડાઈ પર અથવા તેની ઉપરના તમામ ગાંઠો ધરાવે છે, અને બીજામાં તે ઊંડાઈની નીચે તમામ ગાંઠો હોય છે. જોઇનની જેમ, નોંધ લો કે ટોચના ભાગમાં બે નોડ્સ છે જે નીચેના ભાગને કૌંસ કરે છે. આમ, આપણે માર્ગને ત્રણ ભાગોમાં વિભાજિત કરવા માટે આ બે ગાંઠોમાંથી દરેકને સરળતાથી વિભાજિત કરી શકીએ છીએ, પછી બે બાહ્ય ગાંઠોને જોડી શકીએ છીએ જેથી આપણે ઇચ્છા મુજબ ઉપર અને નીચે બે ભાગો સાથે અંત લાવી શકીએ. વિશ્લેષણ ટેંગો વૃક્ષો માટે સ્પર્ધાત્મક ગુણોત્તરને બાંધવા માટે, આપણે શ્રેષ્ઠ ઓફલાઇન વૃક્ષની કામગીરી પર નીચી મર્યાદા શોધવી જોઈએ જેનો આપણે બેન્ચમાર્ક તરીકે ઉપયોગ કરીએ છીએ. એકવાર આપણે ટેંગો વૃક્ષની કામગીરી પર ઉપલી સીમા શોધી લઈએ, પછી આપણે તેમને સ્પર્ધાત્મક ગુણોત્તરમાં વિભાજિત કરી શકીએ છીએ. ઇન્ટરલીવ બાઉન્ડ શ્રેષ્ઠ ઓફલાઇન દ્વિસંગી શોધ વૃક્ષ દ્વારા કરવામાં આવેલા કાર્ય પર નીચી સીમા શોધવા માટે, આપણે ફરીથી પસંદગીના બાળકોની કલ્પનાનો ઉપયોગ કરીએ છીએ. એક્સેસ સિક્વન્સ (શોધોનો ક્રમ) ધ્યાનમાં લેતી વખતે, આપણે સંદર્ભ વૃક્ષ નોડની પસંદગીની ચાઈલ્ડ કેટલી વાર સ્વિચ કરે છે તેનું ધ્યાન રાખીએ છીએ. સ્વીચોની કુલ સંખ્યા (તમામ નોડ્સ પર સારાંશિત) આપેલ એક્સેસ ક્રમ પર કોઈપણ દ્વિસંગી શોધ વૃક્ષ અલ્ગોરિધમ દ્વારા કરવામાં આવેલા કાર્ય પર એસિમ્પ્ટોટિક લોઅર બાઉન્ડ આપે છે. આને ઇન્ટરલીવ લોઅર બાઉન્ડ કહેવામાં આવે છે. ટેંગો વૃક્ષ આને ટેંગો વૃક્ષો સાથે જોડવા માટે, આપણને આપેલ પ્રવેશ ક્રમ માટે ટેંગો વૃક્ષ દ્વારા કરવામાં આવેલા કાર્ય પર ઉપરની સીમા મળશે. આપણી ઉપરની સીમા હશે, જ્યાં k એ આંતરપત્રોની સંખ્યા છે. કુલ ખર્ચને બે ભાગમાં વહેંચવામાં આવે છે, તત્વની શોધ કરવી અને યોગ્ય અપરિવર્તન જાળવવા માટે ટેંગો વૃક્ષની રચનાને અપડેટ કરવી (પસંદગીના બાળકોને બદલવા અને પસંદગીના માર્ગોને ફરીથી ગોઠવવા). શોધ એ જોવા માટે કે શોધ (અપડેટ ન કરવી) આ બાઉન્ડમાં બંધબેસે છે, ફક્ત નોંધ લો કે દર વખતે જ્યારે સહાયક વૃક્ષની શોધ અસફળ થાય છે અને આપણે આગામી સહાયક વૃક્ષ પર જવું પડે છે, જે પસંદગીના ચાઇલ્ડ સ્વિચમાં પરિણમે છે (કારણ કે માતાપિતા પસંદગીનો પાથ હવે બાળક પસંદગીના પાથમાં જોડાવા માટે દિશાઓ સ્વિચ કરે છે). છેલ્લા વૃક્ષ સિવાયની તમામ સહાયક વૃક્ષ શોધ અસફળ હોવાથી (એકવાર શોધ સફળ થાય તે પછી આપણે સ્વાભાવિક રીતે અટકી જઈએ છીએ), આપણે સહાયક વૃક્ષોની શોધ કરીએ છીએ. દરેક શોધ લે છે, કારણ કે સહાયક વૃક્ષનું કદ સંદર્ભ વૃક્ષની ઊંચાઈથી બંધાયેલું છે. અપડેટ કરવાની કિંમત પણ આ મર્યાદામાં બંધબેસે છે, કારણ કે આપણે દરેક મુલાકાત લીધેલા સહાયક વૃક્ષ માટે માત્ર એક કટ અને એક જોઇન કરવું પડશે. એક જ કટ અથવા જોઇન ઓપરેશનમાં માત્ર સતત સંખ્યાબંધ શોધો, સ્પ્લિટ્સ અને કોન્કેટેનેટ્સ લે છે, જેમાંથી દરેક સહાયક વૃક્ષના કદમાં લઘુગણક સમય લે છે, તેથી અમારો અપડેટ ખર્ચ છે. સ્પર્ધાત્મક ગુણોત્તર ટેંગો વૃક્ષો-સ્પર્ધાત્મક છે, કારણ કે શ્રેષ્ઠ ઓફલાઇન દ્વિસંગી શોધ વૃક્ષ દ્વારા કરવામાં આવેલું કાર્ય ઓછામાં ઓછું k માં રેખીય છે (પસંદગીના બાળ સ્વીચની કુલ સંખ્યા), અને ટેંગો વૃક્ષ દ્વારા કરવામાં આવેલું કાર્ય સૌથી વધુ છે. પ્લે વૃક્ષ શ્રેષ્ઠ દ્વિસંગી શોધ વૃક્ષ લાલ-કાળા વૃક્ષ (માહિતી માળખું) સંદર્ભો દ્વિસંગી વૃક્ષો શોધ વૃક્ષો