এখানে আমরা হাইট ব্যালেন্সড লেফটিস্ট ট্রি (HBLT) কী সেটি দেখব। একটি বাইনারি ট্রি বিবেচনা করুন যেখানে একটি স্পেশাল নোড, যাকে এক্সটার্নাল নোড বলা হয়, প্রতিটি খালি সাবট্রি রিপ্লেস করে। বাকি সব নোডকে ইন্টারনাল নোড বলা হয়। যখন কিছু এক্সটার্নাল নোড কিছু বাইনারি ট্রির সাথে যোগ করা হয়, তবে সেটিকে এক্সটেন্ডেড বাইনারি ট্রি বলা হয়।
যদি আমরা এই ট্রির লিফ এজগুলো বিবেচনা না করি, তবে সেটি আসলে বাইনারি ট্রি। এবং এটি এক্সটেন্ডেড বাইনারি ট্রি।
এখন ধরি 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 যা মিন ট্রিও।
