ต้นไม้ฝ่ายซ้ายลำเอียงในโครงสร้างข้อมูล

ที่นี่เราจะมาดูกันว่าต้นไม้ฝ่ายซ้ายที่มีความสูงสมดุล (HBLT) คืออะไร พิจารณาไบนารีทรีที่มีโหนดพิเศษเรียกว่า โหนดภายนอก แทนที่แต่ละทรีย่อยที่ว่างเปล่า โหนดอื่นๆ ทั้งหมดเรียกว่า Internal Nodes . เมื่อมีการเพิ่มโหนดภายนอกด้วยไบนารีทรี โหนดนั้นจะเรียกว่า ไบนารีทรีแบบขยาย .

หากเราไม่พิจารณาขอบใบของต้นไม้ต้นนี้ แสดงว่าเป็นต้นไม้ไบนารีจริง และนี่คือไบนารีทรีแบบขยาย

สมมติว่า s(x) เป็นความยาวของเส้นทางที่สั้นที่สุดจากโหนด x ไปยังโหนดภายนอกในทรีย่อย ถ้า x เป็นโหนดภายนอก จะเป็น s(x) ค่าเท่ากับ 0 หาก x เป็นโหนดภายใน ค่าจะเป็น −

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

โดยที่ L และ R เป็นลูกซ้ายและขวาของ x ตอนนี้ให้เราดูค่าของต้นไม้ที่กำหนด

คำจำกัดความของ HBLT มีลักษณะดังนี้:ต้นไม้ไบนารีคือ ต้นไม้ฝ่ายซ้ายที่มีความสูงสมดุล (HBLT) ถ้าและเฉพาะในกรณีที่ทุกโหนดภายใน ค่า s ของชายด์ด้านซ้ายมากกว่าหรือเท่ากับค่า s ของเด็กด้านขวา

ต้นไม้ด้านบนไม่ใช่ HBLT พาเรนต์ของโหนด a มี s(L) =0 และ s(R) คือ 1 ยกเว้นว่าโหนดอื่นทั้งหมดเป็นไปตามกฎของ HBLT ดังนั้นถ้าเราซ้ายและขวาทรีย่อยของโหนดนั้น เพื่อทำให้เป็น HBLT

คำจำกัดความอื่นๆ ได้แก่ −

• ต้นไม้สูงสุด (ต้นไม้ขั้นต่ำ) คือต้นไม้ ซึ่งค่าของแต่ละโหนดมากกว่า (น้อยกว่า) หรือเท่ากับลูกของมัน

• HBLT สูงสุดคือ HBLT ซึ่งเป็นต้นไม้สูงสุดด้วย HBLT ขั้นต่ำคือ HBLT ซึ่งเป็นต้นไม้ขั้นต่ำด้วย