นิยาม HBLT
พิจารณา Binary Tree ที่แทน Empty Subtree ด้วย External Node โหนดอื่นๆ เรียก Internal Nodes เพิ่ม External Nodes เข้าไป = Extended Binary Tree
ไม่นับ Leaf Edges = Binary Tree จริง นับรวม = Extended Binary Tree
นิยาม s(x) = ความยาว Shortest Path จาก x ไป External Node ใน Subtree ของ x
- x เป็น External Node: s(x) = 0
- x เป็น Internal Node: s(x) = min{s(L), s(R)} + 1
ค่า s(x) ของต้นไม้ตัวอย่าง
เงื่อนไข HBLT
Binary Tree เป็น HBLT ก็ต่อเมื่อ: ที่ทุก Internal Node s(Left Child) ≥ s(Right Child)
ต้นไม้ข้างต้นไม่ใช่ HBLT พาเรนต์ของโหนด a มี s(L)=0, s(R)=1 โหนดอื่นๆ ผ่าน เลย Swap Left/Right ของโหนดนั้น
นิยามเพิ่มเติม
- Max Tree (Min Tree): ค่าโหนด ≥ (≤) ลูกๆ
- Max HBLT = HBLT ที่เป็น Max Tree, Min HBLT = HBLT ที่เป็น Min Tree
