Data Structure & Algorithm(EP.10) — ทรี (Tree)
Tree เป็นโครงสร้างที่ไม่เป็นเชิงเส้น (Non-Linear) รูปแบบของทรีเหมือนกับแผนผังโครงสร้าง ที่มีความสัมพันธ์ด้านในเป็นลำดับชั้น โดยจะทำงานตั้งแต่ลำดับสูงสุดมาที่ลำดับล่างสุด
คุณสมบัติของทรี
ทรีมีโครงสร้างแบบลำดับชั้นแต่ละลำดับชั้นมีความสัมพันธ์ระหว่างข้อมูลเป็นแบบแม่กับลูก (Parent-Child) ภายในความสัมพันธ์ระหว่างโหนดแม่และโหนดลูกนี้จะถูกเชื่อมด้วยเส้นความสัมพันธ์ (Edge)
โหนดแม่ (Parent) คือ โหนดที่อยู่ลำดับบนของอีกโหนด จากภาพตำแหน่งโหนด A อยู่ตำแหน่งบนของโหนด B ดังนั้น จะเรียกโหนด A เป็นโหนดแม่ของโหนด B
โหนดลูก (Child) คือ โหนดที่อยู่ลำดับล่างของอีกโหนด จากภาพตำแหน่งโหนด B อยู่ตำแหน่งล่างของโหนด A ดังนั้น จะเรียกโหนด B เป็นโหนดลูกของโหนด A
โหนดพี่น้อง (Sibling) คือ โหนดที่อยู่ระดับเดียวกัน จากภาพตำแหน่งโหนด B และโหนด C อยู่ในระดับเดียวกัน จะเรียกโหนด B และโหนด C ว่าเป็นโหนดพี่น้อง
โหนดราก (Root) คือ โหนดที่มีคุณสมบัติพิเศษ เป็นโหนดที่ไม่มีโหนดแม่ และทุกโหนดในทรีจะมีโหนดนี้เป็นโหนดแม่ จากภาพ โหนด A ไม่มีโหนดแม่ จะเรียกโหนด A ว่าเป็นโหนดราก
โหนดใบ (Leaf) คือ โหนดที่อยู่ตำแหน่งล่างสุดของทรี จากภาพตำแหน่งโหนด C , D , E อยู่ตำแหน่งล่างสุดของทรี ดังนั้นจะเรียกโหนดดังกล่าวว่า โหนดใบ
บรรพบุรุษ (Ancestor) คือ ความสัมพันธ์ระหว่างโหนดจากภาพอธิบายความสัมพันธ์ระหว่างโหนด A โหนด B , D โดยที่โหนด A , B นั้นเป็นบรรพบุรุษของโหนด D
ลูกหลาน (Descendant) คือ ความสัมพันธ์ที่มีคุณสมบัติการสืบทอดระหว่างโหนดแม่กับลูกหรือหลานจากภาพโหนด D ได้สืบทอดมาจากโหนด A และ โหนด B
ทรีย่อย (Subtree) คือ โหนดที่อยู่ตำแหน่งสืบทอดของโหนดที่เป็นรากจากภาพโหนด A มีทรีย่อยคือ โหนด B , C , D และ E
ไบนารีทรี (Binary Tree) โครงสร้างของไบนารีทรี มีข้อกำหนดเกี่ยวกับโหนดแม่และโหนดลูก คือ โหนดแม่หนึ่งโหนด (R) มีลูกได้ไม่เกิน 2 โหนด และเรียกโหนดลูกเหล่านี้ว่า ทรีย่อย (Subtrees)
โครงสร้างของไบนารีทรี มีข้อกำหนดเกี่ยวกับโหนดแม่และโหนดลูก คือ โหนดแม่หนึ่งโหนด (R) มีลูกได้ไม่เกิน 2 โหนด และเรียกโหนดลูกเหล่านี้ว่า ทรีย่อย (Subtrees)
- โหนดลูกที่อยู่ด้านซ้ายของโหนดแม่จะเรียกว่า ทรีย่อยซ้าย (TL)
- โหนดลูกที่อยู่ด้านขวาของโหนดแม่จะเรียกว่า ทรีย่อยขวา (TR)
- ความสูงของทรี หมายถึง จำนวนโหนดที่มีความสูงมาจากโหนดรากถึงโหนดตำแหน่งใบ โดยแทนความสูงด้วยสัญลักษณ์ h
รูปแบบของไบนารีทรี
- Full Binary Tree ภายในไบนารีทรีนั้นสามารถมีโหนดลูกทั้งสองด้านหรือไม่มีโหนดลูกเลยจำนวนโหนดลูกสามารถเป็น 2 หรือ 0
- Perfect Binary Tree ภายในไบนารีทรีนั้นโหนดที่อยู่ในระดับเดียวกันต้องมีจำนวนโหนดเท่ากัน
- Complete Binary Tree เหมือน Full Binary Tree แต่โหนดลำดับท้ายสุดหรือโหนดใบสามารถมีลูกได้ 1 โหนด
บทความที่เกี่ยวข้อง
- EP.1 — รู้จักกับโครงสร้างข้อมูลและอัลกอริทึม
- EP.2 — การวัดประสิทธิภาพอัลกอริทึม
- EP.3 — อัตราการเติบโตของฟังก์ชั่น
- EP.4 — การวิเคราะห์อัลกอริทึม
- EP.5 — Big-O Notation
- EP.6 — การคำนวณ Big-O
- EP.7 — ลิงค์ลิสต์ (Linked-List)
- EP.8 — สแต็ก (Stack)
- EP.9 — คิว(Queue)
- EP.10 — ทรี (Tree)
- EP.11 — Binary Search Tree (BST)
- EP.12 — กราฟ(Graphs)
