यहाँ हम देखेंगे कि हाइट बैलेंस्ड लेफ्टिस्ट ट्री (Height Balanced Leftist Trees - HBLT) क्या है। एक बाइनरी ट्री पर विचार करें जहां एक विशेष नोड, जिसे बाहरी नोड (external node) कहा जाता है, प्रत्येक खाली उपट्री को प्रतिस्थापित करता है। अन्य सभी नोड्स को आंतरिक नोड्स (Internal Nodes) कहा जाता है। जब कुछ बाहरी नोड्स को किसी बाइनरी ट्री के साथ जोड़ा जाता है, तो उसे विस्तारित बाइनरी ट्री (extended binary tree) कहा जाता है।
यदि हम इस ट्री के पत्ती किनारों पर विचार नहीं करते हैं, तो वह वास्तविक बाइनरी ट्री है। और यह विस्तारित बाइनरी ट्री है।
अब मान लीजिए s(x), नोड x से उसकी उपट्री में बाहरी नोड तक के सबसे छोटे पथ की लंबाई है। यदि x एक बाहरी नोड है, तो उसका s(x) मान 0 है। यदि x एक आंतरिक नोड है, तो मान है:
min{s(L), s(R)} + 1
यहाँ L और R, x के बाएं और दाएं बच्चे हैं। अब देखते हैं दिए गए ट्री के s मान।
HBLT की परिभाषा इस तरह है: एक बाइनरी ट्री हाइट बैलेंस्ड लेफ्टिस्ट ट्री (HBLT) है यदि और केवल यदि, प्रत्येक आंतरिक नोड पर, बाएं बच्चे का s मान दाएं बच्चे के s मान से बड़ा या बराबर होता है।
उपरोक्त ट्री HBLT नहीं है। नोड a के माता-पिता का s(L) = 0, और s(R) = 1 है, सिवाय इसके कि अन्य सभी नोड्स HBLT के नियम को संतुष्ट करते हैं। इसलिए यदि हम उस नोड के बाएं और दाएं उपट्री को स्वैप करते हैं, ताकि यह HBLT बन जाए।
कुछ अन्य परिभाषाएं हैं:
एक मैक्स ट्री (मिन ट्री) एक ट्री है, जिसमें प्रत्येक नोड का मान उसके बच्चों से बड़ा (छोटा) या बराबर होता है।
एक मैक्स HBLT एक HBLT है, जो मैक्स ट्री भी है, एक मिन HBLT एक HBLT है, जो मिन ट्री भी है।
