โครงสร้างข้อมูลแบบทรี
ทรี (Tree) เป็นโครงสร้างข้อมูลที่ความสัมพันธ์ ระหว่างโหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับชั้น (Hierarchical Relationship) ได้มีการนำรูปแบบทรีไปประยุกต์ใช้ในงานต่าง ๆ อย่างแพร่หลาย ส่วนมากจะใช้สำหรับแสดงความสัมพันธ์ระหว่างข้อมูล เช่น แผนผังองค์ประกอบของหน่วยงานต่าง ๆ โครงสร้างสารบัญหนังสือ แต่ละโหนดจะมีความสัมพันธ์กับโหนดในระดับที่ต่ำลงมาหนึ่งระดับได้หลาย ๆ โนด เรียกโหนดดังกล่าวว่า โหนดแม่ (Parent or Mother Node) โหนดที่อยู่ต่ำกว่าโหนดแม่อยู่หนึ่งระดับ เรียกว่า โหนดลูก(Child or Sun Node) โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่ เรียกว่า โหนดราก (Root Node) โหนดที่มีโหนดแม่เป็นโหนดเดียวกัน เรียกว่า โหนดพี่น้อง (Siblings) โหนดที่ไม่มีโหนดลูก เรียกว่า โหนดใบ (Leave Node) เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนดเรียกว่า กิ่ง (Branch) Ancestor Node หรือ บรรพบุรุษของโหนดใด ๆ หมายถึง โหนดที่มาก่อนโหนดใด ๆ Decendant Node หรือ ผู้สืบสกุล หมายถึง โหนดที่ตามหลังโหนดใด ๆ
นิยามของทรี
1. นิยามทรีด้วยนิยามของกราฟ
ทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด (loop) ในโครงสร้าง โหนดสองโหนดใด ๆ ในทรีต้องมีทางติดต่อกันทางเดียวเท่านั้น และทรีที่มี N โหนด ต้องมีกิ่งทั้งหมด N-1 เส้น
การเขียนรูปแบบทรี อาจเขียนได้ 4 แบบ คือ
2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟ
ทรีประกอบด้วยสมาชิกที่เรียกว่า โหนด โดยที่ถ้าว่าง ไม่มีโหนดเลย เรียกว่า นัลทรี (Null Tree) และถ้ามีโหนดหนึ่งเป็นโหนดราก ส่วนที่เหลือจะแบ่งเป็นทรีย่อย (Sub Tree) T1, T2, T3,…,Tk โดยที่ k>=0 และทรีย่อยต้องมีคุณสมบัติเป็นทรี
3. นิยามที่เกี่ยวข้องกับทรี
1. ฟอร์เรสต์ (Forest) หมายถึง กลุ่มของทรีที่เกิดจากการเอาโหนดรากของทรีออก หรือ เซตของทรีที่แยกจากกัน (Disjoint Trees)
2. ทรีที่มีแบบแผน (Ordered Tree) หมายถึง ทรีที่โหนดต่าง ๆ ในทรีนั้นมีความสัมพันธ์ที่แน่นอน เช่น ไปทางขวาไปทางซ้าย เป็นต้น
3. ทรีคล้าย (Similar Tree) คือ ทรีที่มีโครงสร้างเหมือนกัน หรือทรีที่มีรูปร่างของทรีเหมือนกัน โดยไม่คำนึงถึงข้อมูลที่อยู่ในแต่ละโหนด
4.ทรีเหมือน (Equivalent Tree) คือ ทรีที่เหมือนกันโดยสมบูรณ์ โดยต้องเป็นทรีที่คล้ายกันและแต่ละโหนดในตำแหน่งเดียวกันมีข้อมูลเหมือนกัน
5. กำลัง (Degree) หมายถึง จำนวนทรีย่อยของโหนดนั้น ๆ เช่น
6. ระดับของโหนด (Level of Node) คือ ระยะทางในแนวดิ่งของโหนดนั้น ๆ ที่อยู่ห่างจาก
โหนดราก เมื่อกำหนดให้โหนดรากของทรีนั้นอยู่ระดับ 1 และกิ่งแต่ละกิ่งมีความเท่ากันหมด คือ ยาวเท่ากับ 1 หน่วย ซึ่งระดับของโหนดจะเท่ากับจำนวนกิ่งที่น้อยที่สุดจากโหนดรากไปยังโหนดใด ๆ บวกด้วย 1 และจำนวนเส้นทางตามแนวดิ่งของโหนดใด ๆ ซึ่งห่างจากโหนดราก เรียกว่า ความสูง (Height) หรือความลึก (Depth)
แทนทรีด้วยไบนารีทรี เป็นวิธีแก้ปัญหาเพื่อลดการ สิ้นเปลืองเนื้อที่ในหน่วยความจำก็คือ กำหนดลิงค์ฟิลด์ให้มีจำนวนน้อยที่สุดเท่าที่จำเป็นเท่านั้น โดยกำหนดให้แต่ละโหนดมีจำนวนลิงค์ฟิลด์สองลิงค์ฟิลด์ ให้ลิงค์ฟิลด์แรกเก็บที่อยู่ของโหนดลูกคนโต และลิงค์ฟิลด์ที่สองเก็บที่อยู่ของโหนดพี่น้องที่เป็นโหนดถัดไป โหนดใดไม่มีโหนดลูกหรือไม่มีโหนดพี่น้องให้ค่าพอยน์เตอร์ในลิงค์ฟิลด์มีค่าเป็น Null
เป็นโครงสร้างข้อมูลแบบต้นไม้เช่นเดียวกับ Tree โดยประกอบด้วย Root node เพียงโหนดเดียวเท่านั้น โหนดที่เหลือจัดเป็นโหนดลูก (Child node) ซึ่งสามารถมีได้ตั้งแต่ 0 โหนด จนถึง 2 โหนด และโหนดลูกแต่ละโหนดสามารถเป็นโหนดแม่ (Parent node) ซึ่งแต่ละโหนดสามารถมีโหนดลูกได้ตั้งแต่ 0 จนถึง 2 โหนดเช่นเดียวกัน
สรุปได้ว่า ไบนารีทรี คือ โหนดทุกโหนดใน Binary tree จะมีลูกไม่เกินสอง คือ 0 , 1 หรือ 2
จะได้โครงสร้างทรีที่แต่ละโหนดมีลิงค์ฟิลด์แค่สองลิงค์ฟิลด์ ซึ่งช่วยให้ประหยัดเนื้อที่ในการจัดเก็บได้มาก เรียกโครงสร้างทรีที่แต่ละโหนดมีจำนวนโหนดลูกไม่เกินสอง หรือแต่ละโหนดมีจำนวนทรีย่อยไม่เกินสองนี้ว่า ไบนารีทรี (Binary Tree)
การท่องไปในทรี
การท่องไปในไบนารีทรีเป็นการเข้าไปเยือนโหนดทุกโหนดในทรีอย่างมีระบบซึ่งมีวิธีการเดินที่นิยมใช้อยู่ 3 วิธีคือ การท่องแบบพรีออร์เดอร์ การท่องแบบอินออร์เดอร์ และการท่องแบบโพสออร์เดอร์
โครงสร้างไบนารีทรีสามารถนำไปประยุกต์ใช้ในการเก็บนิพจน์คณิตศาสตร์ เรียกทรีนั้นว่า เอ็กซ์เพรสชันทรี แต่ละโหนดจะเก็บตัวดำเนินการและตัวถูกดำเนินการของนิพจน์คณิตศาสตร์ เมื่อเราท่องไปในเอ็กซ์เพรสชันทรีในแบบต่าง ๆ จะได้นิพจน์ในรูปแบบต่าง ๆ กันคือ ถ้าท่องแบบพรีออร์เดอร์ได้นิพจน์พรีฟิกซ์ ถ้าท่องแบบอินออร์เดอร์ได้นิพจน์อินฟิกซ์ และถ้าท่องแบบโพสออร์เดอร์ได้นิพจน์แบบโพสฟิกซ์ เป็นต้น
ไบนารีเซิรชทรีเป็นไบนารีทรีที่มีคุณสมบัติว่า ทุกโหนดในทรีค่าของโหนดรากมีค่ามากกว่าค่าของโหนดในทรีย่อยทางซ้ายและมีค่าน้อยกว่าหรือเท่ากับค่าของโหนดใน ทรีย่อยทางขวา และในแต่ละทรีย่อยก็มีเช่นเดียวกัน การค้นหาข้อมูลในไบนารีเซิรชทรี ทำให้การค้นหาข้อมูลใด ๆ ใช้เวลาน้อยลง เนื่องจากการค้นหาจะใช้ความสัมพันธ์ภายในโครงสร้างทำให้การค้นหาเร็วขึ้น นอกจากนี้ถ้าท่องไปในไบนารีเซิรชทรีแบบอินออร์เดอร์จะได้ข้อมูลเรียงลำดับจากน้อยไปมาก
ไม่มีความคิดเห็น:
แสดงความคิดเห็น