ต้นไม้ไบนารีที่สมบูรณ์กับต้นไม้ไบนารีเต็ม
ต้นไม้ไบนารีเป็นต้นไม้ที่แต่ละโหนดมีลูกหนึ่งหรือสองคน ในไบนารีทรี โหนดไม่สามารถมีลูกมากกว่าสองคนได้ ในไบนารีทรี เด็ก ๆ จะถูกตั้งชื่อว่า "ซ้าย" และ "ขวา" โหนดย่อยมีการอ้างอิงถึงพาเรนต์ ต้นไม้ไบนารีที่สมบูรณ์คือไบนารีทรีที่ต้นไม้ไบนารีทุกระดับถูกเติมอย่างสมบูรณ์ยกเว้นระดับสุดท้าย ในระดับที่ไม่สำเร็จ โหนดจะถูกแนบโดยเริ่มจากตำแหน่งซ้ายสุด ต้นไม้ไบนารีแบบเต็มคือต้นไม้ที่ทุกโหนดในต้นไม้มีลูกสองคน ยกเว้นใบของต้นไม้
ต้นไม้ไบนารีเต็มคืออะไร
ต้นไม้ไบนารีแบบเต็มคือไบนารีทรีที่ทุกโหนดในทรีมีลูกศูนย์หรือสองคนพอดี กล่าวอีกนัยหนึ่ง ทุกโหนดในต้นไม้ยกเว้นใบไม้มีลูกสองคนพอดี รูปที่ 1 ด้านล่างแสดงต้นไม้ไบนารีแบบเต็ม ในไบนารีทรีแบบเต็ม จำนวนโหนด (n) จำนวน laves (l) และจำนวนโหนดภายใน (i) สัมพันธ์กันในลักษณะพิเศษ ซึ่งถ้าคุณรู้จักหนึ่งในนั้น คุณสามารถระบุอีกสองโหนดได้ ค่าดังนี้:
1. หากต้นไม้ไบนารีเต็มมี i โหนดภายใน:
– จำนวนใบ l=i+1
– จำนวนโหนดทั้งหมด n=2i+1
2. หากไบนารีทรีเต็มมี n โหนด:
– จำนวนโหนดภายใน i=(n-1)/2
– จำนวนใบ l=(n+1)/2
3. ถ้าเลขฐานสองเต็มมี l ใบไม้:
– จำนวนโหนดทั้งหมด n=2l-1
– จำนวนโหนดภายใน i=l-1
ต้นไม้ไบนารีที่สมบูรณ์คืออะไร
ดังแสดงในรูปที่ 2 ต้นไม้ไบนารีที่สมบูรณ์คือต้นไม้ไบนารีที่ต้นไม้ทุกระดับจะเต็มไปหมดยกเว้นระดับสุดท้าย นอกจากนี้ ในระดับสุดท้าย ควรแนบโหนดโดยเริ่มจากตำแหน่งซ้ายสุด ต้นไม้ไบนารีที่สมบูรณ์ของความสูง h เป็นไปตามเงื่อนไขต่อไปนี้:
– จากโหนดรูท ระดับที่สูงกว่าระดับสุดท้ายแสดงถึงต้นไม้ไบนารีที่มีความสูง h-1
– อย่างน้อยหนึ่งโหนดในระดับสุดท้ายอาจมีลูก 0 หรือ 1 คน
– ถ้า a, b เป็นสองโหนดในระดับที่สูงกว่าระดับสุดท้าย แล้ว a จะมีลูกมากกว่า b ถ้าหากว่า a อยู่ทางซ้ายของ b
Complete Binary Tree กับ Full Binary Tree ต่างกันอย่างไร
ต้นไม้ไบนารีที่สมบูรณ์และต้นไม้ไบนารีที่สมบูรณ์มีความแตกต่างกันอย่างชัดเจน แม้ว่าไบนารีทรีแบบเต็มคือไบนารีทรีที่โหนดทุกโหนดมีลูกเป็นศูนย์หรือสองคน แต่ทรีไบนารีที่สมบูรณ์คือทรีไบนารีที่ทุกระดับของทรีไบนารีจะเต็มไปหมดยกเว้นระดับสุดท้าย โครงสร้างข้อมูลพิเศษบางอย่าง เช่น ฮีปจะต้องเป็นต้นไม้ไบนารีที่สมบูรณ์ ในขณะที่ไม่จำเป็นต้องเป็นต้นไม้ไบนารีแบบเต็ม ในไบนารีทรีแบบเต็ม หากคุณทราบจำนวนโหนดทั้งหมดหรือจำนวน laves หรือจำนวนโหนดภายใน คุณสามารถค้นหาอีกสองโหนดได้อย่างง่ายดาย แต่ไบนารีทรีที่สมบูรณ์ไม่มีคุณสมบัติพิเศษที่เกี่ยวข้องกับคุณลักษณะทั้งสามนี้