Sorting
การเรียงลำดับ (sorting) เป็นการจัดให้เป็นระเบียบมีแบบแผน ช่วยให้การค้นหาสิ่งของหรือข้อมูล ซึ่งจะสามารถกระทำได้รวดเร็วและมีประสิทธิภาพ เช่น การค้นหาความหมายของคำในพจนานุกรม ทำได้ค่อนข้างง่ายและรวดเร็วเนื่องจากมีการเรียงลำดับคำตามตัวอักษรไว้อย่างมีระบบและเป็นระเบียบ หรือ การค้นหาหมายเลขโทรศัพท์ในสมุดโทรศัพท์ ซึ่งมีการเรียงลำดับ ตามชื่อและชื่อสกุลของ
เจ้าของโทรศัพท์ไว้ ทำให้สามารถค้นหา หมายเลขโทรศัพท์ของคนที่ต้องการได้อย่างรวดเร็ว เป็นต้น
การเรียงลำดับแบบเร็ว (quick sort)เป็นวิธีการเรียงลำดับที่ใช้เวลาน้อยเหมาะสำหรับข้อมูลที่มีจำนวนมากที่ต้องการความรวดเร็ว
ในการทำงาน วิธีนี้จะเลือกข้อมูลจากกลุ่มข้อมูลขึ้นมาหนึ่งค่าเป็นค่าหลัก แล้วหาตำแหน่งที่ถูกต้องให้กับค่าหลักนี้ เมื่อได้ตำแหน่งที่ถูกต้องแล้ว ใช้ค่าหลักนี้เป็นหลักในการแบ่งข้อมูลออกเป็นสองส่วนถ้าเป็นการเรียงลำดับจากน้อยไปมาก ส่วนแรกอยู่ในตอนหน้าข้อมูล ทั้งหมดจะมีค่าน้อยกว่าค่าหลักที่เป็นตัวแบ่งส่วน
กรณีที่ดีที่สุด คือ กรณีที่ค่าหลักที่เลือกแบ่งแล้วข้อมูลอยู่ตรงกลางกลุ่มพอดี และในแต่ละส่วนย่อยก็เช่นเดียวกันจำนวนครั้งของการเปรียบเทียบเป็นดังนี้จำนวนครั้งของการเปรียบเทียบ = n log2 n ครั้ง
กรณีที่แย่ที่สุด คือ กรณีที่ข้อมูลมีการเรียงลำดับอยู่แล้ว อาจจะเรียงจากน้อยไปมากหรือจากมากไปน้อย หรือค่าหลักที่เลือกในแต่ละครั้งเป็นค่าหลักที่น้อยที่สุดหรือมากที่สุด จำนวนครั้งของการเปรียบเทียบจะมากที่สุดดังนี้จำนวนครั้งของการเปรียบเทียบ
= (n −1) + (n −2) + . . . + 3 + 2 + 1
= n (n −1) / 2 ครั้ง
การค้นหาข้อมูล (Searching)
แบ่งเป็น 2 ประเภท ตามแหล่งที่จัดเก็บข้อมูลเช่นเดียวกับการเรียงลำดับ
การค้นหาข้อมูลแบบภายใน (Internal Searching)
การค้นหาข้อมูลแบบภายนอก (External Searching)
1. การค้นหาแบบเชิงเส้นหรือการค้นหาตามลำดับ(Linear)เป็นวิธีที่ใช้กับข้อมูลที่ยังไม่ได้เรียงลำดับ
2. การค้นหาแบบเซนทินัล (Sentinel)เป็นวิธีที่การค้นหาแบบเดียวกับวิธีการค้นหาแบบเชิงเส้นแต่ประสิทธิภาพดีกว่าตรงที่เปรียบเทียบน้อยครั้งกว่า พัฒนามาจากอัลกอริทึมแบบเชิงเส้น
การค้นหาแบบไบนารี (Binary Search)
การค้นหาแบบไบนารีใช้กับข้อมูลที่ ถูกจัดเรียงแล้วเท่านั้นหลักการของการค้นหาคือ ข้อมูลถูกแบ่งออกเป็นสองส่วนแล้วนำค่ากลางข้อมูลมาเปรียบเทียบกับคีย์ที่ต้องการหา
1.หาตัวแทนข้อมูลเพื่อนำมาเปรียบเทียบกับค่าที่ต้องการค้น
ตำแหน่งตัวแทนข้อมูลหาได้จากสูตร
mid = (low+high)/2
mid คือ ตำแหน่งกลาง ,low คือ ตำแหน่งต้นแถวลำดับ
high คือ ตำแหน่งท้ายของแถวลำดับ
2. นำผลการเปรียบเทียบกรณีที่หาไม่พบมาใช้ในการค้นหารอบต่อไปหาในส่วน A ถ้าค่าที่จะหานั้นน้อยกว่าค่าที่ตำแหน่งกลาง ในทางกลับกันหาในส่วน Bถ้าค่าที่จะหานั้นมากกว่าค่าตำแหน่งกลาง
วันอังคารที่ 22 กันยายน พ.ศ. 2552
วันอาทิตย์ที่ 6 กันยายน พ.ศ. 2552
สรุปการเรียน DTS07-02-09-2552
Graph
กราฟ (Graph) เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้น อีกชนิดหนึ่ง กราฟเป็นโครงสร้างข้อมูลที่มีการนำไปใช้ในงานที่เกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างซับซ้อนเช่น การวางข่าย งานคอมพิวเตอร์ การวิเคราะห์เส้นทางวิกฤติ และปัญหาเส้นทางที่สั้นที่สุด เป็นต้น
การท่องไปในกราฟ
1. การค้นหาแบบกว้าง (Breadth-first Search)
2. การค้นหาแบบลึก (Depth-first Search)
การท่องไปในกราฟ
1. การค้นหาแบบกว้าง (Breadth-first Search)กำหนดจุดเริ่มต้น ถ้าให้เริ่มต้นที่จุด A การค้นหาจะเริ่มต้นที่โหนดประชิดของ A จนครบทุกจำนวนของโหนดประชิดจากภาพที่ปรากฏต่อไปนี้ โหนด N1 โหนด N2 ไปเรื่อย ๆจนจบที่โหนด Nk การค้นหาแบบกว้างจะค้นหาต่อที่โหนดประชิดของ N1 ซึ่งเป็นโหนด ประชิดแรกของโหนด Aแบบแผนการค้นหา จะเป็นแบบเดียวกับโหนด A หลังจากเสร็จสิ้นการค้นหาจะดำเนินการค้นหาต่อที่ โหนด N2 จนสุดท้ายจบที่ โหนด Nk ในหารค้นหาแบบกว้างจะใช้คิวเก็บลำดับ
ของโหนด ที่ต้องการค้นหาต่อไป
1.1 การค้นหาแบบกว้าง ในกราฟไม่มีทิศทาง รายชื่อโหนดที่พบจากการค้นหาแบบกว้าง มีได้หลายรายการขึ้นกับลำดับการเรียงโหนดประชิดดังตารางต่อไปนี้ แสดงค่าโหนดประชิดของโหนดทุกโหนด ซึ่งสร้างมาจากกราฟถ้ากำหนดให้เริ่มต้นค้นที่โหนด 1 รายชื่อ
โหนดที่พบเรียงตามลำดับดังนี้ 2 3 4 5 6 7 และ 8ถ้ากำหนดให้เริ่มต้นค้นที่โหนด 6 รายชื่อโหนดที่พบเรียงลำดับดังนี้ 4 8 1 7 5 2 และ 3
1.2 การค้นหาแบบกว้าง ในกราฟมีทิศทาง การค้นหาโหนดในกราฟทำได้ง่ายขึ้นถ้าใช้คิวเก็บลำดับของโหนดประชิดที่ต้องเยี่ยมต่อไป และใช้ตารางเก็บค่าโหนดประชิดของโหนดทุกโหนดในกราฟ การค้นหาแบบกว้างในกราฟจะพบโหนดตามลำดับดังนี้ A F C B D G E J และ K
2. การค้นหาแบบลึก (Depth-first Search)
จะต่างตรงที่จุดเริ่มต้นที่จะไปเยี่ยมโหนดในกราฟมีหลายจุด จึงต้องกำหนดจุดเริ่มต้นสำหรับเยี่ยมเป็นจุดแรก การค้นหาแบบลึกใช้หลักการคล้ายแบบลำดับของต้นไม้จากภาพในตัวอย่างต่อไปจะใช้โหนด A เป็นจุดเริ่มต้น การค้นหาจะเริ่มจากโหนดประชิดค่าแรกของโหนด A คือโหนด N1 แล้วดูว่าโหนดN1 มีโหนดประชิดหรือไม่ถ้ามีก็ค้นหาต่อไป โดยใช้แบบแผนการค้น เหมือนโหนด A จนครบ แล้ว
กลับไปค้นหาที่โหนดประชิดตัวที่ 2 ของโหนด A คือ โหนด N2 โดยใช้แบบแผนการค้นเดียวกับโหนด N1 ทำแบบเดียวกันจนครบถึงโหนด Nk
กราฟ มีน้ำหนัก หมายถึง กราฟที่ทุกเอดจ์ มีค่าน้ำหนักกำกับ ซึ่งค่าน้ำหนักอาจสื่อถึงระยะทาง เวลา ค่าใช้จ่าย เป็นต้น นิยมนำไปใช้
แก้ปัญหาหลัก ๆ 2 ปัญหา คือ
1. การสร้างต้นไม้ทอดข้ามน้อยที่สุด
(Minimum Spanning Trees :MST)
2. การหาเส้นทางที่สั้นที่สุด
(Shortest path)
1. การสร้างต้นไม้ทอดข้ามน้อยที่สุด
(Minimum Spanning Trees :MST)
Kruskal’s Algorithm
1. เรียงลำดับเอดจ์ ตามน้ำหนัก
2. สร้างป่าที่ประกอบด้วยต้นไม้ว่างที่มีแต่โหนด และไม่มีเส้นเชื่อม
3. เลือกเอดจ์ที่มีน้ำหนักน้อยที่สุดและยังไม่เคยถูกเลือกเลย ถ้ามีน้ำหนักซ้ำกันหลายค่าให้สุ่มมา 1เส้น
4. พิจารณาเอดจ์ที่จะเลือก ถ้านำมาประกอบในต้นไม้ทอดข้ามน้อยที่สุดแล้วเกิด วงรอบ ให้ตัดทิ้งนอกนั้นให้นำมาประกอบเป็นเอดจ์ในต้นไม้ทอดข้ามน้อยที่สุด
5. ตรวจสอบเอดจ์ที่ต้องอ่านในกราฟ ถ้ายังอ่านไม่หมดให้ไปทำข้อ 3
6. เลือกเอดจ์ที่เหลือและมีน้ำหนักน้อยที่สุดมา ตามตัวอย่าง คือ edges(6,7) edges (3,4 ) edges (5,6 ) นำมาเชื่อมต่อต้นไม่ในป่า
7. เลือกเอดจ์ที่เหลือและมีน้ำหนักน้อยที่สุด ตามตัวอย่าง คือ edges (5,7) จากนั้นให้ตัดทิ้งไม่นำมาเชื่อมต่อต้นไม้ในป่า เนื่องจากทำให้เกิดวงรอบ
8. เลือกเอดจ์ที่เหลือและมีน้ำหนักน้อยที่สุด ตามตัวอย่าง คือ edges (1,4) จากนั้นให้ตัดทิ้งไม่นำมาเชื่อมต่อต้นไม้ในป่า เนื่องจากทำให้เกิดวงรอบ
9. เลือกเอดจ์ที่เหลือและมีน้ำหนักน้อยที่สุดมา ตามตัวอย่าง คือ edges(3,5) นำมาเชื่อมต่อต้นไม่ในป่า เนื่องจากเป็นเอดจ์สุดท้าย
2. การหาเส้นทางที่สั้นที่สุด (Shortestpath) Dijkstra’s Algorithmหาเส้นทางที่สั้นที่สุดจากโหนดต้นทางไปโหนด
ใด ๆ ในกราฟ มีน้ำหนัก และน้ำหนักไม่เป็นลบ
การคำนวณหาระยะทางสั้นที่สุด จากโหนดต้นทางคือโหนด 1
ไปยังโหนดใด ๆ มีวิธีคำนวณดังนี้
1) เริ่มต้นโหนดที่เป็นจุดเริ่มต้น คือ โหนด 1 ไปไว้ที่เซต Sจากนั้นนำค่าน้ำหนักบนเอดจ์ (1,2) เอดจ์ (1,4) เอดจ์ (1,5)
และ เอดจ์ (1,6) ไปเขียนในตารางสำหรับ โหนด 3 ไม่ได้ เชื่อมต่อกับโหนดที่ 1 ดังนั้นจึงใช้ค่าอินฟินีตี้ (Infinity) แทน แสดงในตารางที่ปรากฏในบรรทัดIter= Initial
2) เลือก W ที่มีระยะทางสั้นที่สุด คือ โหนด 2 ไปไว้ที่เซต Sคำนวณ ระยะทางใหม่ ระยะทางสั้นที่สุด จากโหนด 1 ไปโหนด
อื่น ๆ เท่าเดิม ยกเว้นโหนด 3 ซึ่งขณะนี้มีวิถีกับโหนด 1 ดังนี้ (1,2,3) ระยะทางที่ได้มาจากน้ำหนักบนเอจน์เป็น (1,2) และ เอดจ์ (2,3)รวมกันคือ 70 จึงเขียนค่า 70 แทนค่าอินฟินีตีเดิม
3) เลือก W ที่มีระยะทางสั้นที่สุดคือโหนด 5 ไปไว้ที่เซต Sคำนวณหาระยะทางใหม่ปรากฏว่าถึงแม้จะมีโหนด 5 อยู่ในวิถีเส้นทางใหม่ แต่ระยะทางจากวิถีเดิมสั้นกว่า จึงคงค่าเดิมไว้ดังแสดงในตาราง
4) เลือก W ที่มีระยะทางสั้นที่สุดคือโหนด 4 ไปไว้ที่เซต Sคำนวณหาระยะทางใหม่ปรากฏว่า มีวิถีจากโหนด 1 ไปโหนด
3 รวม 2 วิถีดังนี้
วิถีที่ 1 คือ (1,2 และ3) มีค่าน้ำหนัก = 30+40 =70
วิถีที่ 2 คือ (1,4 และ3) มีค่าน้ำหนัก = 50+10 =60
เลือกน้ำหนักจากวิถีที่สั้นที่สุด คือ 60 ไปเขียนแทนค่าเดิม
5) เลือก W ที่มีระยะทางสั้นที่สุดคือโหนด 3 ไปไว้ที่เซต Sคำนวณหาระยะทางใหม่ปรากฏว่า มีวิถีจากโหนด 1 ไปโหนด 3
กราฟ (Graph) เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้น อีกชนิดหนึ่ง กราฟเป็นโครงสร้างข้อมูลที่มีการนำไปใช้ในงานที่เกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างซับซ้อนเช่น การวางข่าย งานคอมพิวเตอร์ การวิเคราะห์เส้นทางวิกฤติ และปัญหาเส้นทางที่สั้นที่สุด เป็นต้น
การท่องไปในกราฟ
1. การค้นหาแบบกว้าง (Breadth-first Search)
2. การค้นหาแบบลึก (Depth-first Search)
การท่องไปในกราฟ
1. การค้นหาแบบกว้าง (Breadth-first Search)กำหนดจุดเริ่มต้น ถ้าให้เริ่มต้นที่จุด A การค้นหาจะเริ่มต้นที่โหนดประชิดของ A จนครบทุกจำนวนของโหนดประชิดจากภาพที่ปรากฏต่อไปนี้ โหนด N1 โหนด N2 ไปเรื่อย ๆจนจบที่โหนด Nk การค้นหาแบบกว้างจะค้นหาต่อที่โหนดประชิดของ N1 ซึ่งเป็นโหนด ประชิดแรกของโหนด Aแบบแผนการค้นหา จะเป็นแบบเดียวกับโหนด A หลังจากเสร็จสิ้นการค้นหาจะดำเนินการค้นหาต่อที่ โหนด N2 จนสุดท้ายจบที่ โหนด Nk ในหารค้นหาแบบกว้างจะใช้คิวเก็บลำดับ
ของโหนด ที่ต้องการค้นหาต่อไป
1.1 การค้นหาแบบกว้าง ในกราฟไม่มีทิศทาง รายชื่อโหนดที่พบจากการค้นหาแบบกว้าง มีได้หลายรายการขึ้นกับลำดับการเรียงโหนดประชิดดังตารางต่อไปนี้ แสดงค่าโหนดประชิดของโหนดทุกโหนด ซึ่งสร้างมาจากกราฟถ้ากำหนดให้เริ่มต้นค้นที่โหนด 1 รายชื่อ
โหนดที่พบเรียงตามลำดับดังนี้ 2 3 4 5 6 7 และ 8ถ้ากำหนดให้เริ่มต้นค้นที่โหนด 6 รายชื่อโหนดที่พบเรียงลำดับดังนี้ 4 8 1 7 5 2 และ 3
1.2 การค้นหาแบบกว้าง ในกราฟมีทิศทาง การค้นหาโหนดในกราฟทำได้ง่ายขึ้นถ้าใช้คิวเก็บลำดับของโหนดประชิดที่ต้องเยี่ยมต่อไป และใช้ตารางเก็บค่าโหนดประชิดของโหนดทุกโหนดในกราฟ การค้นหาแบบกว้างในกราฟจะพบโหนดตามลำดับดังนี้ A F C B D G E J และ K
2. การค้นหาแบบลึก (Depth-first Search)
จะต่างตรงที่จุดเริ่มต้นที่จะไปเยี่ยมโหนดในกราฟมีหลายจุด จึงต้องกำหนดจุดเริ่มต้นสำหรับเยี่ยมเป็นจุดแรก การค้นหาแบบลึกใช้หลักการคล้ายแบบลำดับของต้นไม้จากภาพในตัวอย่างต่อไปจะใช้โหนด A เป็นจุดเริ่มต้น การค้นหาจะเริ่มจากโหนดประชิดค่าแรกของโหนด A คือโหนด N1 แล้วดูว่าโหนดN1 มีโหนดประชิดหรือไม่ถ้ามีก็ค้นหาต่อไป โดยใช้แบบแผนการค้น เหมือนโหนด A จนครบ แล้ว
กลับไปค้นหาที่โหนดประชิดตัวที่ 2 ของโหนด A คือ โหนด N2 โดยใช้แบบแผนการค้นเดียวกับโหนด N1 ทำแบบเดียวกันจนครบถึงโหนด Nk
กราฟ มีน้ำหนัก หมายถึง กราฟที่ทุกเอดจ์ มีค่าน้ำหนักกำกับ ซึ่งค่าน้ำหนักอาจสื่อถึงระยะทาง เวลา ค่าใช้จ่าย เป็นต้น นิยมนำไปใช้
แก้ปัญหาหลัก ๆ 2 ปัญหา คือ
1. การสร้างต้นไม้ทอดข้ามน้อยที่สุด
(Minimum Spanning Trees :MST)
2. การหาเส้นทางที่สั้นที่สุด
(Shortest path)
1. การสร้างต้นไม้ทอดข้ามน้อยที่สุด
(Minimum Spanning Trees :MST)
Kruskal’s Algorithm
1. เรียงลำดับเอดจ์ ตามน้ำหนัก
2. สร้างป่าที่ประกอบด้วยต้นไม้ว่างที่มีแต่โหนด และไม่มีเส้นเชื่อม
3. เลือกเอดจ์ที่มีน้ำหนักน้อยที่สุดและยังไม่เคยถูกเลือกเลย ถ้ามีน้ำหนักซ้ำกันหลายค่าให้สุ่มมา 1เส้น
4. พิจารณาเอดจ์ที่จะเลือก ถ้านำมาประกอบในต้นไม้ทอดข้ามน้อยที่สุดแล้วเกิด วงรอบ ให้ตัดทิ้งนอกนั้นให้นำมาประกอบเป็นเอดจ์ในต้นไม้ทอดข้ามน้อยที่สุด
5. ตรวจสอบเอดจ์ที่ต้องอ่านในกราฟ ถ้ายังอ่านไม่หมดให้ไปทำข้อ 3
6. เลือกเอดจ์ที่เหลือและมีน้ำหนักน้อยที่สุดมา ตามตัวอย่าง คือ edges(6,7) edges (3,4 ) edges (5,6 ) นำมาเชื่อมต่อต้นไม่ในป่า
7. เลือกเอดจ์ที่เหลือและมีน้ำหนักน้อยที่สุด ตามตัวอย่าง คือ edges (5,7) จากนั้นให้ตัดทิ้งไม่นำมาเชื่อมต่อต้นไม้ในป่า เนื่องจากทำให้เกิดวงรอบ
8. เลือกเอดจ์ที่เหลือและมีน้ำหนักน้อยที่สุด ตามตัวอย่าง คือ edges (1,4) จากนั้นให้ตัดทิ้งไม่นำมาเชื่อมต่อต้นไม้ในป่า เนื่องจากทำให้เกิดวงรอบ
9. เลือกเอดจ์ที่เหลือและมีน้ำหนักน้อยที่สุดมา ตามตัวอย่าง คือ edges(3,5) นำมาเชื่อมต่อต้นไม่ในป่า เนื่องจากเป็นเอดจ์สุดท้าย
2. การหาเส้นทางที่สั้นที่สุด (Shortestpath) Dijkstra’s Algorithmหาเส้นทางที่สั้นที่สุดจากโหนดต้นทางไปโหนด
ใด ๆ ในกราฟ มีน้ำหนัก และน้ำหนักไม่เป็นลบ
การคำนวณหาระยะทางสั้นที่สุด จากโหนดต้นทางคือโหนด 1
ไปยังโหนดใด ๆ มีวิธีคำนวณดังนี้
1) เริ่มต้นโหนดที่เป็นจุดเริ่มต้น คือ โหนด 1 ไปไว้ที่เซต Sจากนั้นนำค่าน้ำหนักบนเอดจ์ (1,2) เอดจ์ (1,4) เอดจ์ (1,5)
และ เอดจ์ (1,6) ไปเขียนในตารางสำหรับ โหนด 3 ไม่ได้ เชื่อมต่อกับโหนดที่ 1 ดังนั้นจึงใช้ค่าอินฟินีตี้ (Infinity) แทน แสดงในตารางที่ปรากฏในบรรทัดIter= Initial
2) เลือก W ที่มีระยะทางสั้นที่สุด คือ โหนด 2 ไปไว้ที่เซต Sคำนวณ ระยะทางใหม่ ระยะทางสั้นที่สุด จากโหนด 1 ไปโหนด
อื่น ๆ เท่าเดิม ยกเว้นโหนด 3 ซึ่งขณะนี้มีวิถีกับโหนด 1 ดังนี้ (1,2,3) ระยะทางที่ได้มาจากน้ำหนักบนเอจน์เป็น (1,2) และ เอดจ์ (2,3)รวมกันคือ 70 จึงเขียนค่า 70 แทนค่าอินฟินีตีเดิม
3) เลือก W ที่มีระยะทางสั้นที่สุดคือโหนด 5 ไปไว้ที่เซต Sคำนวณหาระยะทางใหม่ปรากฏว่าถึงแม้จะมีโหนด 5 อยู่ในวิถีเส้นทางใหม่ แต่ระยะทางจากวิถีเดิมสั้นกว่า จึงคงค่าเดิมไว้ดังแสดงในตาราง
4) เลือก W ที่มีระยะทางสั้นที่สุดคือโหนด 4 ไปไว้ที่เซต Sคำนวณหาระยะทางใหม่ปรากฏว่า มีวิถีจากโหนด 1 ไปโหนด
3 รวม 2 วิถีดังนี้
วิถีที่ 1 คือ (1,2 และ3) มีค่าน้ำหนัก = 30+40 =70
วิถีที่ 2 คือ (1,4 และ3) มีค่าน้ำหนัก = 50+10 =60
เลือกน้ำหนักจากวิถีที่สั้นที่สุด คือ 60 ไปเขียนแทนค่าเดิม
5) เลือก W ที่มีระยะทางสั้นที่สุดคือโหนด 3 ไปไว้ที่เซต Sคำนวณหาระยะทางใหม่ปรากฏว่า มีวิถีจากโหนด 1 ไปโหนด 3
สรุปการเรียน DTS06-26-08-2552
Tree
ทรี (Tree) เป็นโครงสร้างข้อมูลที่ความสัมพันธ์ระหว่าง โหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับชั้น (Hierarchical Relationship) แต่ละโหนดจะมีความสัมพันธ์กับโหนดในระดับที่ต่ำลงมา หนึ่งระดับได้หลาย ๆ โหนดรียกโหนดดังกล่าวว่า
โหนดแม่ (Parent orMother Node)โหนดที่อยู่ต่ำกว่าโหนดแม่อยู่หนึ่งระดับเรียกว่า โหนดลูก (Child or Son Node)
โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่เรียกว่า โหนดราก (Root Node)โหนดที่มีโหนดแม่เป็นโหนดเดียวกันเรียกว่า โหนดพี่น้อง (Siblings)โหนดที่ไม่มีโหนดลูก เรียกว่าโหนดใบ (Leave Node)เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนด
เรียกว่า กิ่ง (Branch)
การท่องไปในไบนารีทรี (Traversing Binary Tree)
วิธีการท่องไปนั้นมีด้วยกันหลายแบบแล้วแต่ว่าต้องการลำดับขั้นตอนการเยือนอย่างไร โหนดที่ถูกเยือนอาจเป็นโหนดแม่ (แทนด้วย N)ทรีย่อยทางซ้าย (แทนด้วย L)หรือทรีย่อยทางขวา (แทนด้วย R)วิธีการท่องเข้าไปไบนารีทรีที่นิยมใช้กันมากเป็นการท่องจากซ้ายไปขวา 3 แบบแรกเท่านั้นคือ NLR LNR และ LRN
1. การท่องไปแบบพรีออร์เดอร์(Preorder Traversal)เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี NLR มีขั้นตอนการเดินดังต่อไปนี้
(1) เยือนโหนดราก
(2) ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
(3) ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์
2.การท่องไปแบบอินออร์เดอร์(Inorder Traversal)เป็นการเดินเข้าไปเยือนโหนดต่าง ๆในทรีด้วยวิธี LNR มีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
(2) เยือนโหนดราก
(3) ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์
3. การท่องไปแบบโพสออร์เดอร์(Postorder Traversal)เป็นการเดินเข้าไปเยือนโหนดต่าง ๆในทรีด้วยวิธี LRN มีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบโพสต์ออร์เดอร์
(2) ท่องไปในทรีย่อยทางขวาแบบโพสต์ออร์เดอร์
(3) เยือนโหนดราก
ไบนารีเซิร์ชทรี
ไบนารีเซิร์ชทรี (Binary Search Tree)เป็นไบนารีทรีที่มีคุณสมบัติที่ว่าทุก ๆ โหนดในทรี ค่าของโหนดรากมีค่ามากกว่าค่าของทุกโหนดในทรีย่อยทางซ้าย และมีค่าน้อยกว่าหรือเท่ากับค่าของทุกโหนดในทรีย่อยทางขวาและในแต่ละทรีย่อยก็มี คุณสมบัติเช่นเดียวกัน
ทรี (Tree) เป็นโครงสร้างข้อมูลที่ความสัมพันธ์ระหว่าง โหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับชั้น (Hierarchical Relationship) แต่ละโหนดจะมีความสัมพันธ์กับโหนดในระดับที่ต่ำลงมา หนึ่งระดับได้หลาย ๆ โหนดรียกโหนดดังกล่าวว่า
โหนดแม่ (Parent orMother Node)โหนดที่อยู่ต่ำกว่าโหนดแม่อยู่หนึ่งระดับเรียกว่า โหนดลูก (Child or Son Node)
โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่เรียกว่า โหนดราก (Root Node)โหนดที่มีโหนดแม่เป็นโหนดเดียวกันเรียกว่า โหนดพี่น้อง (Siblings)โหนดที่ไม่มีโหนดลูก เรียกว่าโหนดใบ (Leave Node)เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนด
เรียกว่า กิ่ง (Branch)
การท่องไปในไบนารีทรี (Traversing Binary Tree)
วิธีการท่องไปนั้นมีด้วยกันหลายแบบแล้วแต่ว่าต้องการลำดับขั้นตอนการเยือนอย่างไร โหนดที่ถูกเยือนอาจเป็นโหนดแม่ (แทนด้วย N)ทรีย่อยทางซ้าย (แทนด้วย L)หรือทรีย่อยทางขวา (แทนด้วย R)วิธีการท่องเข้าไปไบนารีทรีที่นิยมใช้กันมากเป็นการท่องจากซ้ายไปขวา 3 แบบแรกเท่านั้นคือ NLR LNR และ LRN
1. การท่องไปแบบพรีออร์เดอร์(Preorder Traversal)เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี NLR มีขั้นตอนการเดินดังต่อไปนี้
(1) เยือนโหนดราก
(2) ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
(3) ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์
2.การท่องไปแบบอินออร์เดอร์(Inorder Traversal)เป็นการเดินเข้าไปเยือนโหนดต่าง ๆในทรีด้วยวิธี LNR มีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
(2) เยือนโหนดราก
(3) ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์
3. การท่องไปแบบโพสออร์เดอร์(Postorder Traversal)เป็นการเดินเข้าไปเยือนโหนดต่าง ๆในทรีด้วยวิธี LRN มีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบโพสต์ออร์เดอร์
(2) ท่องไปในทรีย่อยทางขวาแบบโพสต์ออร์เดอร์
(3) เยือนโหนดราก
ไบนารีเซิร์ชทรี
ไบนารีเซิร์ชทรี (Binary Search Tree)เป็นไบนารีทรีที่มีคุณสมบัติที่ว่าทุก ๆ โหนดในทรี ค่าของโหนดรากมีค่ามากกว่าค่าของทุกโหนดในทรีย่อยทางซ้าย และมีค่าน้อยกว่าหรือเท่ากับค่าของทุกโหนดในทรีย่อยทางขวาและในแต่ละทรีย่อยก็มี คุณสมบัติเช่นเดียวกัน
สมัครสมาชิก:
บทความ (Atom)
