महत्वपूर्ण द्विआधारी खोज वृक्षों का क्रियात्मक सार

द्विआधारी खोज वृक्षों को पुनर्संरचना करने वाले एल्गोरिदम प्रायः महत्वपूर्ण छद्म कोड में प्रस्तुत किए जाते हैं। यह समझ में आता है, क्योंकि इनका प्रदर्शन इन-प्लेस क्रिया पर निर्भर करता है, न कि मेमोरी में नए नोड आवंटित करने पर। दुर्भाग्यवश, ये महत्वपूर्ण एल्गोरिदम सत्यापित करना notoriously कठिन होते हैं क्योंकि उनके लूप अविवेचन अधूरे वृक्ष खंडों से जुड़े होते हैं जिन्हें पुनर्मात्रा किया जा रहा होता है। इस पेपर में पुनर्संरचनित द्विआधारी खोज वृक्ष में तत्वों को एक्सेस और सम्मिलित करने के लिए कई नए कार्यात्मक एल्गोरिदम प्रस्तुत किए गए हैं जो अपने महत्वपूर्ण समकक्षों के समान तेजी से होते हैं; फिर भी, इन कार्यात्मक एल्गोरिदम की सटीकता एक सरल इन्क्रिमेंटल तर्क का उपयोग करके स्थापित की गई है। प्रत्येक डेटा संरचना, मूव-टू-रूट, स्प्ले और ज़िप वृक्ष के लिए, यह पेपर ज़िपर्स का उपयोग करके एक नीचे से ऊपर एल्गोरिदम और एक शीर्ष से नीचे एल्गोरिदम का वर्णन करता है जो एक नए पहले श्रेणी के कंस्ट्रक्टर संदर्भ प्राइमिटिव का उपयोग करता है। कार्यात्मक और महत्वपूर्ण एल्गोरिदम तुलनीय हैं: हम Coq प्रमाण सहायक में इसको स्थापित करने वाले प्रमाणों को यांत्रिक बनाते हैं जो Iris फ्रेमवर्क का उपयोग करते हैं। यह द्विआधारी खोज वृक्षों पर प्रसिद्ध एल्गोरिदम का पहला पूरी तरह से सत्यापित कार्यान्वयन प्रदान करता है जिसकी प्रदर्शन C में सबसे तेज कार्यान्वयन के समान है।