Tree
ทรี เป็นโครงสร้างข้อมูลที่ความสัมพันธ์ระหว่างโหนด จะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับชั้น เช่น Flowchat เป็นต้น
แต่ละโหนกจะมีความสัมพันธ์กับโหนดในระดับที่ต่ำลงมาหนึ่งระดับได้หลายๆโหนด เรียกว่า โหนดแม่
โหนดที่อยู่ต่ำกว่าโหนกแม่อยู่หนึ่งระดับเรียกว่า โหนดลูก
โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่ เรียกว่า โหนดราก
โหนดที่มีโหนดแม่เป็นโหนดเดียวกัน เรียกว่า โหนดพี่น้อง
โหนดที่ไม่มีโหนดลูก เรียกว่า โหนดใบ
เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนด เรียกว่า กิ่ง
นิยามของทรี
1.นิยามทรีด้วยนิยามของกราฟ
ทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด (Loop) ในโครงสร้าง โหนดสองโหนดใดๆ ในทรีต้องมีทางติดต่อกันทางเดียวเท่านั้น และทรีที่มี N โหนด ต้องมีกิ่งทั้งหมด N-1 เส้น
การเขียนรูปแบบทรี เขียนได้ 4 แบบ คือ แบบที่มีรากอยู่ข้างบน,แบบที่มีรากอยู่ข้างล่าง,แบบที่มีรากอยู่ด้านซ้าย,แบบที่มีรากอยู่ด้านขวา
2.นิยามทรีด้วยรูปแบบรีเคอร์ซีฟ
ทรี ประกอบด้วยสมาชิกที่เรียกว่าโหนด โดยที่ถ้าว่าง ไม่มีโหนดใดๆเรียกว่า Null Tree และถ้ามีโหนดหนึ่งเป็นโหนดราก ส่วนที่เหลือจะแบ่งเป็นทรีย่อย (Sub Tree)
นิยามที่เกี่ยวข้องกับทรี
1.Forest คือ เซตของทรีที่แยกจากกัน
2.Ordered Tree คือ ทรีโหนดต่างๆในทรีนั้นมีความสัมพันธ์ที่แน่นอน
3.ทรีคล้าย (Similar Tree) คือ ทรีที่มีโครงสร้างเหมือนกัน (แต่ Data ต่าง)
4.ทรีเหมือน คือ ทรีที่เหมือนกันโดนสมบูรณ์ (Order และ Data เหมือนกัน)
5.Degree คือ จำนวนทรีย่อยของโหนดนั้นๆ
6.Level of Node คือ ระยะทางในแนวดึงของโหนดนั้นๆ ที่อยู่ห่างจากโหนดราก ซึ่งระดับของโหนดจะเท่ากับจำนวนกิ่งที่น้อยที่สุดจากโหนดรากไปยังโหนดใดๆบวกด้วย 1 และจำนวนเส้นทางตามแนวดิ่งของโหนดใดๆ ซึ่งห่างจากโหนดราก เรียกว่า ความสูง หรือ ความลึก
การแทนที่ืทรีในหน่วยความจำหลัก
จะมีพอยเตอร์เชื่อมโยงจากโหนดแม่ไปยังโหนดลูก แต่ละโหนดต้องมีลิงค์ฟิลด์เพื่อเก็บที่อยู่ของโหนดลูกต่างๆนั้นคือ จำนวนลิงค์ฟิลด์
1. โหนดแต่ละโหนดเก็บพอยเตอร์ชี้ไปยังโหนดลูกทุกโหนด
การแทนที่วิธีนี้ จะทำให้จำนวนฟิลด์ในแต่ละโหนดเท่ากัน และค่อนข้างใช้เนื้อที่จำนวนมาก เนื่องจากแต่ละโหนดมีจำนวนโหนดลูกไม่เท่ากันหรือบางโหนดไม่มีลูกเลย ถ้าเป็นทรีที่แต่ละโหนดมีจำนวนโหนดลูกที่แตกต่างกันมาก จะเป็นการสิ้นเปลืองเนื้อที่ในหน่วยความจำโดยเปล่าประโยชน์
2. แทนที่ด้วยไบนารีทรี
เป็นวิธีแก้ปัญหาเพื่อลดการสิ้นเปลืองเนื้อที่ในหน่วยความจำ โดยกำหนดให้แต่ละโหนดมีจำนวนลิงค์ฟิลด์สองลิงค์ฟิลด์
- ลิงค์ฟิลด์แรกเก็บที่อยู่ของโหนดลูกคนโต
- ลิงคฟิลด์ที่สองเก็บที่อยู่ของโหนดพี่น้องที่เป็นโหนดถัดไปโหนดใดไม่มีโหนดลูกหรือไม่มีโหนดพี่น้องให้ค่าพอยเตอร์ในลิงค์ฟิลด์มีค่าเป็น Null
การแปลงทรีทั่วไปให้เป็นไบนารีทรี มีลำดับขั้นตอนการแปลงดังต่อไปนี้
1.ให้โหนดแม่ชี้ไปยังโหนดลูกคนโต แล้วลบความสัมพันธ์ ระหว่างโหนดแม่และโหนดลูกอื่นๆ
2.ให้เชื่อมความสัมพันธ์ระหว่างโหนดพี่น้อง
3.จับให้ทรีย่อยทางขวาเอียงลงมา 45 องศา
การท่องไปในไบนารีทรี
ปฏิบัติการที่สำคัญในไบนารีทรี คือการท่องไปในไบนารี เพื่อเข้าไปเยือนทุกๆโหนดในทรี สามารถเยือนโหนดทุกๆโหนดๆละหนึ่งครั้ง โหนดที่ถูกเยือนอาจเป็นโหนดแ่ม่ (แทนด้วย N) ทรีย่อยทางซ้าย (แทนด้วย L) หรือทรีย่อยทางขวา (แทนด้วย R)
ไม่มีความคิดเห็น:
แสดงความคิดเห็น