ट्री का लेफ्ट-चाइल्ड राइट-सिबलिंग प्रतिनिधित्व

लेफ्ट-चाइल्ड राइट-सिबलिंग प्रतिनिधित्व

यह एक n-एरी ट्री (सामान्य ट्री) को बाइनरी ट्री के रूप में प्रस्तुत करने की तकनीक है। प्रत्येक नोड के लिए बच्चों की सूची के बजाय केवल **दो पॉइंटर्स** रखे जाते हैं:

1. लेफ्ट चाइल्ड (फर्स्ट चाइल्ड): पहले (सबसे बाएं) बच्चे का पॉइंटर।
2. राइट सिबलिंग (नेक्स्ट सिबलिंग): तत्काल अगले सिबलिंग का पॉइंटर।

रूपांतरण नियम

• समान पैरेंट के सभी बच्चों को लेफ्ट-टू-राइट लिंक करें (राइट-सिबलिंग पॉइंटर्स के माध्यम से)।
• पैरेंट केवल **पहले बच्चे** से लिंक करता है (लेफ्ट-चाइल्ड पॉइंटर के माध्यम से)।

उदाहरण

मूल ट्री:          LCRS प्रतिनिधित्व:
    10                  10
  / | \ \               |
 2  3  4  5              2 → 3 → 4 → 5
 |  |  |                |   |   |   |
 6  7  8                6   7   8   9
    |
    9

लाभ

• मेमोरी कुशल: प्रति नोड अधिकतम 2 पॉइंटर्स (फिक्स्ड), चाहे बच्चों की संख्या कितनी भी हो।
• सरल कार्यान्वयन: बाइनरी ट्री नोड संरचना का पुन: उपयोग करता है।
• कोई पूर्व ज्ञान आवश्यक नहीं: बच्चों की संख्या के लिए सरणी आकार की आवश्यकता नहीं।

नुकसान

• धीमे बुनियादी ऑपरेशन्स: खोज/सम्मिलन/विलोपन में O(डिग्री) समय लग सकता है क्योंकि सही पोजीशन खोजने के लिए सभी सिबलिंग्स को पार करना पड़ सकता है (सबसे खराब स्थिति)।
• कम सहज: पैरेंट-टू-चाइल्ड नेविगेशन के लिए दो पॉइंटर हॉप्स की आवश्यकता होती है (लेफ्ट चाइल्ड → राइट सिबलिंग चेन)।

उपयोग के मामले

• मेमोरी-बाधित वातावरण।
• जब ट्री ज्यादातर स्टेटिक हो (कम संशोधन)।
• पार्स ट्रीज़, XML/HTML DOM प्रतिनिधित्व (जहां सिबलिंग ट्रैवर्सल आम है)।