सिपल के पेड़

एक संतुलित खोज वृक्ष कई आधुनिक एल्गोरिदम की नींव है। कंप्यूटर साइंस की किताबों के पन्नों पर आपको लाल-काले, एवीएल-, बी- और कई अन्य संतुलित पेड़ों के विवरण मिलेंगे। लेकिन स्थायी संतुलन के लिए पवित्र कंघी बनानेवाले की रेती का पीछा किया जाता है?

कल्पना कीजिए कि हम पहले ही एक पेड़ का निर्माण कर चुके हैं चाबियाँ और अब हमें अनुरोधों का जवाब देने की आवश्यकता है कि क्या दी गई कुंजी पेड़ में निहित है। यह पता चल सकता है कि उपयोगकर्ता मुख्य रूप से एक कुंजी में रुचि रखता है, और वह केवल समय-समय पर बाकी के लिए पूछता है। यदि कुंजी जड़ से दूर है, तो अनुरोध दूर ले जा सकते हैं समय। सामान्य ज्ञान यह निर्धारित करता है कि स्कोर को अनुकूलित किया जा सकता है पेड़ पर एक कैश जोड़कर। लेकिन इस दृष्टिकोण में लचीलापन और लालित्य की कुछ कमी है।

आज मैं स्प्ले पेड़ों के बारे में बात करूंगा। ये पेड़ स्थायी रूप से संतुलित नहीं हैं और यहां तक ​​कि रैखिक समय भी अलग-अलग अनुरोधों पर काम कर सकते हैं। हालांकि, प्रत्येक अनुरोध के बाद, वे अपनी संरचना बदलते हैं, जो बहुत बार दोहराया अनुरोधों को संसाधित करने की अनुमति देता है। इसके अलावा, उनसे एक अनुरोध को संसाधित करने की मूल्यह्रास लागत , जो स्थायी रूप से संतुलित समकक्षों के लिए स्प्ले पेड़ों को एक अच्छा विकल्प बनाता है।

सिपल के पेड़

अस्सी के दशक के मध्य में, रॉबर्ट टारजन और डैनियल स्लेटर ने कुछ सुंदर और कुशल डेटा संरचनाओं का प्रस्ताव रखा। उन सभी के पास एक सरल बुनियादी संरचना और एक या दो उत्तराधिकार हैं जो उन्हें स्थानीय रूप से लगातार सही करते हैं। सिपेल ट्री एक ऐसी संरचना है।

सेप ट्री एक सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री है। पेड़ को किसी भी अतिरिक्त जानकारी को संग्रहीत करने की आवश्यकता नहीं है, जो इसे स्मृति कुशल बनाता है। प्रत्येक कॉल के बाद, यहां तक ​​कि एक खोज, स्प्ले ट्री अपनी संरचना को बदलता है।

नीचे मैं एल्गोरिथ्म का वर्णन करूँगा कि पेड़ जोड़ीदार विभिन्न कुंजियों के सेट पर कैसे काम करता है, और फिर मैं इसका विश्लेषण करूंगा।

एल्गोरिथ्म

पेड़ की संरचना का वर्णन करने के लिए, हमें एक सरल वर्ग की आवश्यकता है जो एक ही शीर्ष का वर्णन करता है,

class Node: def __init__(self, key, left = None, right = None, parent = None): self.left = left self.right = right self.parent = parent self.key = key 

और माता-पिता के लिए संकेत के साथ काम करने के लिए दो सहायक प्रक्रियाएं।

 def set_parent(child, parent): if child != None: child.parent = parent def keep_parent(v): set_parent(v.left, v) set_parent(v.right, v) 

