DTS 01-09-52

สรุปเนื้อหาบทเรียน เรื่อง Tree

ทรี (Tree) เป็นโครงสร้างข้อมูลที่มีความสัมพันธ์กัน ระหว่าง โหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับชั้น ส่วนมากจะใช้สำหรับ แสดงความสัมพันธ์ระหว่างข้อมูล ในทรีหนึ่งทรีจะประกอบไปด้วยรูทโหนด (root node) เพียงหนึ่งโหนด แล้วรูทโหนดสามารถแตกโหนดออกเป็นโหนดย่อยๆ ได้อีกหลายโหนดเรียกว่าโหนดลูก (Child node) เมื่อมีโหนดลูกแล้ว โหนดลูกก็ยังสามารถแสดงเป็นโหนดพ่อแม่ (Parent Node) โดยการแตกโหนดออกเป็นโหนดย่อยๆได้อีก



นิยามของโครงสร้างต้นไม้

1. นิยามของทรีด้วยนิยามของกราฟ

2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟ


นิยามที่เกี่ยวข้องกับ ทรี

1.นิยามทรีด้วยนิยามของกราฟ
ทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด (loop) ในโครงสร้าง โหนดสองโหนดใดๆในทรีต้งมทางติดต่อกันทางเดียวเท่านั้น และทรีที่มี N โหนด ต้องมีกิ่งทั้งหมด N-1 เส้น อาจเขียนได้ 4 รูปแบบ
- แบบมีรากอยู่ด้านบน
- แบบมีรากอยู่ด้านล่าง
- แบบมีรากอยู่ด้านซ้าย
- แบบมีรากอยู่ด้านขวา

2. นิยามทรีด้วยรูปแบบรรีเคอร์ซีฟ
ทรีประกอบด้วยสมาชิกที่เรียกว่า โหนด โดยที่ ถ้าว่าง ไม่มีโหนดใดๆ เรียกว่า Null Tree และถ้ามีโหนดหนึ่งเป็นโหนดราก ส่วนที่เหลือจะแบ่งเป็น ทรีย่อย (Sub Tree) โดยที่ k>=0 และทรีย่อยต้องมีคุณสมบัติเป็นทรี



นิยามที่เกี่ยวข้อง

1.ฟอร์เรสต์ (Forest)
2.ทรีที่มีแบบแผน (Ordered Tree)
3.ทรีคล้าย (Similar Tree)
4.ทรีเหมือน (Equivalent Tree)
5.กำลัง(Degree)
6.ระดับของโหนด (Level of Node)


การแทนที่ทรีในหน่วยความจำหลัก

1.โหนดแต่ละโหนดเก็บพอยเตอร์ชี้ไปยังโหนดลูกทุกโหนด ซึ่งจะทำให้ฟิลด์มีจำนวนเท่ากัน มีขนาดเท่ากับโหนดที่มีลูกมากที่สุด โหนดที่ไม่มีลูกใส่ค่า Null แล้วให้ลิงค์ฟิลด์เก็บค่าพอยเตอร์ของโหนดลูกตัวถัดไปเรื่อยๆ เช่น ลิงค์ฟิลด์แรกเก็บค่าพอยเตอร์ชี้ไปยังโหนดลูกลำดับแรก แต่การแทนที่ทรีด้วยวิธีนี้เป็นการสิ้นเปลืองเนื้อที่โดยใช่เหตุเนื่องจากว่าโหนดบางโหนดอาจมีโหนดลูกน้อย หรือไม่มีโหนดลูกเลย

2.แทนทรีด้วยไบนารีทรี จะมีการกำหนดโหนดทุกโหนดให้มีจำนวนลิงค์ฟิลด์เพียงสองลิงค์ฟิลด์ โดยลิงค์ฟิลด์แรกเก็บที่อยู่โหนดลูกคนโต ลิงค์ฟิลด์ที่สองเก็บที่อยู่โหนดพี่น้อง กรณีไม่มีโหนดลูกและโหนดพี่น้องใส่ Null การแทนที่ทรีด้วยวินี้เป็นการประหยัดเนื้อที่ได้มาก
ไบนารีทรีแบบสมบูรณ์นั้นจะมีโหนดทรีย่อยทางด้านซ้ายและขวา ยกเว้นโหนดใบหรือโหนดที่ไม่มีลูก แต่โหนดใบจะต้องอยู่ในระดับเดียวกัน

การแปลงทรีทั่วไปให้เป็นไบนารีทรี มีขั้นตอนดังนี้

1.ให้โหนดแม่ชี้ไปยังโหนดลูกคนโตแล้วตัดความสัมพันธ์ระหว่างโหนดลูกอื่นๆ
2.เชื่อมความสัมพันธ์ระหว่างโหนดพี่น้อง
3.ให้ทรีย่อยทางขวาเอียงลงมา 45 องศา

การท่องไปในไบนารีทรี

เป็นการเยือนทุกๆโหนด อย่างมีระบบแบบแผน สามารถเยือนโหนดได้โหนดละหนึ่งครั้ง วิธีการท่องนั้นอยู่ที่ว่าต้องการลำดับการเยือนอย่างไร โดย
- N อาจเป็นโหนดแม่
- L ทรีย่อยทางซ้าย
- R ทรีย่อยทางขวา

วิธีการท่องไปในทรีมี 6 วิธี แต่นิยมใช้กันมากคือ NLR , LNR , LRN

1. การท่องไปแบบพรีออร์เดอร์ เป็นการเยือนด้วยวิธี NLR ในลักษณะการเข้าถึงจะเริ่มต้นจากจุดแรกคือ N จากนั้นจึงเข้าไปทรีย่อยด้านซ้ายและเข้าถึงทรีย่อยด้านขวา
2. การท่องไปแบบอินออร์เดอร์ เป็นการเยือนด้วยวิธี LNR สำหรับการเข้าถึงแบบอินออร์เดอร์จะดำเนินการเข้าเยี่ยมทรีย่อยด้านซ้ายก่อน จากนั้นจึงเข้าเยี่ยม N และสิ้นสุดการเข้าเยี่ยมที่ทรีย่อยด้านขวา
3. การท่องไปแบบโพสออร์เดอร์ เป็นการเยือนด้วยวิธี LRN การประมวลผลของโพสออร์เดอร์ จะเริ่มต้นด้วยทรีย่อยด้านซ้ายจานั้นมาประมวลผลต่อที่ทรีย่อยด้านขวาและสิ้นสุดการประมวลผลที่ N