सबूत यह है कि ये रोटेशन चाल पूरे बाइनरी पेड़ खोज स्थान - पेड़, सिद्धांत, सबूत, औपचारिक सत्यापन का पता लगा सकते हैं

मैं इस परियोजना पर काम कर रहा हूं जहां मुझे निम्नलिखित के लिए सैद्धांतिक प्रमाण खोजने की आवश्यकता है।

मेरे पास एक विशेष प्रकार के बाइनरी ट्री हैं, जहां

1) प्रत्येक आंतरिक नोड में निश्चित रूप से दो बच्चे होंगे।

2) एन लीफ नोड्स हैं और क्रम 1 से n में सबसे बाएं से दाएं सबसे ऊपर माना जा सकता है।

अब यह स्पष्ट है कि ऐसे संभावित पेड़ों की घातीय संख्या होगी, जिनमें दो गुण हैं।

अगर मैं किसी भी यादृच्छिक पेड़ से शुरू करता हूं और बेतरतीब ढंग से नमूने का एक आंतरिक नोड दो ऑपरेशनों में से एक लेफ्ट रोटेट या राइट रोटेट (https://en.wikipedia.org/wiki/Tree_rotation), बेतरतीब ढंग से। क्या किसी भी यादृच्छिक पेड़ से किसी भी अन्य पेड़ से खोज स्थान में शुरू करना संभव है।

मैंने विभिन्न संसाधनों की कोशिश की है, लेकिन इसके लिए कोई प्रमाण नहीं मिला है। मैंने खुद इसकी कोशिश की है, लेकिन समाधान तक नहीं पहुंच पा रहा हूं। मुझे खुशी है कि अगर कोई मेरी मदद कर सके।

उत्तर:

पहले दिखाते हैं कि समान संख्या वाले पत्तों वाले सभी पेड़ों में समान संख्या में आंतरिक नोड होते हैं। यह जाँच कर दिखाया जाता है कि कितने पत्तों वाले वृक्षों में वृक्ष है I आंतरिक नोड्स। साथ में I आंतरिक नोड्स, हैं 2*I किनारों। I-1 इन किनारों के आंतरिक नोड्स को जोड़ता है, इसलिए I+1 पत्ती नोड्स के लिए किनारों को छोड़ दिया जाता है। तो, साथ पेड़ n पत्ती नोड्स, है n-1 आंतरिक नोड्स।

यह देखने के लिए कि एक पेड़ को दूसरे पेड़ में बदला जा सकता है, यह दोनों पेड़ों को कुछ "आधार" पेड़ में बदलने के लिए पर्याप्त है। जैसे चलो A वह पेड़ हो जहां हर आंतरिक नोड (अंतिम को छोड़कर) में बाईं ओर पत्ती और दाईं ओर आंतरिक नोड हो। यह एक पथ की तरह है :-) किसी भी पेड़ को बदलने के लिए A केवल सही घुमावों की आवश्यकता होती है, और यह आदेश नोड्स को खोजने के लिए आसान है कि घुमाव कैसे करें। बदलना T1 सेवा मेरे T2 यह रूपांतरित करने के लिए पर्याप्त है T1 सेवा मेरे A, और घुमावों की रिवर्स सूची द्वारा A सेवा मेरे T2.