एक स्प्ले ट्री का मुख्य हेयुरिस्टिक मूव-टू-रूट है। किसी भी शीर्ष पर पहुंचने के बाद, यह जड़ तक बढ़ जाता है। चढ़ाई को चोटियों के मोड़ के माध्यम से महसूस किया जाता है। एक बारी में, आप बच्चे के साथ माता-पिता को स्वैप कर सकते हैं, जैसा कि नीचे दिए गए आंकड़े में दिखाया गया है।

 def rotate(parent, child): gparent = parent.parent if gparent != None: if gparent.left == parent: gparent.left = child else: gparent.right = child if parent.left == child: parent.left, child.right = child.right, parent else: parent.right, child.left = child.left, parent keep_parent(child) keep_parent(parent) child.parent = gparent 

लेकिन सिर्फ शीर्ष को तब तक मोड़ना जब तक वह जड़ नहीं बन जाता। स्प्ले ट्री की चाल यह है कि जब आप वर्टेक्स को ऊपर ले जाते हैं, तो रूट की दूरी न केवल वर्टेक्स को उठाए जाने के लिए कम हो जाती है, बल्कि इसके सभी वंशजों के लिए वर्तमान सबट्रेक्ट्स में हो जाती है। इसके लिए, ज़िग-ज़िग और ज़िग-ज़ैग कॉर्नरिंग तकनीकों का उपयोग किया जाता है।

ज़िग-ज़िग और ज़िग-ज़ैग का मूल विचार दादा से बच्चे तक के मार्ग पर विचार करना है। यदि रास्ता केवल बाएं बच्चों के साथ या केवल दाईं ओर जाता है, तो इस स्थिति को zig-zig कहा जाता है। इसे कैसे संसाधित किया जाए यह नीचे दिए गए आंकड़े में दिखाया गया है। पहले माता-पिता की बारी, फिर बच्चे की।



अन्यथा, हम पहले बच्चे को वर्तमान माता-पिता के साथ बदलते हैं, फिर एक नए के साथ।



यदि शीर्ष पर कोई दादा नहीं है, तो हम सामान्य मोड़ लेते हैं:



ऊपर वर्णित ज़िग-ज़िग और ज़िग-ज़ैग टर्न का उपयोग करके वर्टेक्स को ऊपर उठाने की प्रक्रिया स्प्ले ट्री की कुंजी है।

नोट। रूसी में, शब्द "स्प्ले" का अनुवाद "विस्तार" के रूप में किया गया था। मुझे लगता है कि यह बहुत अच्छा अनुवाद नहीं है। आप शीर्ष लेते हैं और इसे ऊपर खींचते हैं। इस समय, अन्य सभी चोटियां नीचे की ओर मुड़ जाती हैं। कुछ ऐसा ही होता है जब आप एक टी-शर्ट को ट्विस्ट करते हैं। इसलिए शब्द "ट्विस्ट" यहां अधिक उचित लगता है।

 def splay(v): if v.parent == None: return v parent = v.parent gparent = parent.parent if gparent == None: rotate(parent, v) return v else: zigzig = (gparent.left == parent) == (parent.left == v) if zigzig: rotate(gparent, parent) rotate(parent, v) else: rotate(parent, v) rotate(gparent, v) return splay(v) 

स्प्ले ट्री में खोज प्रक्रिया सामान्य से भिन्न होती है केवल अंतिम चरण में: वर्टेक्स पाए जाने के बाद, हम इसे ऊपर खींचते हैं और splay प्रक्रिया के माध्यम से इसे जड़ बनाते हैं।

 def find(v, key): if v == None: return None if key == v.key: return splay(v) if key < v.key and v.left != None: return find(v.left, key) if key > v.key and v.right != None: return find(v.right, key) return splay(v) 

मुख्य प्रविष्टि और विलोपन को लागू करने के लिए, हमें दो प्रक्रियाओं की आवश्यकता होती है: split और merge (कट और मर्ज)।

