ต้นไม้แบบทวิภาค
ต้นไม้ทวิภาค (อังกฤษ: binary tree) ในศาสตร์คอมพิวเตอร์ เป็นโครงสร้างข้อมูลแบบต้นไม้ซึ่งแต่ละปมมีปมลูกได้ไม่เกิน 2 ปม โดยแยกออกเป็นปมด้านซ้าย และปมด้านขวา ปมที่มีปมลูก เรียกว่า ปมพ่อแม่ และปมลูกอาจมีรีเฟอร์เรนซ์ไปยังปมพ่อแม่ของมัน ในโครงสร้างแบบต้นไม้จะมีปม ๆ หนึ่งเป็นปมบรรพบุรุษของทุกปม เราเรียกปมนี้ว่าปมราก การเข้าถึงปมทุกปมในโครงสร้างแบบต้นไม้ทำได้โดยเริ่มต้นจากปมราก และใช้รีเฟอร์เรนซ์ของปมนั้นท่องไปตามปมลูกด้านซ้ายและด้านขวาของมัน ต้นไม้ที่มีเฉพาะปมราก เรียกว่าต้นไม้ว่าง (null tree) ในต้นไม้ทวิภาค กิ่งหรือดีกรีของทุก ๆ ปมมีค่ามากที่สุดได้ไม่เกิน 2 ต้นไม้ที่มีปมจำนวน 'n' ปมจะมีกิ่งได้ไม่เกิน 'n-1' กิ่ง ต้นไม้ทวิภาคมักใช้สำหรับต้นไม้ค้นหาทวิภาค (binary search trees) และฮีพทวิภาค (binary heaps)
คำจำกัดความสำหรับต้นไม้ราก
[แก้]- ขอบโดยตรง (A directed edge) หมายถึงเส้นที่เชื่อมจากปมพ่อแม่ไปยังปมลูก
- ปมรากเป็นปมที่ไม่มีปมพ่อแม่ ต้นไม้หนึ่งต้นมีปมรากเพียงปมเดียว
- ปมใบ (leaf node) เป็นปมที่ไม่มีปมลูก
- ความลึกของปม (The depth of a node) n เป็นความยาวของเส้นทางจากปมราก ไปจนถึงปมนั้น เซตของทุกปม ณ ความลึกที่ให้ บางครั้งเรียกว่าระดับของต้นไม้ ปมรากมีความลึกเท่ากับ 0
- ความลึก หรือความสูง (The depth or height) ของต้นไม้ เป็นความยาวของเส้นทางจากปมรากไปจนถึงปมที่อยู่ลึกที่สุดของต้นไม้นั้น
- ปมพี่น้อง (Siblings nodes) เป็นปมที่มีปมพ่อแม่เดียวกัน
- ปม p เป็นปมบรรพบุรุษของปม q ถ้ามีเส้นทางจากปมรากไปถึงปม q และเรียกปม q ว่าเป็นปมลูกหลานของปม p
- ขนาดของปม (The size of a node) คือ จำนวนปมลูกหลานของมันทั้งหมดรวมทั้งตัวมันด้วย
- กิ่งเข้า (In-degree) ของปม คือจำนวนกิ่งที่เข้าหามัน
- กิ่งออก (Out-degree) ของปม คื่อจำนวนกิ่งที่ออกจากปมนั้น
- ปมรากเป็นเพียงปมเดียวในต้นไม้ที่มีกิ่งเข้า (In-degree) เท่ากับ 0
- ปมในมีกิ่งออก เท่ากับ 0
ชนิดของต้นไม้ทวิภาค
[แก้]- ต้นไม้ทวิภาคที่มีราก (A rooted binary tree) เป็นต้นไม้ซึ่งปมรากหนึ่งปม และทุกปมในต้นไม้มีปมลูกได้ไม่เกิน 2 ปม
- ต้นไม้ทวิภาคแบบเต็ม (A full binary tree) เป็นต้นไม้ซึ่งทุก ๆ ปมยกเว้นปมใบ มีปมลูก 2 ปม
- ต้นไม้ทวิภาคแบบสมบูรณ์ (A perfect binary tree) เป็นต้นไม้ทวิภาคแบบเต็ม ซึ่งปมใบทุกปมจะอยู่ในระดับเดียวกันหรือมีความลึกเท่ากัน
- complete binary tree เป็นต้นไม้ทวิภาคซึ่งปมทุกระดับยกเว้นระดับล่างสุด จะมีปมลูก 2 ปม และทุกปมจะเริ่มจากทางซ้ายสุด
- ต้นไม้ทวิภาคสมดุล เป็นต้นไม้ทวิภาค ซึ่งความลึกของต้นไม้ย่อย (subtree) สองต้นของทุก ๆ ปม เท่ากัน ปมใบของต้นไม้ย่อยจะมีระดับเท่ากัน