डिटरमिनिस्टिक सर्च ट्रीज़ (Deterministic Search Trees) के दो रैंडमाइज़्ड विकल्प रैंडमाइज़्ड बाइनरी सर्च ट्रीज़, ट्रेप्स (Treaps) और स्किप लिस्ट्स (Skip Lists) हैं। ट्रेप्स और स्किप लिस्ट्स दोनों को सुरुचिपूर्ण डेटा स्ट्रक्चर (Elegant Data Structures) के रूप में परिभाषित किया जाता है, जहां रैंडमाइज़ेशन सरल और कुशल अपडेट ऑपरेशन्स की सुविधा देता है।
इस खंड में हम बताते हैं कि कैसे ट्रेप्स और स्किप लिस्ट्स दोनों को डेटा स्ट्रक्चर को बदले बिना कुशल फिंगर सर्च ट्रीज़ के रूप में लागू किया जा सकता है। दोनों डेटा स्ट्रक्चर फिंगर सर्च का समर्थन अपेक्षित O(log d) समय में करते हैं, जहां अपेक्षाएं डेटा स्ट्रक्चर के निर्माण के दौरान एल्गोरिदम द्वारा किए गए रैंडम विकल्पों पर ली जाती हैं।
स्किप लिस्ट्स (Skip Lists)
स्किप लिस्ट में, कोई एलिमेंट a के लिए नोड से जिसमें एलिमेंट b है, फिंगर सर्च कर सकता है बस इस बिंदु से खोज जारी रखकर। ध्यान दें कि यदि a < b, तो खोज पिछड़े दिशा में आगे बढ़ती है, और यदि a > b, तो खोज आगे की दिशा में आगे बढ़ती है। पिछड़ा हुआ केस स्किप लिस्ट में सामान्य खोज के सममित है, लेकिन आगे का केस वास्तव में अधिक जटिल है। आम तौर पर, स्किप लिस्ट में खोज तेज होने की उम्मीद है क्योंकि सूची की शुरुआत में सेंटिनल को सबसे लंबा नोड माना जाता है। हालांकि, हमारी फिंगर ऊंचाई 1 के नोड से जुड़ी हो सकती है। इसके कारण, हम खोज करने की कोशिश करते हुए शायद ही कभी चढ़ते हैं; ऐसा कुछ जो सामान्य रूप से कभी नहीं होता। हालांकि, इस जटिलता के साथ भी, हम O(log d) अपेक्षित खोज समय प्राप्त करने में सक्षम हैं।
ट्रेप्स (Treaps)
ट्रेप (Treap) को एक रैंडमाइज़्ड बाइनरी सर्च ट्री (Randomized Binary Search Tree - BST) के रूप में परिभाषित किया जाता है। ट्रेप में खोज किसी अन्य BST में एलिमेंट खोजने के समान है। ट्रेप्स में हालांकि यह गुण होता है कि दूरी d के दो एलिमेंट्स के बीच अपेक्षित पथ लंबाई (Expected Path Length) O(log d) होती है। इस प्रकार, एलिमेंट b वाले नोड से एलिमेंट a के लिए फिंगर सर्च करने के लिए, कोई b एलिमेंट से ट्री पर तब तक चढ़ सकता है जब तक एलिमेंट a का पूर्वज (Ancestor) न मिल जाए, जिस बिंदु पर सामान्य BST खोज सामान्य तरीके से आगे बढ़ती है। जबकि यह गणना करना कि क्या एक नोड दूसरे का पूर्वज है, गैर-तुच्छ है, कोई ट्री को इस रूप के क्वेरी का समर्थन करने के लिए बढ़ा सकता है ताकि अपेक्षित O(log d) फिंगर सर्च समय प्रदान किया जा सके।