split प्रक्रिया एक key को इनपुट के रूप में प्राप्त करती है और पेड़ को दो में विभाजित करती है। एक पेड़ में, सभी मूल्य key से कम हैं, और दूसरे में, अधिक है। इसे सरलता से लागू किया जाता है। आपको कुंजी के सबसे करीब find शीर्ष को find माध्यम से find जरूरत है, इसे बढ़ाएं और फिर बाएं या दाएं सबट्री (या दोनों) को काट दें।

 def split(root, key): if root == None: return None, None root = find(root, key) if root.key == key: set_parent(root.left, None) set_parent(root.right, None) return root.left, root.right if root.key < key: right, root.right = root.right, None set_parent(right, None) return root, right else: left, root.left = root.left, None set_parent(left, None) return left, root 

अगली कुंजी सम्मिलित करने के लिए, उस पर split कॉल करने के लिए पर्याप्त है, और फिर एक नया शीर्ष-रूट बनाएं, जिसमें उप- split का परिणाम होगा।

 def insert(root, key): left, right = split(root, key) root = Node(key, left, right) keep_parent(root) return root 

merge प्रक्रिया इनपुट पर दो पेड़ प्राप्त करती है: बाएं left और दाएं right । सही संचालन के लिए, left पेड़ की चाबी right पेड़ की चाबी से छोटी होनी चाहिए। यहां हम सही पेड़ की सबसे छोटी कुंजी के साथ शीर्ष को लेते हैं और इसे ऊपर खींचते हैं। उसके बाद, बाएं सबट्री के रूप में, left पेड़ से जुड़ें।

 def merge(left, right): if right == None: return left if left == None: return right right = find(right, left.key) right.left, left.parent = left, right return right 

एक शीर्ष को हटाने के लिए, आपको इसे ऊपर उठाने की आवश्यकता है, और फिर इसके बाएं और दाएं उप-मर्ज को मर्ज करें।

 def remove(root, key): root = find(root, key) set_parent(root.left, None) set_parent(root.right, None) return merge(root.left, root.right) 

डुप्लिकेट कुंजियों का समर्थन करने के लिए स्प्ले ट्री के लिए, ऐसा करने के दो तरीके हैं। आवश्यक कुंजी को संग्रहीत करने वाली प्रत्येक कुंजी को सूची में जोड़ना आवश्यक है। जानकारी, या खोज प्रक्रिया को लागू करें ताकि यह LUR ट्रैवर्सल ऑर्डर में पहले वर्टेक्स को दिए गए कुंजी के बराबर या उससे अधिक के साथ लौटाए।

के विश्लेषण

ध्यान दें कि पेड़ों को हटाने, डालने, विलय करने और विभाजित करने के लिए काम करते हैं find प्रक्रिया का + क्रम।

find प्रक्रिया पेड़ में वांछित शीर्ष की गहराई के अनुपात में काम करती है। जब खोज splay , तो splay प्रक्रिया splay , जो कि शीर्ष की गहराई के अनुपात में भी काम करती है। इस प्रकार, यह splay प्रक्रिया के चल रहे समय का मूल्यांकन करने के लिए पर्याप्त है।

विश्लेषण के लिए, हम भौतिक विज्ञानी विधि का उपयोग करते हैं, जिसके बारे में मैंने मूल्यह्रास विश्लेषण के बारे में एक लेख में बात की थी। चलो - उप-आकार शीर्ष पर जड़ के साथ । शीर्ष रैंक हम मात्रा कहते हैं । हमारी क्षमता होगी ।

हम मानते हैं कि splay(v) प्रक्रिया का वास्तविक समय गहराई के बराबर है कोने । ध्यान दें कि यह प्रक्रिया के दौरान किए जाने वाले प्राथमिक घुमावों की संख्या के बराबर भी है।

कथन । शीर्ष से splay ऑपरेशन का परिशोधन लागत एक पेड़ में जड़ के साथ बनाता है ।

प्रमाण
अगर - जड़, तो कथन स्पष्ट है। अन्यथा, प्रक्रिया splay(v) को चरणों में विभाजित करें। प्रत्येक चरण के दौरान, तीन में से एक मोड़ किया जाता है: zig, zig-zig, या zig-zag। समय की एक इकाई को एक साधारण मोड़ पर, दो इकाइयों को जिग-ज़िग और ज़िग-ज़ैग पर खर्च किया जाता है।

