- एक गतिशील उंगली खोज डेटा संरचना को अंगुलियों की खोज के अलावा उंगली द्वारा दी गई स्थिति में तत्वों को सम्मिलित करना और हटाना भी करना चाहिए।
- उंगली खोज ट्री को O(log d) समय में उंगलियों की खोज का समर्थन करने वाले B-पेड़ों के एक प्रकार के रूप में परिभाषित किया गया है और O(1) समय में अपडेट किया जाता है, यह मानते हुए कि केवल O(1) चलने योग्य उंगलियों को बनाए रखा जाता है।
- एक उंगली d स्थिति को पार करने के लिए O(log d) समय की आवश्यकता होती है।
- फिंगर सर्च ट्री (अर्थात एवीएल-पेड़, लाल-काले पेड़) निर्माण या तो अंगुलियों की एक निश्चित संख्या पर विचार करते हैं या केवल परिशोधित स्थिर समय में अपडेट का समर्थन करते हैं।
- अंगुलियों की मनमानी संख्या का समर्थन करने वाले और सबसे खराब स्थिति वाले अपडेट बनाए गए हैं।
- एक खोज ट्री जो सबसे खराब स्थिति में O(1) समय में एक मनमाना स्थिति में अपडेट का समर्थन करता है, लेकिन केवल O(log n) समय में खोजों का समर्थन करता है।
- ओ (लॉग डी) समय खोजों और ओ (लॉग डी एन) समय सम्मिलन और हटाने का समर्थन करने वाले निर्माण।
- फिंगर सर्च ट्री सबसे खराब स्थिति वाले निरंतर समय सम्मिलन और O(log d n) समय विलोपन का उपभोग करते हैं।
- लिंक्ड (2,4)-पेड़ों के लिए एक अंतरिक्ष कुशल वैकल्पिक समाधान के अनुसार, एक उंगली की अनुमति है, जिसे (2,4)-पेड़ों के समान प्रदर्शन लागत से आगे बढ़ाया जा सकता है। समाधान में किसी भी स्तर के लिंक और पैरेंट पॉइंटर्स की आवश्यकता नहीं होती है, इसके बजाय उंगली के लिए एक विशेष ओ (लॉग एन) स्पेस डेटा संरचना, हाथ बनाया जाता है जो उंगली को कुशलता से पार करने की अनुमति देता है।
- स्प्ले ट्री को स्व-समायोजन बाइनरी सर्च ट्री के एक वर्ग के रूप में परिभाषित किया गया है जो परिशोधन ओ (लॉग एन) समय में खोजों, सम्मिलन और विलोपन का समर्थन करता है। उस स्प्ले ट्री को कुशल फिंगर सर्च ट्री के रूप में लागू किया जा सकता है।
- एक O(n) आरंभीकरण लागत को देखते हुए, एक स्प्ले ट्री में पिछली पहुंच से दूरी d पर पहुंच की परिशोधित लागत O(log d) है जहां एक्सेस में खोज, सम्मिलन और विलोपन शामिल हैं।
- ध्यान दें कि कथन केवल एक उंगली की उपस्थिति में लागू होता है, जो हमेशा अंतिम एक्सेस किए गए तत्व की ओर इशारा करता है।
- उपरोक्त सभी निर्माण एक पॉइंटर मशीन पर लागू किए जा सकते हैं जहां तत्वों पर केवल दो तत्वों की तुलना की अनुमति है।
- कम्प्यूटेशन (रैम) के रैंडम एक्सेस मशीन मॉडल के लिए, निरंतर अद्यतन समय और ओ (लॉग डी) खोज समय के साथ एक फिंगर सर्च ट्री विकसित किया गया है। यह परिणाम छोटे वृक्ष संरचनाओं को सारणीबद्ध करके प्राप्त किया जाता है, लेकिन केवल तत्वों की तुलना करता है।
