อ่านบทความนี้ใน Facebook
Tree (หรือ rooted tree) นั้นประกอบไปด้วยอะไรบ้าง?
ในโพสที่แล้ว เราได้คุยกันไปว่า tree ในมุมมองของ graph theory คืออะไร และคุยกันไปถึงเรื่องของ rooted tree ที่เราเลือกหยิบ vertex ใด vertex หนึ่งมานิยามมันว่าเป็น “root vertex”
(ทำให้เราสามารถเขียน rooted tree ออกมาเป็นชั้น ๆ ได้แบบในภาพปกเลย)
แน่นอนว่าการกำหนด “root vertex” (หรือ vertex เริ่มต้น) มันทำให้เกิดหลาย ๆ concept เกิดขึ้นตามมา สำหรับในโพสนี้เราจะมา explore concept เหล่านั้นกัน
✦ อย่างแรกเลยการกำหนด root มันทำให้เราบอกได้ว่า “vertex หนึ่ง ๆ อยู่ห่างจาก root เท่าไหร่” สิ่งนี้ก็คือสิ่งที่เราเรียกว่า “level” นั่นเอง เช่น node F อยู่ใน level 2 เพราะอยู่ห่างจาก root สองก้าว (จะเห็นว่า level เริ่มต้นที่ 0)
✦ “height” หรือความสูงของ tree ก็คือ “ความยาวที่มากที่สุดจาก root ไปที่ vertex ล่างสุด (เรียกว่า leaf vertex)” จากในตัวอย่างมี height = 3
✦ “leaf vertex” คือ vertex ที่ไม่มี edge เชื่อมไปยัง vertex อื่น ๆ ที่มี level ต่ำกว่าอีกแล้ว (หรือ vertex ที่ไม่มี children) เช่น vertex H, I, J, F และ G; ตรงข้ามกับ root ที่ไม่มี edge เชื่อมไปยัง vertex ที่มี level สูงกว่าอีกแล้ว (หรือ vertex ที่ไม่มี parent)
✦ “parent” คือ vertex ที่อยู่ติดกันใน level ที่สูงกว่า; ยกตัวอย่างเช่น vertex H จะมี parent เป็น vertex D หรือ vertex F จะมี parent เป็น vertex C
✦ “child” คือ vertices ที่อยู่ติดกันใน level ที่ต่ำกว่า; ยกตัวอย่างเช่น vertex D เราจะมี child สองตัวได้แก่ vertex H กับ I)
✦ “sub-tree” เป็น tree ย่อย ๆ ที่อยู่ใน tree ใหญ่อีกที (จะเห็นว่ามี recursive structure)
✦ “siblings” คือ vertex ที่มี parent เดียวกันและอยู่ใน level เดียวกัน
ความน่าสนใจก็คือ concept เหล่านี้ ไม่ว่าจะเป็น parent-child relationship, height/levels หรืออะไรก็ตามจะไม่เกิดขึ้นเลยถ้าเราไม่กำหนด “root vertex”
มันน่าสนใจมากว่าบางที “การเปลี่ยน property แค่นิดเดียว” สามารถส่งผลให้เกิด “implication หรือโครงสร้างที่น่าสนใจ” ตามมาให้เราได้ค้นหาเพิ่มอีกมากมาย