प्रत्येक चरण के बाद, शीर्ष की रैंक बदल जाएगा। प्रारंभिक रैंक होने दें और उसके बाद स्टेज एक - । प्रत्येक चरण के लिए, शायद, अंतिम, को छोड़कर, हम दिखाते हैं कि इसके कार्यान्वयन के लिए मूल्यह्रास का समय ऊपर से सीमित हो सकता है । अंतिम चरण के लिए, ऊपरी सीमा होगी । ऊपरी सीमा को सममित करना और रैंकों के मध्यवर्ती मूल्यों को कम करना, हम आवश्यक प्राप्त करते हैं



आपको बस उस पर ध्यान देने की आवश्यकता है , और ।

अब हम प्रत्येक प्रकार के रोटेशन का अलग-अलग विश्लेषण करेंगे।

Zig। इसे केवल एक बार, अंतिम चरण में किया जा सकता है। वास्तविक समय । आइए आकृति को देखें और समझें कि रैंक केवल कोने पर बदलती हैं और ।



तो, मूल्यह्रास लागत होगी । रैंक और घट रहे हैं। संबंधित उपप्रकारों के आकार के आधार पर, हम सूत्र पर लागू होते हैं असमानता:



इसलिए, ।

Zig-zig। वास्तविक समय । ध्यान दें कि रैंक केवल कोने पर बदलते हैं । और ।



फिर मूल्यह्रास लागत । रैंक और छोटा किया जा सकता है। हमें वह मिलता है । उपप्रकारों के आकार के आधार पर, हम सूत्र पर लागू होते हैं दो असमानताएँ:



और मिलता है ।

हमारा लक्ष्य यह दिखाना है कि । इसके लिए यह दिखाना पर्याप्त है :



सुविधा के लिए, हम रैंक को बाईं ओर स्थानांतरित करेंगे और हम साबित करेंगे । रैंक की परिभाषा से । अंतिम समानता । आइए आकृति को देखें और समझें ।

तथ्य यह है। किसी भी सकारात्मक के लिए ऐसा है ।

इसलिए, । आवश्यक हो गया।

Zig-zag।



पिछले मामले के समान, हम मूल्यह्रास का अनुमान लिखते हैं: ।

रैंक और घट रहे हैं। सूत्र को हम निम्नलिखित असमानताओं को लागू करते हैं:



इसलिए, । यह असमानता पिछले मामले के समान साबित होती है।

इस प्रकार, हमने तीनों मामलों का विश्लेषण किया और रैंक के माध्यम से परिशोधन समय के लिए एक ऊपरी अनुमान प्राप्त किया।

यह ध्यान देने योग्य है कि किसी भी शीर्ष की रैंक पेड़ के आकार के लघुगणक द्वारा सीमित है। जिसमें से निम्नलिखित प्रमेय निम्नानुसार हैं।

प्रमेय। splay मूल्यह्रास किया गया है ।

अन्य मैट्रिक्स और गुण

मिष्ठान के लिए, मैं विकिपीडिया का उल्लेख करना चाहूंगा और यहाँ कुछ दिलचस्प तथ्य प्रस्तुत करूंगा।

स्थैतिक इष्टतम प्रमेय । चलो - आइटम की संख्या का अनुरोध किया गया था । फिर कर रहे हैं एक splay पेड़ पर खोज क्वेरी में चलता है ।

वास्तव में, यह तथ्य निम्नलिखित रिपोर्ट करता है। आइए पहले से जानते हैं कि विभिन्न तत्वों के लिए कितने प्रश्न पूछे जाएंगे। हम इन अनुरोधों का यथाशीघ्र उत्तर देने के लिए एक विशिष्ट बाइनरी ट्री का निर्माण कर रहे हैं। बयान में कहा गया है कि, splay स्थिरांक के लिए सटीक splay पेड़ सबसे इष्टतम निश्चित पेड़ की तुलना में कोई बदतर नहीं होगा जो हम सोच सकते हैं।

