Tree
ทรี (Tree) เป็นโครงสร้างข้อมูลที่ความสัมพันธ์
ระหว่าง โหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับ
ชั้น (Hierarchical Relationship)
แต่ละโหนดจะมีความสัมพันธ์กับโหนดใน
ระดับที่ต่ำลงมา หนึ่งระดับได้หลาย ๆ โหนด
เรียกโหนดดังกล่าวว่า โหนดแม่ (Parent or
Mother Node)
โหนดที่อยู่ต่ำกว่าโหนดแม่อยู่หนึ่งระดับ
เรียกว่า โหนดลูก (Child or Son Node)
โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่
เรียกว่า โหนดราก (Root Node)
โหนดที่มีโหนดแม่เป็นโหนดเดียวกัน
เรียกว่า โหนดพี่น้อง (Siblings)
โหนดที่ไม่มีโหนดลูก เรียกว่า
โหนดใบ (Leave Node)
เส้นเชื่อมแสดงความสัมพันธ์ระหว่าง
โหนดสองโหนดเรียกว่า กิ่ง (Branch)
นิยามของทรี
1. นิยามทรีด้วยนิยามของกราฟ
ทรี คือ กราฟที่ต่อเนื่องโดยไม่มี
วงจรปิด (loop) ในโครงสร้าง โหนดสองโหนด
ใด ๆ ในทรีต้องมีทางติดต่อกัน
ทางเดียวเท่านั้น และทรีที่มี N โหนด ต้องมีกิ่ง
ทั้งหมด N-1 เส้น
2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟ
ทรีประกอบด้วยสมาชิกที่เรียกว่า
โหนด โดยที่ ถ้าว่าง ไม่มีโหนดใด ๆ
เรียกว่านัลทรี (Null Tree) และถ้ามีโหนด
หนึ่งเป็นโหนดราก ส่วนที่เหลือจะแบ่งเป็น
ทรีย่อย (Sub Tree)
T1, T2, T3,…,Tk โดยที่ k>=0
และทรีย่อย
ต้องมีคุณสมบัติเป็นทรี
นิยามที่เกี่ยวข้องกับทรี
1. ฟอร์เรสต์ (Forest)
หมายถึง กลุ่มของทรีที่เกิดจากการ
เอาโหนดรากของทรีออก
หรือ เซตของทรีที่แยกจากกัน(Disjoint Trees)
2. ทรีที่มีแบบแผน (Ordered Tree)
หมายถึง ทรีที่โหนดต่าง ๆ ในทรีนั้นมี
ความสัมพันธ์ที่แน่นอน เช่น ไปทางขวา
ไปทางซ้าย
3. ทรีคล้าย (Similar Tree)
คือทรีที่มีโครงสร้างเหมือนกัน หรือทรีที่มี
รูปร่างของทรีเหมือนกัน โดยไม่คำนึงถึง
ข้อมูลที่อยู่ในแต่ละโหนด
4. ทรีเหมือน (Equivalent Tree)
คือทรีที่เหมือนกันโดยสมบูรณ์ โดยต้องเป็นทรีที่
คล้ายกันและแต่ละโหนดในตำแหน่ง
เดียวกันมีข้อมูลเหมือนกัน
5. กำลัง (Degree)
หมายถึงจำนวนทรีย่อยของโหนด นั้น ๆ
ในรูปโหนด “B” มีกำลังเป็น 1 เพราะ
มีทรีย่อย คือ {“D”}
ส่วนโหนด “C” มีค่ากำลังเป็นสอง เพราะ
มีทรีย่อย คือ {“E”, “G”, “H”, “I”} และ {“F”}
6. ระดับของโหนด (Level of Node)
คือระยะทางในแนวดิ่งของโหนดนั้น ๆ ที่อยู่ห่างจากโหนด
ราก เมื่อกำหนดให้ โหนดรากของทรีนั้นอยู่ระดับ 1
และกิ่งแต่ละกิ่งมีความเท่ากันหมด คือ ยาวเท่ากับ 1
หน่วย ซึ่งระดับของโหนดจะเท่ากับจำนวนกิ่งที่น้อยที่สุด
จากโหนดรากไปยังโหนดใด ๆ บวกด้วย 1
และจำนวนเส้นทางตามแนวดิ่งของโหนดใด ๆ ซึ่งห่าง
จากโหนดราก เรียกว่า ความสูง (Height)
หรือความลึก (Depth)
การแทนที่ทรีในหน่วยความจำหลัก
การแทนที่โครงสร้างข้อมูลแบบทรีในความจำหลัก
จะมีพอยเตอร์เชื่อมโยงจากโหนดแม่ไปยังโหนดลูก แต่ละ
โหนดต้องมีลิงค์ฟิลด์เพื่อเก็บที่อยู่ของโหนดลูกต่าง ๆ นั่นคือ
จำนวน ลิงค์ฟิลด์ของแต่ละโหนดขึ้นอยู่กับจำนวนของ
โหนดลูก
1. โหนดแต่ละโหนดเก็บพอยเตอร์ชี้ไปยังโหนดลูก
ทุกโหนด การแทนที่ทรีด้วยวิธีนี้ จะให้จำนวนฟิลด์ในแต่ละ
โหนดเท่ากันโดยกำหนดให้มีขนาดเท่ากับจำนวนโหนดลูก
ของโหนดที่มีลูกมากที่สุด โหนดใดไม่มีโหลดลูกก็ให้ค่า
พอยเตอร์ในลิงค์ฟิลด์นั้นมีค่าเป็น Null
และให้ลิงค์ฟิลด์แรกเก็บค่าพอยเตอร์ชี้ไปยังโหนด ลูกลำดับ
ที่หนึ่ง ลิงค์ฟิลด์ที่สองเก็บค่าพอยเตอร์ชี้ไปยังโหนดลูก
ลำดับที่สอง และลิงค์ฟิลด์อื่นเก็บค่าพอยเตอร์ของโหนดลูก
ลำดับ ถัดไปเรื่อย ๆ
2. แทนทรีด้วยไบนารีทรี
เป็นวิธีแก้ปัญหาเพื่อลดการ สิ้นเปลืองเนื้อที่ในหน่วยความจำก็คือ
กำหนดลิงค์ฟิลด์ให้มีจำนวนน้อยที่สุดเท่าที่จำเป็นเท่านั้น
โดยกำหนดให้แต่ละโหนดมีจำนวนลิงค์ฟิลด์สองลิงค์ฟิลด์
-ลิงค์ฟิลด์แรกเก็บที่อยู่ของโหนดลูกคนโต
-ลิงค์ฟิลด์ที่สองเก็บที่อยู่ของโหนดพี่น้องที่เป็นโหนดถัดไป
โหนดใดไม่มีโหนดลูกหรือไม่มีโหนดพี่น้องให้ค่าพอยน์เตอร์ใน
ลิงค์ฟิลด์มีค่าเป็น Null
การแปลงทรีทั่วไปให้เป็นไบนารีทรี
ขั้นตอนการแปลงทรีทั่วๆ ไปให้เป็น
ไบนารีทรี มีลำดับขั้นตอนการแปลง ดังต่อไปนี้
1. ให้โหนดแม่ชี้ไปยังโหนดลูกคนโต แล้วลบ
ความสัมพันธ์ ระหว่างโหนดแม่และโหนดลูกอื่น ๆ
2. ให้เชื่อมความสัมพันธ์ระหว่างโหนดพี่น้อง
3. จับให้ทรีย่อยทางขวาเอียงลงมา 45 องศา
1. การท่องไปแบบพรีออร์เดอร์
(Preorder Traversal)
เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี
NLR มีขั้นตอนการเดินดังต่อไปนี้
(1) เยือนโหนดราก
(2) ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
(3) ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์
2.การท่องไปแบบอินออร์เดอร์
(Inorder Traversal)
เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ
ในทรีด้วยวิธี LNR
มีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
(2) เยือนโหนดราก
(3) ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์
3. การท่องไปแบบโพสออร์เดอร์
(Postorder Traversal)
เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ
ในทรีด้วยวิธี LRN มีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบโพสต์ออร์เดอร์
(2) ท่องไปในทรีย่อยทางขวาแบบโพสต์ออร์เดอร์
(3) เยือนโหนดราก
ไบนารีเซิร์ชทรี
ไบนารีเซิร์ชทรี (Binary Search Tree)
เป็นไบนารีทรีที่มีคุณสมบัติที่ว่าทุก ๆ โหนด
ในทรี ค่าของโหนดรากมีค่ามากกว่าค่าของทุก
โหนดในทรีย่อยทางซ้าย และมีค่าน้อยกว่า
หรือเท่ากับค่าของทุกโหนดในทรีย่อยทางขวา
และในแต่ละทรีย่อยก็มี คุณสมบัติเช่นเดียวกัน
ไม่มีความคิดเห็น:
แสดงความคิดเห็น