डेटा संरचना में ऊंचाई-पक्षपाती वामपंथी पेड़

यहां हम देखेंगे कि हाइट बैलेंस्ड लेफ्टिस्ट ट्री (HBLT) क्या है। एक बाइनरी ट्री पर विचार करें जहां एक विशेष नोड, जिसे बाहरी नोड . कहा जाता है प्रत्येक खाली उपट्री को प्रतिस्थापित करता है। अन्य सभी नोड्स को आंतरिक नोड्स . कहा जाता है . जब कुछ बाहरी नोड्स को किसी बाइनरी ट्री के साथ जोड़ा जाता है, तो उसे विस्तारित बाइनरी ट्री . कहा जाता है ।

अगर हम इस पेड़ के पत्तों के किनारों पर विचार नहीं करते हैं, तो यह वास्तविक बाइनरी ट्री है। और यह विस्तारित बाइनरी ट्री है।

अब मान लीजिए s(x) नोड x से बाहरी नोड तक इसके उपट्री में सबसे छोटे पथ की लंबाई हो। यदि x एक बाहरी नोड है, तो इसका s(x) मान 0 है। यदि x एक आंतरिक नोड है, तो मान है -

min{𝑠(𝐿), 𝑠(𝑅)} + 1

यहाँ L और R, x के बाएँ और दाएँ बच्चे हैं। आइए अब दिए गए पेड़ के s मान देखें।

HBLT की परिभाषा इस प्रकार है:एक बाइनरी ट्री हाइट बैलेंस्ड लेफ्टिस्ट ट्री (HBLT) है, यदि और केवल तभी, प्रत्येक आंतरिक नोड पर, बाएं बच्चे का s मान दाएं बच्चे के s मान से अधिक या बराबर होता है।

उपरोक्त पेड़ HBLT नहीं है। नोड ए के माता-पिता में एस (एल) =0 है, और एस (आर) 1 है, सिवाय इसके कि अन्य सभी नोड्स एचबीएलटी के नियम को संतुष्ट कर रहे हैं। तो अगर हम उस नोड के बाएँ और दाएँ सबट्री, इसे HBLT बनाने के लिए।

कुछ अन्य परिभाषाएं हैं -

• अधिकतम पेड़ (न्यूनतम पेड़) एक ऐसा पेड़ होता है, जिसमें प्रत्येक नोड का मान उसके बच्चों के बराबर (कम) या उसके बराबर होता है।

• एक अधिकतम एचबीएलटी एक एचबीएलटी है, जो कि एक अधिकतम पेड़ भी है, एक न्यूनतम एचबीएलटी एक एचबीएलटी है, जो कि एक छोटा पेड़ भी है।