वर्तमान सेट पर प्रमेय । चलो - यह उन अनुरोधों की संख्या है जो हमने पहले ही तत्व के अंतिम अनुरोध के बाद से की है ; यदि आपने अभी तक संबोधित नहीं किया है, तो बस शुरुआत से ही अनुरोधों की संख्या। फिर समय प्रसंस्करण अनुरोध होंगे ।

यह तथ्य लेख की शुरुआत में कैश की मेरी चर्चा को औपचारिक बनाता है। वास्तव में, उनका कहना है कि औसतन, हाल ही में अनुरोध की गई वस्तु जड़ से दूर नहीं जाती है।

स्कैनिंग प्रमेय अनुक्रमिक पहुँच (LUR) में एक splay तत्वों का प्रदर्शन किया जाता है ।

इस तथ्य का एक महान व्यावहारिक परिणाम है। विभाजन और मर्ज के संचालन के साथ, यह splay पेड़ों को rope डेटा संरचनाओं के लिए एक उत्कृष्ट आधार बनाता है। आप इसके बारे में अधिक पढ़ सकते हैं - हैबर रोप्स के पदों में - तेज लाइनें और मोनॉयड और उनके अनुप्रयोग ...।

आपका ध्यान के लिए धन्यवाद!

साहित्य

• टारजन "डेटा संरचनाएं और नेटवर्क एल्गोरिदम"
• स्लेटोर, डैनियल डी।; टारजन, रॉबर्ट ई। (1985), "सेल्फ-एडजस्टिंग बाइनरी सर्च ट्रीज़"

यूपीडी

एक नोट पर उपयोगितावाद

व्यवहार में इस एल्गोरिथ्म की प्रयोज्यता के बारे में टिप्पणियों में एक उचित प्रश्न है। इसका उत्तर देने से पहले, मैं यह नोट करना चाहता हूं कि यह पोस्ट सबसे पहले पाठक को एल्गोरिथम और उसकी सैद्धांतिक नींव से परिचित कराती है। इस कारण से, प्रभावी कार्यान्वयन, विवरण और अनुकूलन के बारे में प्रश्न, जिनमें से कई हैं, मैं लेख से बाहर निकल गया।

एक दर्जन लेखों के लिए इस विषय का अध्ययन किया गया। "सिस्टम सॉफ्टवेयर में BST के प्रदर्शन विश्लेषण" की Pfaff समीक्षा, जिसमें नोड्स के विभिन्न आंतरिक अभ्यावेदन के साथ 20 संतुलित पेड़ों की तुलना की जाती है, बहुत आशावादी लगता है। वर्चुअल मेमोरी को प्रबंधित करने, आईपी पैकेट को कैच करने और क्रॉस-रेफरेंस को हल करने के कार्यों के लिए वास्तविक डेटा पर परीक्षण किया जाता है। वर्चुअल मेमोरी और क्रॉस-रेफरेंस पर, शानदार पेड़ों ने सबसे अच्छा प्रदर्शन किया; आईपी ​​पैकेट ने एवीएल और लाल-काले पेड़ों को रास्ता दिया। उच्च प्रदर्शन को वास्तविक डेटा की विशेषता द्वारा समझाया गया है। अध्ययन का विवरण लेख में ही पढ़ा जाता है।

आप टिमई अहो और आदि द्वारा "टाइमिंग एपिंग और वर्किंग सेट्स के लाभ" लेख में घुमावों की संख्या को कम करने के मुद्दे पर विस्तार से रिपोर्ट पढ़ सकते हैं । लेख के अंत में ग्रंथ सूची में कई और प्रदर्शन रिपोर्ट हैं।