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

ที่นี่เราจะเห็นรูปแบบอื่นของต้นไม้ฝ่ายซ้าย ในที่นี้ เราจะพิจารณาจำนวนโหนดในทรีย่อย แทนที่จะเป็นความยาวของพาธที่สั้นที่สุดสำหรับรูทไปยังโหนดภายนอก ในที่นี้เราจะกำหนดน้ำหนัก w(x) ของโหนด x ให้เป็นจำนวนโหนดภายในในทรีย่อยที่มีรูท x ถ้า x เป็นโหนดภายนอก น้ำหนักจะเป็น 0 ถ้า x เป็นโหนดภายใน น้ำหนักจะมากกว่าผลรวมของน้ำหนักย่อยหนึ่งค่า

นี่คือตัวอย่าง Weight Biased Leftist Tree (WBLT) −

สมมติว่าต้นไม้ไบนารีเป็นแบบนี้ -

หากเราคำนวณค่า w(x) สำหรับแต่ละโหนด มันจะเป็นเช่นนี้ -

ตอนนี้คำจำกัดความของ WBLT เป็นเหมือน −

ต้นไม้ไบนารีเรียกว่า Weight Balanced Leftist Tree ถ้าทุกโหนดภายใน w(x) ของลูกด้านซ้ายมากกว่าหรือเท่ากับ w(x) ของเด็กด้านขวา WBLT สูงสุด (นาที) คือต้นไม้สูงสุด (ต่ำสุด) ที่เป็น WBLT ด้วย