Tree (ทรี)
ทรี หรือโครงสร้างข้อมูลแบบต้นไม้ ประกอบด้วยโหนด (node) ซึ่งเป็นส่วนที่เก็บข้อมูล ในทรีหนึ่งทรีจะประกอบไปด้วยรูทโหนด (root node) เพียงหนึ่งโหนด แล้วรูทโหนดสามารถแตกโหนดออกเป็นโหนดย่อยๆ ได้อีกหลายโหนดเรียกว่าโหนดลูก (Child node) เมื่อมีโหนดลูกแล้ว โหนดลูกก็ยังสามารถแสดงเป็นโหนดพ่อแม่ (Parent Node) โดยการแตกโหนดออกเป็นโหนดย่อยๆได้อีก โหนดที่มีโหนดแม่เป็นโหนดเดียวกันเรียกว่า โหนดพี่น้อง (Siblings) โหนดที่ไม่มีโหนดลูกเรียกว่า โหนดใบ (Leave Node) เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดเรียกว่า กิ่ง (Beanch) คือ โหนดที่ไม่ใช่ Leaf Node
นิยามของทรี
1. นิยามทรีด้วยนิยามของกราฟทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด (loop) ในโครงสร้าง โหนดสองโหนดใดๆ ในทรีต้องมีทางติดต่อกัน ทางเดียวกันนั้น และทรีที่มี N โหนด ต้องมีกิ่งทั้งหมด N -1เส้น การเขียนรูปแบบทรี อาจเขียนได้ 4 แบบ คือ
1. แบบที่มีรากอยู่ด้านบน
2. แบบที่มีรากอยู่ด้านล่าง
3. แบบที่มีรากอยู่ด้านซ้าย4. แบบที่มีรากอยู่ด้านขวา
การท่องไปในไบนารีทรี (Traversing Binary Tree)
คือ การเข้าไปเยือนทุก ๆ โหนดในทรี วิธีการท่องเข้าไปต้องเป็นไปอย่างมีระบบแบบแผน สามารถเยือนโหนดทุก ๆ โหนด ๆ ละหนึ่งครั้ง วิธีการท่องไปนั้นมีด้วยกันหลายแบบ โหนดที่ถูกเยือนอาจเป็นโหนดแม่ (แทนด้วย N)ทรีย่อยทางซ้าย (แทนด้วย L) หรือทรีย่อยทางขวา (แทนด้วย R)
วิธีการท่องเข้าไปในทรีมี 6 วิธีคือ
NLR LNR LRN NRL RNL และ RLN
แต่วิธีการท่องเข้าไปในทรีที่นิยมใช้กันมากเป็นการท่องจากซ้ายไปขวา 3 แบบแรก
คือ NLRLNR LRN ซึ่งลักษณะการนิยามเป็นนิยามแบบ รีเคอร์ซีฟ (Recursive)
ขั้นตอนวิธีดึงโหนดออกอาจแยกพิจารณาได้ 3 กรณีดังต่อไปนี้
1. กรณีโหนดที่จะดึงออกเป็นโหนดใบ
2. กรณีโหนดที่ดึงออกมีเฉพาะทรีย่อยทางซ้ายหรือทรีย่อยทางขวาเพียงด้านใดด้านหนึ่ง
3. กรณีโหนดที่ดึงออกมีทั้งทรีย่อยทางซ้ายและทรีย่อยทางขวา - ถ้าโหนดที่มาแทนที่เป็นโหนดที่เลือกจากทรีย่อยทางซ้าย ต้องเลือกโหนดที่มีค่ามากที่สุดในทรีย่อยทางซ้ายนั้น - ถ้าโหนดที่จะมาแทนที่เป็นโหนดที่เลือกมาจากทรีย่อยทางขวา ต้องเลือกโหนดที่มีค่าน้อยที่สุดในทรีย่อยทางขวานั้น
ไม่มีความคิดเห็น:
แสดงความคิดเห็น