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