Data Structure and Algorithm

135 คร้งั ท่ี 1 จับกลุ่มข้อมลู กลุ่มละ 2 ตัว และทาการจัดเรียงภายในกลมุ่ 45 67 28 39 48 20 95 86 30 53 29 82 ขอ้ มลู หลงั จากจดั เรียงคร้ังที่ 1 45 67 28 39 20 48 86 95 30 53 29 82 ครง้ั ที่ 2 จบั กลมุ่ ข้อมูล กลมุ่ ละ 4 ตัว และทาการจัดเรียงภายในกลมุ่ 45 67 28 39 20 48 86 95 30 53 29 82 ข้อมลู หลังจากจดั เรยี งครั้งที่ 2 28 39 45 67 20 48 86 95 29 30 53 82 คร้งั ท่ี 3 จบั กลมุ่ ข้อมูล กลุ่มละ 8 ตวั และทาการจดั เรียงภายในกลุ่ม 28 39 45 67 20 48 86 95 29 30 53 82 ขอ้ มูลหลงั จากจัดเรียงครัง้ ที่ 3 20 28 39 45 48 67 86 95 29 30 53 82 จับกลุม่ ข้อมูล กลมุ่ ละ 16 ตวั และทาการจัดเรยี งภายในกลุ่ม คร้งั ที่ 4 20 28 39 45 48 67 86 95 29 30 53 82 ข้อมลู หลงั จากจัดเรยี งครง้ั ที่ 4 20 28 29 30 39 45 48 53 67 82 86 95 หลังจากจัดเรยี งข้อมูลแบบผสาน โดยจัดลาดับคา่ ต่าสดุ ไปหาคา่ สูงสุดการจัดเรยี งขอ้ มูล ไดด้ งั นี้ [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ชดุ ข้อมลู 45 67 28 39 48 20 95 86 30 53 29 82 ขอ้ มูลหลงั 20 28 29 30 39 45 48 53 67 82 86 95 จากจัดเรียง เอกสารประกอบการสอนรายวชิ าโครงสรา้ งข้อมูลและอลั กอริทมึ

136 ชอื่ หน่วยเรยี น : การค้นหาข้อมลู (Searching) รหัสวชิ า 13-132-207 หน่วยเรียนท่ี 8 เวลาสอน 12 คาบ ช่ือบทเรียน 8.1 การค้นหาข้อมลู แบบเรียงลาดับ (Sequential Searching) 8.2 การค้นหาข้อมูลแบบทวิภาค (Binary Searching) 8.3 การค้นหาข้อมูลแบบไบนารเี ซิรท์ ทรี (Binary Search Tree) 8.4 การค้นหาข้อมลู แบบแฮชชงิ่ (Hashing Search) จุดประสงคก์ ารสอน 8.1 อธิบายการคน้ หาข้อมูลแบบเรยี งลาดบั 8.1.1 หาผลลัพธ์การคน้ หาข้อมูลแบบเรียงลาดบั 8.2 อธิบายการค้นหาข้อมลู แบบทวภิ าค 8.2.1 หาผลลพั ธ์การค้นหาข้อมลู แบบทวิภาค 8.3 อธบิ ายการค้นหาข้อมลู แบบไบนารีเซิรท์ ทรี 8.3.1 แกไ้ ขปญั หาและหาผลลัพธ์การค้นหาแบบไบนารีเซิร์ททรี 8.3.2 แก้ไขปญั หาและหาผลลัพธ์การดาเนินการกับไบนารเี ซริ ์ททรี 8.3.3 แก้ไขปัญหาและหาผลลัพธ์การทางานของตน้ ไม้ AVL 8.4 อธบิ ายการค้นหาข้อมูลแบบแฮชชิง่ 8.4.1 คานวณฟงั กช์ ันแฮชชง่ิ 8.4.2 แก้ไขปญั หาและหาผลลัพธ์การแก้ปญั หาการชนของคยี ์ เอกสารประกอบการสอนรายวิชาโครงสร้างขอ้ มูลและอลั กอริทมึ

137 หนว่ ยเรยี นท่ี 8 การคน้ หาขอ้ มูล (Searching) เทคนิคการค้นหาข้อมูลให้เหมาะสมกับงาน เพ่ือให้สามารถค้นหาข้อมูลได้อย่างถูกต้องและ รวดเร็วน้ัน ซึ่งข้ันตอนวิธีการค้นหาข้อมูลมีหลายวิธี โดยแต่ละวิธีจะเหมาะสมกับงานแตกต่างกัน ดงั น้นั ผู้ใช้จะต้องเลือกใชข้ น้ั ตอนวิธีในการคน้ หาขอ้ มลู ให้เหมาะสม การค้นหาข้อมูลพื้นฐานมีหลายวธิ ี เชน่ การค้นหาขอ้ มลู แบบเรียงลาดับ การค้นหาข้อมูลแบบ ทวภิ าค การค้นหาแบบไบนารเี ซริ ์ททรี การค้นหาขอ้ มลู แบบแฮชชงิ่ 8.1 การค้นหาข้อมูลแบบเรียงลา้ ดบั (Sequential Searching) การคน้ หาแบบเรียงลาดับเป็นการค้นหาข้อมูลลักษณะเชิงเส้นที่ไม่มีการจัดเรียงข้อมูล โดยจะ ทาการเปรียบเทียบค่าคีย์ท่ีตอ้ งการค้นหาเทียบค่าข้อมูล ต้ังแต่ข้อมูลตัวแรกจนกระท่ังพบข้อมลู ท่ีมีค่า ตรงกัน หรือเปรียบเทียบไปจนถึงข้อมูลตัวสุดท้าย หากไม่ตรงกับค่าใด ก็หมายความถึงไม่มีข้อมูลนั้น การค้นหาขอ้ มูลแบบลาดบั จงึ ใชส้ าหรบั ค้นหาข้อมลู ทีม่ ีจานวนไม่มากและเป็นวธิ ีท่ีง่ายทีส่ ดุ หลกั การค้นหาข้อมลู แบบเรยี งลาดับมสี ่วนประกอบในการคน้ หาข้อมูล 2 ชนดิ คอื 1. ค่าข้อมูลท่ีต้องการค้นหา (Target given) ค่าข้อมูลน้ีเป็นข้อมูลที่ต้องการ โดยจะถูก จัดเก็บอยู่ในอารเ์ รย์ 2. ต้าแหน่งที่ต้องการ (Location Wanted) ตาแหน่งอ้างอิงที่ใช้ในการจัดเก็บข้อมูล โดย อาร์เรยจ์ ะทาการกาหนดในช่องจดั เกบ็ โดยมีตัวช้ี (Index) เป็นตวั ระบถุ งึ ตาแหน่งในหน่วยความจา ตาแหนง่ ทีต่ ้องการ Location = a[5] ชดุ ข้อมลู [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 14 21 36 18 62 91 28 84 30 77 69 25 ขอ้ มลู ที่ตอ้ งการ Target = 62 ภาพที่ 8.1 ส่วนประกอบสาหรับการคน้ หาแบบซีเควนเชียล เอกสารประกอบการสอนรายวิชาโครงสร้างข้อมลู และอลั กอริทมึ

138 ตัวอย่างท่ี 8.1 กาหนดชุดข้อมูล 38 49 90 27 24 68 30 58 94 83 65 50 ค้นหาข้อมูล (Target) คอื 24 แบบเรยี งลาดับ ชุดข้อมลู [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 38 49 90 27 24 68 30 58 94 83 65 50 ครั้งที่ 1 24 ≠ 38 38 49 90 27 24 68 30 58 94 83 65 50 ครงั้ ท่ี 2 24 ≠ 49 38 49 90 27 24 68 30 58 94 83 65 50 คร้งั ท่ี 3 24 ≠ 90 38 49 90 27 24 68 30 58 94 83 65 50 ครัง้ ที่ 4 24 ≠ 27 38 49 90 27 24 68 30 58 94 83 65 50 คร้งั ท่ี 5 24 = 24 38 49 90 27 24 68 30 58 94 83 65 50 จากตัวอย่างท่ี 8.1 การค้นหาแบบซีเควนเชียลของชดุ ข้อมลู ทัง้ 12 ตวั โดยเปน็ การค้นหาขอ้ มูล (Target) ซ่ึงจะเริ่มต้นค้นหาข้อมูลจากลาดับแรกไปเรื่อยๆ จนกว่าจะเจอข้อมูลท่ีต้องการ (เริ่มจาก 1,2,3,..,n) ครง้ั ท่ี 1 เปรยี บเทียบขอ้ มลู 24 ≠ 38 คร้งั ที่ 2 เปรียบเทียบขอ้ มลู 24 ≠ 49 ครัง้ ที่ 3 เปรยี บเทียบข้อมลู 24 ≠ 90 ครั้งท่ี 4 เปรยี บเทยี บข้อมลู 24 ≠ 27 ครัง้ ท่ี 5 เปรียบเทียบข้อมลู 24 = 24 เอกสารประกอบการสอนรายวชิ าโครงสร้างขอ้ มูลและอลั กอรทิ มึ

139 ตัวอย่างท่ี 8.2 กาหนดชุดข้อมูล 38 49 90 27 24 68 30 58 94 83 65 50 ค้นหาตาแหน่ง (Location) คือ [4] แบบเรียงลาดบั ชดุ ข้อมลู [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 38 49 90 27 24 68 30 58 94 83 65 50 ครั้งท่ี 1 [4] ≠ [1] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 38 49 90 27 24 68 30 58 94 83 65 50 ครงั้ ที่ 2 [4] ≠ [2] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 38 49 90 27 24 68 30 58 94 83 65 50 คร้งั ท่ี 3 [4] ≠ [3] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 38 49 90 27 24 68 30 58 94 83 65 50 คร้ังที่ 4 [4] = [4] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 38 49 90 27 24 68 30 58 94 83 65 50 จากตัวอย่างที่ 8.2 การค้นหาแบบซีเควนเชียลของชุดข้อมูลทั้ง 12 ตัว โดยเป็นการค้นหา ตาแหน่ง (Location) ซ่ึงจะเริ่มต้นค้นหาตาแหน่งจากลาดับแรกไปเรื่อยๆ จนกว่าจะเจอตาแหน่งที่ ตอ้ งการ (เรมิ่ จาก 1,2,3,..,n) ครง้ั ท่ี 1 เปรยี บเทียบขอ้ มูล [4] ≠ [1] ครั้งที่ 2 เปรียบเทียบขอ้ มลู [4] ≠ [2] ครั้งท่ี 3 เปรยี บเทยี บข้อมลู [4] ≠ [3] คร้งั ที่ 4 เปรยี บเทียบข้อมลู [4] = [4] เอกสารประกอบการสอนรายวชิ าโครงสรา้ งขอ้ มลู และอัลกอริทมึ

140 8.2 การคน้ หาขอ้ มลู แบบทวภิ าค (Binary Searching) การค้นหาข้อมลู แบบทวิภาคเป็นวธิ กี ารท่ีเพ่มิ ประสทิ ธิภาพในการค้นหาข้อมลู ดีกว่าการค้นหา ข้อมูลแบบลาดับ ซ่ึงการค้นหาข้อมูลแบบทวิภาคจะดาเนินการกับข้อมูลที่มีการจัดเรียงลาดับแล้ว เท่าน้ัน เพราะจะนาข้อมูลที่ต้องการค้นหาไปเปรียบเทียบกับข้อมูลท่ีอยู่ตาแหน่งค่ากลาง (Mid) หาก คยี ม์ ีค่านอ้ ยกวา่ ก็ไปเปรยี บเทียบกับคา่ กลางของชุดขอ้ มูลดา้ นซา้ ย แต่ถ้ามีคา่ มากกว่าก็ไปเปรียบเทยี บ กับค่ากลางของชุดข้อมูลด้านขวา เปรียบเทียบซ้าแบบเดิมจนกว่าจะพบค่ากลางที่เท่ากับค่าคีย์ แต่ถ้า ไมเ่ ทา่ กันแสดงวา่ ไม่มีข้อมูลท่ีตอ้ งการคน้ หา สตู ร mid = (first + last)/2 ; เมอ่ื mid คอื ตาแหนง่ ค่ากลางของชุดขอ้ มลู first คอื ตาแหน่งคา่ ข้อมูลแรก last คอื ตาแหน่งคา่ ข้อมลู สดุ ท้าย ตัวอย่างท่ี 8.3 กาหนดชุดข้อมูล 38 49 90 27 24 68 30 58 94 83 65 50 ค้นหาข้อมูล (Target) คอื 24 แบบทวภิ าค ชดุ ข้อมลู [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 38 49 90 27 24 68 30 58 94 83 65 50 นาขอ้ มลู ทง้ั หมดมาจัดเรยี งจากนอ้ ยไปหามาก [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 24 27 30 38 49 50 58 65 68 83 90 94 ครง้ั ที่ 1 หาตาแหน่งกลางของข้อมูล mid = (first + last)/2 = (1+12)/2 =6 first mid last [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 24 27 30 38 49 50 58 65 68 83 90 94 เปรียบเทียบ mid=50 กับ Target=24 คือ 24<50 ดังน้ัน Target ท่ีต้องการจึงมีค่า น้อยกว่า จึงเลือกเปรียบเทียบกับชุดข้อมูลด้านซ้าย เพราะด้านขวาจะเป็นชุดข้อมูลที่มี คา่ มากกวา่ 50 จึงไมจ่ าเปน็ ตอ้ งใชใ้ นการเปรยี บเทยี บ เอกสารประกอบการสอนรายวชิ าโครงสรา้ งขอ้ มูลและอัลกอริทึม

141 ครั้งท่ี 2 หาตาแหนง่ กลางของข้อมลู mid = (first + last)/2 = (1+5)/2 =3 first mid Last [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 24 27 30 38 49 เปรียบเทียบ mid=30 กับ Target=24 คือ 24<30 ดังนั้น Target ที่ต้องการจึงมีค่า น้อยกว่า จึงเลือกเปรียบเทียบกับชุดข้อมูลด้านซ้าย เพราะด้านขวาจะเป็นชุดข้อมูลที่มี ค่ามากกว่า 30 จงึ ไม่จาเปน็ ต้องใช้ในการเปรยี บเทยี บ ครั้งท่ี 3 หาตาแหนง่ กลางของข้อมูล mid = (first + last)/2 = (1+2)/1 =1 first +mid last [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 24 27 เปรยี บเทยี บ mid=24 กบั Target=24 คอื 24=24 ดงั นั้นค้นพบ Target ทต่ี อ้ งการ ตวั อยา่ งท่ี 8.4 กาหนดชุดข้อมูล 38 49 90 27 24 68 30 58 94 83 65 50 ค้นหาข้อมูล (Target) คอื 60 แบบทวิภาค ชุดขอ้ มลู [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 38 49 90 27 24 68 30 58 94 83 65 50 นาขอ้ มลู ทั้งหมดมาจัดเรียงจากน้อยไปหามาก [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 24 27 30 38 49 50 58 65 68 83 90 94 คร้ังท่ี 1 หาตาแหน่งกลางของข้อมลู mid = (first + last)/2 = (1+12)/2 =6 เอกสารประกอบการสอนรายวชิ าโครงสร้างขอ้ มลู และอัลกอริทมึ

142 first mid last [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 24 27 30 38 49 50 58 65 68 83 90 94 เปรียบเทียบ mid=50 กับ Target=60 คือ 60>50 ดังนั้น Target ท่ีต้องการจึงมีค่า มากกว่า จงึ เลือกเปรยี บเทียบกับชุดข้อมูลด้านขวา เพราะด้านซ้ายจะเป็นชดุ ข้อมลู ที่มี คา่ น้อยกวา่ 50 จงึ ไม่จาเปน็ ตอ้ งใช้ในการเปรยี บเทยี บ ครง้ั ที่ 2 หาตาแหนง่ กลางของข้อมูล mid = (first + last)/2 ครัง้ ท่ี 3 = (7+12)/2 =9 first mid last [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 58 65 68 83 90 94 เปรียบเทียบ mid=68 กับ Target=60 คือ 60<68 ดังน้ัน Target ที่ต้องการจึงมีค่า น้อยกว่า จึงเลือกเปรยี บเทียบกับชุดข้อมูลดา้ นซ้าย เพราะด้านขวาจะเป็นชุดขอ้ มูลที่มี ค่ามากกว่า 68 จงึ ไมจ่ าเป็นตอ้ งใช้ในการเปรียบเทยี บ หาตาแหน่งกลางของข้อมลู mid = (first + last)/2 = (7+8)/2 =7 first+mid last [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 58 65 เปรียบเทียบ mid=58 กับ Target=60 คือ 60>58 ดังนั้น Target ท่ีต้องการจึงมีค่า มากกวา่ จึงเลือกเปรยี บเทยี บกับชดุ ข้อมูลดา้ นขวา คร้งั ที่ 4 หาตาแหน่งกลางของข้อมูล mid = (first + last)/2 = (8+8)/2 =8 first+mid+last [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] 65 เปรียบเทียบ mid=65 กบั Target=60 คือ 60<65 ดงั น้ัน ไมพ่ บ Target ทต่ี ้องการ เอกสารประกอบการสอนรายวชิ าโครงสร้างข้อมูลและอลั กอริทึม

143 8.3 การค้นหาขอ้ มลู แบบไบนารเี ซิรท์ ทรี (Binary Search Tree) การค้นหาข้อมูลแบบไบนารีเซิร์ททรีเป็นการค้นหาที่ลดความผิดพลาดของการค้นหาข้อมูล ลาดับและแบบทวิภาค คือ การลบหรือการเพ่ิมข้อมูลในตาแหน่งท่ีข้อมูลเดิมถูกเปล่ียนไป และเมื่อ ค้นหาจะทาให้เกิดความผิดพลาด เพราะข้อมูลที่ค้นพบเป็นข้อมูลในตาแหน่งเดิมของข้อมูลที่ถูกลบ หรอื เพ่ิม ดังนั้นนาการคน้ หาขอ้ มูลแบบไบนารีเซิรท์ ทรีมาแก้ปัญหาดังกล่าว ซง่ึ มหี ลกั การทางานดังนี้ 1. ทุกขอ้ มูลในโครงสรา้ งดา้ นซ้ายมคี ่านอ้ ยกวา่ รูทโหนด 2. ทกุ ขอ้ มลู ในโหนดดา้ นขวา มคี า่ มากกวา่ หรือเท่ากบั รูทโหนด 3. โหนดมกี ารจดั เรียงแบบไบนารเี ซริ ์ททรี การรับข้อมูลเข้ากาหนดให้ข้อมูลแรกจะเป็นรูทโหนด ข้อมูลต่อไปที่รับเข้ามาจะทาการ เปรียบเทียบค่ากับรูทโหนด หากมีค่าน้อยกว่าจะจัดเป็นโหนดลูกด้านซ้าย แต่ถ้ามีค่ามากกว่าหรือ เท่ากับจะถกู จดั ใหอ้ ยู่ในโหนดลกู ด้านขวา ซงึ่ แทนค่า K เป็นคียใ์ นการเปรียบเทยี บดังภาพที่ 8.2 K All<K All>=K ภาพท่ี 8.2 โครงสรา้ งแบบไบนารเี ซริ ์ททรี 30 30 25 40 30 (a) (b) 30 30 25 25 40 40 15 15 28 55 (c) (d) (e) ภาพที่ 8.3 โครงสร้างทเ่ี ป็นแบบไบนารเี ซิรท์ ทรี เอกสารประกอบการสอนรายวชิ าโครงสรา้ งขอ้ มลู และอลั กอริทึม

144 จากภาพที่ 8.3 เป็นโครงสร้างแบบไบนารีเซิร์ททรี เน่ืองจากข้อมูลของโหนดย่อยด้านซ้าย น้อยกวา่ คา่ รทู โหนด และโหนดย่อยดา้ นขวามากกวา่ รูทโหนด เชน่ ภาพที่ 8.3(d) 25<30<40 35 20 25 20 23 35 (a) (b) 55 55 35 40 35 40 25 30 25 30 (c) (d) ภาพท่ี 8.4 โครงสรา้ งทไ่ี ม่เป็นแบบไบนารีเซิร์ททรี จากภาพที่ 8.4 ถึงจะมีการจัดโครงสร้างแบบไบนารีแต่จะเห็นว่าค่าข้อมูลน้ันมีการจัด ตาแหน่งทไ่ี ม่ถกู ต้อง เชน่ ภาพท่ี 7.4(c) 35<55>40 ตัวอย่างที่ 8.5 จากข้อมูลต่อไปน้ี 45 37 64 73 53 25 40 จงเรียงข้อมูลโดยใช้โครงสร้างแบบ ไบนารเี ซริ ์ททรี 45 37 64 25 40 53 73 รับขอ้ มลู ตัวท่ี 1 ค่าข้อมูล 45 กาหนดเป็นรทู โหนด รับขอ้ มูลตวั ท่ี 2 คา่ ข้อมูล 37 คา่ 37<45 กาหนดโหนดดา้ นซา้ ยของ 45 เอกสารประกอบการสอนรายวิชาโครงสร้างขอ้ มูลและอลั กอริทึม

145 รับข้อมูลตวั ท่ี 3 คา่ ข้อมลู 64 ค่า 64>45 กาหนดโหนดดา้ นขวาของ 45 รับข้อมูลตัวท่ี 4 ค่าข้อมูล 73 ค่า 73>45 และ 73>64 กาหนดเป็นโหนดด้านขวา ของ 64 รับข้อมูลตัวที่ 5 ค่าข้อมูล 53 ค่า 53>45 และ 53<64 กาหนดเป็นโหนดด้านซ้าย ของ 64 รับข้อมูลตัวท่ี 6 ค่าข้อมูล 25 ค่า 25<45 และ 25<37 กาหนดเป็นโหนดด้านซ้าย ของ 37 รับข้อมูลตัวท่ี 7 ค่าข้อมูล 40 ค่า 40<45 และ 40>37 กาหนดเป็นโหนดด้านขวา ของ 37 8.3.1 การคน้ หาแบบไบนารีเซริ ์ททรี 1. การคน้ หาคา่ ทีน่ อ้ ยทีส่ ุด (Find Smallest Node) การค้นหาค่าที่น้อยท่ีสุดด้วยไบนารีเซิร์ททรี โดยรูปแบบของโครงสร้างจะมีการช้ีค่า จากรูทโหนดไปตามโหนดด้านซ้ายซ่ึงเป็นค่าท่ีน้อยและโหนดสุดท้ายของโครงสร้างที่ไม่มีการช้ีไป ยัง โหนด ซง่ึ ก็คือโหนดท่มี ีคา่ น้อยทสี่ ุด 30 20 10 ภาพท่ี 8.5 การคน้ หาค่าที่นอ้ ยทส่ี ุด จากภาพที่ 8.5 ช้ีไปยังค่ารูทโหนดและช้ีต่อไปยังโหนดต่อไปทางด้านซ้ายจนกระทั่ง ถงึ โหนดทไี่ มม่ ีการชี้คา่ ไปยังโหนดอนื่ อกี ซง่ึ มีคา่ ข้อมูล 10 เป็นคา่ ที่น้อยท่ีสดุ 2. การคน้ หาคา่ ท่ีมากที่สดุ (Find Large Node) การค้นหาค่าท่ีมากที่สุดจะมีรูปแบบเช่นเดียวกันกับการค้นหาค่าท่ีน้อยท่ีสุด แต่จะ เปล่ียนจากค้นหาตามโหนดด้านซ้ายเป็นโหนดดา้ นขวาแทนจนกว่าพบโหนดที่มีการชี้ไปยังโนดอ่ืน ทา ใหไ้ ด้ค่าขอ้ มลู ท่ีมากที่สดุ 30 40 50 ภาพที่ 8.6 การคน้ หาคา่ ขอ้ มูลท่ีมากทีส่ ุด เอกสารประกอบการสอนรายวิชาโครงสร้างขอ้ มูลและอลั กอริทมึ

146 จากภาพท่ี 8.6 กาหนดพอยน์เตอร์ root ช้ีไปยังค่ารูทโหนดและชี้ต่อไปยังโหนด ต่อไปทางด้านขวาจนกระท่ังถึงโหนดท่ีไม่มีการช้ีค่าไปยังโหนดอื่นอีก ซ่ึงมีค่าข้อมูล 50 เป็นค่าท่ีมาก ทีส่ ดุ 3. ค้นหาคา่ ทีต่ อ้ งการ (Request Node) การค้นหาค่าที่ต้องการจะใช้วิธีการค้นหาแบบไบนารี คือ การเทียบค่ากับรูทโหนด หากมีค่านอ้ ยกวา่ ก็ดาเนินการคน้ หาดา้ นซ้าย แต่ถา้ มคี ่ามากกว่าดาเนินการค้นข้อมลู ดา้ นขวา จากภาพที่ 8.7 ต้องการคน้ หาขอ้ มูล 25 จะต้องดาเนนิ การกาหนดพอยน์เตอร์ชไี้ ปยัง รูทโหนดทาให้ทราบว่าจะต้องค้นหาต่อไปในทรีย่อยด้านซ้ายเพราะ 25<30 เมื่อเทียบค่ากับ 20 ซึ่งมี ค่ามากกวา่ จงึ ไปดา้ นขวา และพบขอ้ มลู ทต่ี รงกบั ค่าทีต่ อ้ งการคือ 25 30 20 25 ภาพท่ี 8.7 การคน้ หาข้อมูลที่ตอ้ งการในโครงสร้างไบนารีเซิรท์ ทรี 8.3.2 การดา้ เนนิ การกบั ไบนารีเซริ ท์ ทรี 1. การด้าเนินการแทรกขอ้ มูล คือ การเพ่ิมโหนดเข้ามาในโครงสร้างด้วยวิธีการระบุตาแหน่ง (Address) โดยการ เทยี บค่าจาก รทู โหนด และเพ่ิมโหนดยังตาแหน่งท่ีถูกตอ้ งเชน่ เดียวกบั การจัดเรยี งข้อมูลในครง้ั แรก ตวั อย่างที่ 8.6 เพ่ิมข้อมูล 28 และ 75 ลงในไบนารเี ซิร์ททรีตอ่ ไปน้ี 30 20 40 10 25 35 50 เอกสารประกอบการสอนรายวชิ าโครงสรา้ งขอ้ มลู และอลั กอริทึม

147 แทรกข้อมูล 28 ทาการเปรียบเทียบกับค่าเริ่มต้นหรือรูดโหนด คือ 30 เม่ือ เปรียบเทียบค่าแล้ว 28<30 จึงเดินทางไปด้านซ้าย เปรียบเทียบค่า 28>20 เดินทางไปยังด้านขวา เปรยี บเทียบ 28 > 25 และกาหนดการลิงคด์ า้ นขวาของ 25 ชีไ้ ปยงั โหนด 28 แทรกข้อมูล 60 ทาการเปรียบเทียบกับรูดโหนด คอื 30 เม่ือเปรียบเทียบค่าแล้ว 60 >30 จึงเดินทางไปด้านขวา เปรียบเทียบค่า 60>40 เดินทางไปยงั ดา้ นขวา เปรยี บเทียบ 60<50 และ กาหนดการลิงคด์ า้ นขวาของ 50 ชไ้ี ปยงั โหนด 60 30 20 40 10 25 35 50 28 60 2. การด้าเนินการลบขอ้ มูล การลบข้อมูลหรือการลบโหนดออกจากไบนารีเซิร์ททรีน้ัน จะมีวิธีการท่ีซับซ้อน ยงิ่ ขึน้ เนอ่ื งจากมีการเปลี่ยนตาแหนง่ ของโหนดและตอ้ งมีการปรับปรุงโครงสรา้ งไบนารีเซิรท์ ทรีแบง่ ได้ 4 กรณดี งั นี้ กรณที ี่ 1 : ถา้ โหนดทีต่ อ้ งการลบไม่มีโหนดลูก หากโหนดท่ีตอ้ งการลบไม่มี โหนดลูกสามารถท่ีจะลบโหนดน้ันออกได้เลย โดยการเซตโหนดพ่อแม่ของโหนดที่ต้องการลบมีค่าเป็น nil และทาการคนื ตาแหนง่ ใหก้ ับหนว่ ยความจา เช่น ลบข้อมูล 35 30 30 20 40 20 40 10 25 35 50 10 25 50 ก่อนการลบโหนด หลังการลบโหนด กรณีที่ 2 : ถ้าโหนดทต่ี ้องการลบมีเพียงโหนดลูกด้านขวา สาหรับโหนดที่ ต้องการลบมีเฉพาะโหนดลูกด้านขวาจะทาการลบการลิงก์โหนดย้อยด้านขวาของโหนดพ่อแม่จากนั้น โหนดลูกจะถูกเซตคา่ ให้เป็นโหนดยอ่ ยด้านขวาของโหนดพ่อแมท่ ่ีถูกลบ เช่น ลบขอ้ มลู 50 เอกสารประกอบการสอนรายวิชาโครงสร้างข้อมลู และอัลกอริทมึ

148 30 30 20 40 20 40 10 25 50 10 20 ก่อนการลบโหนด หลงั การลบโหนด กรณีที่ 3 : ถ้าโหนดที่ต้องการลบมีเพียงโหนดลูกด้านซ้าย จะทาการลบ ลิงคโ์ หนดย่อยด้านซ้ายของโหนดพ่อแม่จากนั้นโหนดลูกจะถูกเซตค่าเป็นโหนดย่อยด้านซา้ ยของโหนด พอ่ แม่ เชน่ ลบขอ้ มลู 10 30 30 20 40 20 40 10 35 50 35 50 ก่อนการลบโหนด หลังการลบโหนด กรณีที่ 4 : ถ้าโหนดท่ีต้องการลบมีโหนดลูกท้ังซ้ายและขวา สาหรับการ ลบโหนดที่มีโหนดลูกทั้งด้านซ้ายและด้านขวานั้นถือเป็นการลบโหนดที่อยู่กึ่งกลาง ดังนั้นโครงสร้าง ของไบนารีทรีเซิร์ททรี ก็จะเกิดความไม่สมดุล จึงต้องมีการปรับเปลี่ยนและแทนท่ีตาแหน่งโดยการ นาเอาโหนดในโครงสร้างมาแทนท่ี ซึง่ วิธกี ารที่จะเลอื กนาเอาโหนดใดมาแทนท่นี นั้ สามารถท่ีจะเลอื กได้ อยู่ 2 วธิ ีคือ (1) เลือกค่าของโหนดท่ีมีค่าสูงสุดของโหนดท่ีต้องการลบด้านซ้ายของทรี ย่อย แทนทีย่ งั ตาแหน่งของโนดท่ีตอ้ งการลบ หรือ (2) เลือกค่าโหนดที่มีค่าต่าสุดของโหนดท่ีต้องการลบด้านขวาของทรีย่อย แทนที่ยงั ตาแหน่งของโหนดที่ต้องการลบ เอกสารประกอบการสอนรายวชิ าโครงสร้างข้อมูลและอัลกอรทิ มึ

149 30 25 20 40 20 40 10 25 35 50 10 35 50 ก่อนการลบโหนด หลังการลบโหนด 8.3.3 ต้นไม้ AVL การปรับสมดุลโครงสร้างของทรี สาเหตุที่ต้องมีการปรับโครงสร้างของทรี เน่ืองมาจาก ต้องการให้มีประสิทธภิ าพของการค้นหาท่ีรวดเรว็ ขึ้น โดยพิจารณาภาพที่ 8.8 40 30 35 45 20 40 30 10 25 35 45 25 (b) AVL Trees 20 15 (a) ไบนารีเซริ ทท์ รีท่ีมีความสูงไม่สมดลุ ภาพท่ี 8.8 การจัดเรยี งโครงสรา้ งทรี จากภาพท่ี 8.8(a) เปน็ โครงสร้างที่มกี ารจัดเรียงในรูปแบบทจ่ี ดั เรยี งสมบรู ณ์เกือบทีจ่ ะเปน็ เชิง เส้น แต่ในภาพที่ 8.8(b) เป็นการปรับโครงสร้างให้มาอยู่ในแบบ AVL TREES จะเห็นว่ามีรูปแบบท่ี เหมือนกบั ไบนารีเซิร์ททรี คอื มีโหนดท่เี ป็นคู่กนั เอกสารประกอบการสอนรายวชิ าโครงสรา้ งข้อมูลและอัลกอรทิ ึม

150 ไบนารีทรีท่ีมีการจัดเรียงกันในลักษณะของความสูงท่ีไม่สมดุลกันน้ัน หากต้องการปรับให้มี ระดับทรี มีความสมดุลในแบบของ AVL มีสตู รในการคดิ คา่ ความสมดุล ซ่ึงคา่ ที่ไดจ้ ากการลบกันต้องมี คา่ 1 น่นั กค็ อื 0,-1,+1 คอื HL – HR  1 ; เมอื่ HL คือ ความสูงของโหนดด้านซา้ ย HR คือ ความสูงของโหนดด้านขวา HL = 3 HR = 2 30 20 40 10 25 35 50 HL = 2 5 15 30 HR = 2 (a) HL - HR = 1 HR = 1 HL = 1 30 20 40 20 40 10 25 35 50 (b) HL - HR = 1 (a) HL - HR = -1 ภาพท่ี 8.9 ความสมดุลของ AVL TREES จากภาพท่ี 8.9(a) ได้ค่าความสมดุลของทรีคือ 1 น่ันก็คือ HL=3, HR=2 หาความ สมดุลจากสูตร HL-HR = 3-2 =1 ความสมดุลของภาพที่ 8.9(b) HL-HR = 2-1 =1 และความสมดุล ของภาพท่ี 8.9(c) HL-HR = 1-0 = -1 เอกสารประกอบการสอนรายวชิ าโครงสรา้ งข้อมูลและอัลกอริทึม

151 1. การปรบั ความสมดุลของทรี เมื่อมีการดาเนินการกับทรี เช่น การลบ หรือ การแทรกโหนดเข้าไปในทรีจะทาให้ เกิดความเปลี่ยนแปลงด้านโครงสร้าง ในบางคร้ังอาจทาให้ขาดความสมดุล ดังน้ันจึงจาเป็นต้องปรับ ความสมดุลของทรโี ดยวิธีการของ AVL TREES สามารถระบุถงึ ความไมส่ มดลุ ของทรีได้ 4 กรณคี อื กรณีที่ 1 : ความไม่สมดุลของโครงสร้างจากโหนดซ้ายของโหนดซ้าย (Left of Left) คือ ความไม่สมดุลอันเกิดจากการเปล่ียนแปลงโครงสร้างท่ีโหนดลูกด้านซ้ายของ โหนดย่อยดา้ นซา้ ยดงั ภาพท่ี 8.10 ก่อน เพมิ่ โหนด 5 หลงั เพิม่ โหนด 5 30 30 20 40 20 40 10 25 10 25 5 ภาพท่ี 8.10 กรณีความไม่สมดลุ ของโครงสรา้ งจากโหนดซา้ ยของโหนดซ้าย กรณีท่ี 2 : ความไม่สมดุลของโครงสร้างจากโหนดขวาของโหนดขวา (Right of Right) คือ ความไม่สมดุลอันเกิดจากการเปลี่ยนแปลงโครงสร้างท่ีโหนดลูกด้านขวาของ โหนดยอ่ ยดา้ นขวา ดังภาพท่ี 8.11 กอ่ น เพมิ่ โหนด 60 หลัง เพ่มิ โหนด 60 30 30 20 40 20 40 35 50 35 50 60 ภาพท่ี 8.11 กรณคี วามไมส่ มดลุ ของโครงสรา้ งจากโหนดขวาของโหนดขวา เอกสารประกอบการสอนรายวิชาโครงสร้างขอ้ มลู และอัลกอริทึม

152 กรณีที่ 3 : ความไม่สมดุลของโครงสร้างจากโหนดขวาของโหนดซ้าย (Right of Left) คือ ความไม่สมดุลอันเกิดจากการเปลี่ยนแปลงโครงสร้างท่ีโหนดลูกด้านขวาของ โหนดย่อยด้านซา้ ย ดังภาพที่ 8.12 กอ่ น เพม่ิ โหนด 15 หลงั เพมิ่ โหนด 15 30 30 20 40 20 40 10 25 10 25 15 ภาพที่ 8.12 กรณีความไม่สมดุลของโครงสรา้ งจากโหนดขวาของโหนดซา้ ย กรณีท่ี 4 : ความไม่สมดุลของโครงสร้างจากโหนดซ้ายของโหนดขวา (Left of Right) คือ ความไม่สมดุลอันเกิดจากการเปล่ียนแปลงโครงสร้างที่โหนดลูกด้านซ้ายของ โหนดยอ่ ยด้านขวา ดงั ภาพที่ 8.13 ก่อน เพิม่ โหนด 55 หลงั เพิ่มโหนด 55 30 30 20 40 20 40 35 50 35 50 55 ภาพท่ี 8.13 กรณีความไม่สมดลุ ของโครงสรา้ งจากโหนดซา้ ยของโหนดขวา เอกสารประกอบการสอนรายวิชาโครงสรา้ งขอ้ มลู และอัลกอริทึม

153 2. วิธีการปรบั ความสมดุลของทรี (1) ปรับความสมดุลของ Left of Left สามารถปรับโดยการหมุน โครงสรา้ งของโหนดทข่ี าดความสมดุลใหห้ มนุ ไปยงั ดา้ นขวาโครงสรา้ งดังภาพท่ี 7.14 กอ่ น ปรับหมุนขวา หลัง ปรบั หมนุ ขวา 30 20 20 40 10 30 10 25 5 25 40 ภาพท่ี 8.14 การปรบั ความสมดุลของ Left of Left 5 จากภาพท่ี 8.14 ก่อนปรับหมนุ ขวาโหนด 5 เปน็ โหนดท่ีขาดความสมดุล จึง ทาการปรับหมุนไปด้านขวาโดยปรับหมุนนา 20 ข้ึนมาและปรับ 30 เป็นโหนดขวาของ 25 จึงทาให้ เกิดความสมดลุ ดังภาพหลงั ปรบั หมนุ ขวา (2) ปรับความสมดุลของ Right of Right ทาการปรับโครงสร้างโดยการ หมนุ ซา้ ยดังภาพที่ 8.15 ก่อน ปรับหมุนซ้าย หลัง ปรบั หมนุ ซ้าย 30 40 20 40 30 50 35 50 20 35 60 60 ภาพท่ี 8.15 การปรับสมดุลของ Right of Right เอกสารประกอบการสอนรายวิชาโครงสรา้ งข้อมูลและอัลกอรทิ ึม

154 จากภาพที่ 8.15 ก่อนปรับหมุนซ้าย โครงสร้างโหนด 60 ขาดสมดุล ปรับ โครงสร้างโดยการหมุนโหนด 30 ไปด้านซ้ายทาให้ได้โหนด 40 เป็นรูทโหนด ทาให้ทรีมีความสมดุลดัง ภาพหลงั ปรับหมนุ ซ้าย (3) ปรับความสมดุลของ Right of Left การปรับความสมดุลของ Right of Left จะมีการปรับหมุนแกนของโหนดอยู่ 2 ขั้นตอนคือ การปรับโหนดที่ไม่สมดุลให้มีการจัดแบบ Left of Left แลว้ ปรับหมุนไปในด้านขวา ดงั ภาพท่ี 8.16 กอ่ น ปรับหมุน หลงั ปรับหมนุ ซ้าย ครั้งท่ี 1 30 30 20 40 20 40 10 25 15 25 5 15 10 18 18 5 15 20 หลงั ปรับหมนุ ขวา ครง้ั ท่ี 2 30 10 18 25 40 5 ภาพที่ 8.16 การปรับความสมดลุ ของ Right of Left จากภาพที่ 8.16 ข้ันแรกจะหมุนแกนไปด้านซ้ายก่อน ปรับโครงสร้างโดย การหมุนโหนด 10 ไปด้านซ้าย ทาให้ได้โหนด 15 แทนที่ 10 จากนั้นจึงปรับโหนดหมุนด้านขวา เลือก โหนด 30 ปรับหมุนขวา ทาให้ไดโ้ หนด 20 เปน็ รูทโหนด เอกสารประกอบการสอนรายวิชาโครงสร้างข้อมลู และอัลกอรทิ มึ

155 (4) ปรับความสมดุลของ Left of Right สาหรับวิธีการปรับความสมดุล จะใช้รูปแบบตรงกันข้ามกับ Right of Left คือจะเลือกปรับหมุนก่อนแล้วจึงปรับหมุนซ้ายดังภาพท่ี 8.17 กอ่ น ปรับหมนุ หลัง ปรับหมนุ ขวา ครั้งที่ 1 30 30 20 40 20 35 35 50 33 40 33 38 31 38 50 31 35 หลัง ปรบั หมนุ ซ้าย ครัง้ ที่ 2 30 40 20 33 38 50 31 ภาพท่ี 8.17 การปรบั ความสมดุลของ Left of Right จากภาพที่ 8.17 ขั้นแรกจะหมุนแกนไปด้านขวาก่อน ปรับโครงสร้างโดย การหมุนโหนด 40 ไปด้านขวา ทาให้ได้โหนด 35 แทนที่ 40 จากน้ันจึงปรับโหนดหมุนด้านซ้าย เลือก โหนด 30 ปรบั หมุนขวา ทาใหไ้ ดโ้ หนด 35 เป็นรูทโหนด เอกสารประกอบการสอนรายวชิ าโครงสร้างข้อมลู และอัลกอรทิ มึ

156 8.4 การคน้ หาขอ้ มูลแบบแฮชชิง่ (Hashing Search) การค้นหาข้อมูลแบบแฮชชิ่ง คือ การค้นหาข้อมูลที่ถูกจัดเก็บในตารางแฮช โดยการนาคีย์ ข้อมูล ที่ต้องการค้นหาไปผ่านกระบวนการแฮช (Hash Function) เพ่ือให้ทราบตาแหน่งท่ีใช้ในการ เก็บขอ้ มลู ตารางแฮช (Hash Table) คือ ตารางท่ีใช้ในการเก็บข้อมูล โดยจะนาคีย์ข้อมูลไปผ่าน กระบวนการแฮช เพื่อให้ไดต้ าแหน่งที่จะใชใ้ นการจัดเก็บข้อมูลในตารางแฮช (222) คยี ข์ ้อมูล (Key) คอื คา่ ทีร่ ับเข้ามาจะต้องถูกแปลงคา่ ฟังก์ชัน (Hash Function) ในรปู แบบใด รปู แบบหน่ึง แล้วมีค่าเป็นตาแหน่ง (Address) จัดเก็บบนหน่วยความจาและเม่ือต้องการค้นหาข้อมูล ใชก้ ระบวนการเดยี วกัน เพอ่ื ค้นหาข้อมลู ท่ตี อ้ งการด้วยการแปลงคยี ์ (305) คีย์ [001] 001 1245678 [002] 002 1453283 Address [003] 003 Nara 2536482 6 [004] 004 Hash 3 [005] 005 99 [006] 006 Sita :: :: :: [099] 099 Wara [100] 100 ภาพท่ี 8.18 การจดั เกบ็ ข้อมูลในตารางแฮช จากภาพท่ี 8.18 เม่ือรับค่าคีย์เข้ามาคีย์เหล่านั้นจะถูกแปลงค่าด้วยฟังก์ชันแฮช แล้วได้ แอดเดรสหรอื ตาแหนง่ ของตารางแฮช ซึ่งมกี ารจดั เก็บข้อมลู อยู่ 8.4.1 ฟังก์ชันแฮชช่งิ (Hashing Function) 1. Direct Hashing สาหรับวิธีการนี้เป็นวิธีการแบบพื้นฐานคือการเลือกค่า key ท่ี เป็นคีย์ของรหัสรายการนามาจดั ลงข้อมลู ในตารางตามตาแหน่งโดยตรงดงั ภาพท่ี 8.19 เอกสารประกอบการสอนรายวิชาโครงสร้างขอ้ มลู และอลั กอรทิ ึม

157 คีย์ [001] 001 Nara 1245678 [002] 002 Prim 1453283 Address [003] 003 Sita 2536482 6 [004] 004 Hash 3 [005] 005 Wara 99 [006] 006 :: :: :: [099] 099 [100] 100 ภาพที่ 8.19 วธิ กี ารแปลงคา่ คีย์แบบ Direct Hashing จากภาพที่ 8.19 เม่ือรับค่าคีย์เข้ามาผ่านการแฮชด้วยวิธีการ Direct ก็จะได้ตาแหน่ง (Address) ตามค่าคยี ์ใช้ในการจัดเก็บขอ้ มูล 2. Division Hashing จะทาการแปลงค่าคียโ์ ดยการใชว้ ิธีการหาค่าระหวา่ งค่าคีย์กับจานวน ของการเก็บค่าข้อมูลของตารางแฮชด้วยฟังก์ชันโมดูโล (Modulo) แล้วบวกด้วย 1 ซ่ึงกาหนดเป็น ตาแหนง่ เริ่มตน้ ของการจัดเก็บ Address = K Mod N+1 ; เม่อื K คอื ค่าคีย์ N คือ จานวนตารางแฮช Mod คอื การหารเอาเศษ ตัวอย่างท่ี 8.7 กาหนดตารางแฮชจัดเก็บข้อมูล 308 ตาแหน่ง ต้องการเก็บรหัส 19837483, 27364859, 34583924, 46273947, 58374627 จะถูกจัดเก็บตาแหน่งใด รหัสนกั ศึกษา Division Hashing Address 19837483 = 19837483 Mod 308 + 1 = 128 27364859 = 27364859 Mod 308 + 1 = 292 34583924 = 34583924 Mod 308 + 1 = 145 46273947 = 46273947 Mod 308 + 1 = 28 58374627 = 58374627 Mod 308 + 1 = 4 3. Digit Hashing สาหรับวิธีการ Digit Hashing เป็นการเลือกค่าตาแหน่งจากค่าคีย์ เช่น หากต้องการจัดเก็บรหัสนักศึกษา โดยกาหนดรหัสนักศึกษา 8 ตาแหน่ง แต่ต้องการจัดเก็บเพียง 3 เอกสารประกอบการสอนรายวิชาโครงสร้างขอ้ มลู และอลั กอริทมึ

158 ตาแหน่งลงในตารางแฮชก็จะเลือกเอาเฉพาะตาแหน่งท่ีต้องการเป็นตาแหน่งแอดเดรส เช่น ตาแหน่ง 1,2,3 ตัวอย่างท่ี 8.8 ตาแหน่งแอดเดรสบนตารางแฮชจานวน 3 ตาแหน่ง ของรหัสนักศึกษาในตาแหน่งท่ี 1,3,7 ของคา่ คยี ์ คา่ คยี ์ ตา้ แหน่งแอดเดรส 19837483 188 27364859 235 34583924 352 46273947 424 58374627 532 4. Midsquare Hashing เป็นการหาตาแหน่งแอดเดรสท่ีใช้วิธีการนาเอาค่าคีย์มายกกาลัง สอง จากน้ันเลือกเอาค่ากลางของข้อมูลที่ได้มากาหนดตาแหน่งแอดเดรสบนตารางแฮช การเก็บ ตาแหน่งแอดเดรสนี้ก็แล้วแต่ว่าจะกาหนดการเก็บกี่ตาแหน่ง แต่ต้องไม่เกิน 9 ตาแหน่ง เพราะเป็น จานวนที่คอมพิวเตอร์สามารถที่จะจัดเก็บในแอดเดรสได้สูงสุดแต่บางกรณีก็สามารถท่ีจะประยุกต์เอา Digit Hashing เขา้ มาร่วมดว้ ย คือ การเลือกตาแหนง่ คีย์มายกกาลังแลว้ เลอื กคา่ กลาง ตวั อยา่ งท่ี 8.9 รบั ค่าคีย์ 8 ตาแหน่ง เลือกคา่ ตาแหน่ง 2,4,6,8 หาแอดเดรสดว้ ยวธิ ีการ Midsquare คา่ คีย์ Midsquare ผลลัพธ์ Digit 2,4,6,8 19837483 9343 x 9343 87291649 9164 27364859 7689 x 7689 59120721 2072 34583924 4894 x 4894 23951236 5123 46273947 6797 x 6797 46199209 9920 58374627 8767 x 8767 76860289 6028 5. Folding Hashing สาหรับวิธีการ Folding Hashing จะใช้การกาหนดค่าคีย์ท่ีรับมาแบ่ง จานวนของตัวเลขตามจานวนแอดเดรสแล้วรวมค่าคานวณได้ตัวเลขตามท่ีต้องการ โดยวิธีการหา แอดเดรสของคยี ์อยู่ 2 วธิ ีดงั นี้ (1) Fold Shift ใช้การแบ่งจานวนคีย์รวมจานวนเม่ือได้ค่าตาแหน่งแอดเดรสท่ีเกิน ให้ตัดออก เช่น รับค่าคีย์ 123456789 ต้องการแอดเดรสจานวน 3 ตาแหน่ง คือ 000-999 ได้ค่า แอดเดรสดว้ ยการแบง่ ตวั เลขคยี ์เปน็ 123 456 เอกสารประกอบการสอนรายวชิ าโครงสรา้ งข้อมลู และอัลกอรทิ ึม

159 789 รวมคา่ 1 3 6 8 ทาการตดั คา่ ตัวเลขท่ีเกนิ แอดเดรสออกคือ 1 แอดเดรสที่ตอ้ งการของคียน์ ้คี ือ 3 6 8 (2) Fold boundary ใชร้ ูปแบบหาค่าแอดเดรส เช่นเดียวกับ Fold Shift แตจ่ ะทา การแบง่ คยี ์ดว้ ยการกลับตาแหน่ง เชน่ ค่าคีย์ 123456789 หาแอดเดรส 3 2 1 (กลับค่า 1 2 3) 4 5 6 (ตาแหน่งกลางคงเดมิ ) 9 8 7 (กลบั คา่ 7 8 9) รวมคา่ 1 7 6 4 ตดั ตาแหน่งที่เกินของแอดเดรสออกคือ 1 แอดเดรสทตี่ ้องการของคียน์ ี้คือ 764 6. Rotation Hashing สาหรับการ Rotation Hashing จะทาการแปลงค่าคีย์ด้วยการหมุน ตาแหน่งของตัวเลข ซ่ึงอาจจะนาเอาตัวเลขตาแหน่งท้ายหมุนมาด้านหน้าหรือด้านหน้าหมุนมา ด้านหลัง ตวั อยา่ งที่ 8.10 หาแอดเดรสใหม่ดว้ ยวธิ กี าร Rotation Hashing ค่าคีย์ หมุนคยี ์ คยี ใ์ หม่ 19837483 19837483 31983748 27364859 27364859 92736485 34583924 34583924 43458392 46273947 46273947 74627394 58374627 58374627 75837462 8.4.2 การแก้ปัญหาการชนของคยี ์ (Collision) การแปลงค่าคีย์ด้วยวิธีการต่างๆ ท่ีกล่าวมาในบางกรณีอาจเจอปัญหาเก่ียวกับการชนของคีย์ คือ ได้ค่าแอดเดรสเดียวกัน ซึ่งไม่สามารถที่จะให้มีการบรรลุลงยังแอดเดรสเดียวกันได้ จึงแบ่งวิธีการ แก้ปัญหาการชนของคยี ์ ออกเปน็ 3 วธิ ีคอื 1. การแก้ปญั หาการชนกนั ของคีย์ด้วยการปรับต้าแหน่ง การแก้ปัญหาการชนกันของคีย์ด้วยวิธีการนี้ คือ การแก้ปัญหาเก่ียวกับตาแหน่ง แอดเดรสที่มกี ารชนกันโดยแบง่ ออกเปน็ 4 วธิ ีคือ (1) Linear Probe จะใช้วิธีการเลื่อนตาแหน่งของคีย์ที่มีการชนกันย้ายลง ไปยงั แอดเดรสทยี่ งั ว่างอยดู่ งั ภาพท่ี 7.20 เอกสารประกอบการสอนรายวชิ าโครงสรา้ งขอ้ มลู และอัลกอรทิ ึม

160 คีย์ [001] 001 Nara 143534 [002] 002 Prim 243563 Address [003] 003 Yura 5 [004] 004 Sita Hash 5 [005] 005 Meena [006] 006 : 007 Wara :: :: [099] 099 [100] 100 ภาพที่ 8.20 การแก้การชนกันของคยี ด์ ้วย Linear Probe จากภาพท่ี 8.20 เมื่อมีการแปลงค่าคีย์ 143534 จะได้แอดเดรสที่ 005 ซ่ึง สามารถลงข้อมูลได้โดยไมม่ ีการชนกนั ของคีย์ เพราะยังไม่มีขอ้ มูลแตเ่ ม่ือมีคีย์ 243563 รบั เข้ามาแปลง คา่ คีย์ไดแ้ อดเดรส 005 เช่นกันแต่ในแอดเดรสนี้มีข้อมลู อยู่แล้ว จงึ ตอ้ งเล่ือนมาตรวจสอบหาแอดเดรส ทวี่ า่ งครง้ั ที่ 1 มีคา่ ข้อมลู ครงั้ ที่ 2 จงึ ได้แอดเดรส 007 เพ่อื ใช้ในการเกบ็ ข้อมลู ข้อเสียของวิธีน้ีคือ การจัดวางข้อมูลลงยังแอดเดรสน้ัน ไม่สามารถที่จะ กาหนดตาแหน่งที่แน่นอนได้ เพราะต้องอาศัยการตรวจสอบแอดเดรสท่ีใกล้ตาแหน่งเดิมก่อน แล้วจึง เลื่อนไปยังตาแหนง่ ตอ่ ไปจนกวา่ จะพบแอดเดรสว่างสาหรบั จัดการข้อมลู ทาให้การค้นหาข้อมลู จะต้อง ตรวจสอบและเทยี บค่ากับตาแหน่งหลายคร้งั จนกวา่ จะพบ (2) Quadratic Probe วธิ ีการนที้ าการคานวณตาแหนง่ ใหมใ่ หก้ ับการชน กนั ของคยี ์จากสตู ร New Address = (K ± j2) mod N ; เมื่อ K คอื ตาแหน่งแอดเดรสที่เกิดการชนกนั ของคีย์ j คือ ลาดับเลขของการชนกนั โดยเรมิ่ นับตั้งแต่ 1 N คือ จานวนตารางแฮชที่ใช้ในการเก็บข้อมลู โดยวิธีการน้ีจะใช้การตรวจสอบจานวนของการชนกันของคยี ์กอ่ นแลว้ นามา ยกกาลังสองจากนั้นบวกลบกับตาแหน่งแอดเดรสท่ีมีการชนกัน หารด้วยจานวนของตารางแสดงใน ตารางท่ี 8.1 เอกสารประกอบการสอนรายวิชาโครงสร้างข้อมลู และอัลกอรทิ มึ

161 ตารางที่ 8.1 การแก้การชนกันของคีย์ด้วย Quadratic Probe (N= 150) ล้าดับการชนกัน ตา้ แหน่งแอดเดรสที่ชนกัน (K) J2 ต้าแหน่งแอดเดรสใหม่ 1 1 1 02 2 2 4 06 3 6 9 15 4 15 16 31 5 31 25 56 6 56 36 92 7 92 49 141 8 141 64 55 (3) Pseudo random สาหรับวิธีการน้ีอาจเรียกได้ว่าเป็นการแก้ปัญหา การชนกันของคีย์ด้วยการทาแฮชชิ่ง 2 ครั้ง (Double hashing) โดยเมื่อคานวณหาตาแหน่งในคร้ัง แรกแล้วเกิดการชนกันกจ็ ะคานวณหาตาแหน่งใหมจ่ ากสตู ร New Address = (ax+c) Mod N + 1 ; เมอื่ a คอื ตาแหนง่ แอดเดรสทม่ี กี ารชนกนั x คอื จานวนครงั้ ของการทาซ้า c คอื ค่าคงท่ีทีก่ าหนดข้นึ N คือ จานวนตารางแฮช ตวั อยา่ งที่ 8.11 จงแก้การชนกันของแอดเดรสในตาแหน่งท่ี 2 และเป็นครั้งที่ 3 ของการทาซ้ากัน ของตาแหน่ง กาหนดค่า C=1 จานวนตารางแฮช 355 ชอ่ ง New Address = (ax + c) mod N+1 = (2(3)+1) mod 355+1 = 14 จะไดต้ าแหน่งใหม่ของการจดั เรยี งคือ 014 (4) Key Offset สาหรับการแก้ปัญหาการชนกันของคีย์ด้วยวิธีการน้ี จะ นาค่าคีย์ท่ีมีการชนกันในแอดเดรสมาทาการ offset ก่อน คือ แปลงค่าด้วยการหารด้วยจานวนช่อง ตารางแฮช จากนัน้ จึงนาคีย์ทไ่ี ด้ไปหาแอดเดรส ซึ่งถา้ มกี ารชนกันอกี ก็จะวนรอบการทางานอกี Offset = key / N Address = ((Offset + Old Address) mod N ) + 1 เอกสารประกอบการสอนรายวชิ าโครงสรา้ งขอ้ มูลและอัลกอรทิ ึม

162 ตวั อย่างที่ 8.12 จากภาพที่ ค่าคีย์ 192410 มีการชนกันของคีย์ในแอดเดรส 007 จงหาค่าของ แอดเดรสด้วยวิธีการ key offset ในคร้ังท่ี 1 และคร้ังท่ี 2 เม่ือตารางแฮชเก็บข้อมูล ได้ 355 ชอ่ ง หาแอดเดรสคร้ังที่ 1 Offset = key/N = 192410 / 355 = 542 Address = ((542+007) mod 355) + 1 = 195 หาแอดเดรสครั้งท่ี 2 Offset = key/N = 192410 / 355 = 542 Address = ((542+195) mod 355) + 1 = 25 2. การแกป้ ญั หาการชนกันของคยี ์ด้วยลิงค์ลิสต์ สาหรับวิธีการแก้ปัญหารูปแบบน้ีจะนาเอาโครงสร้างแบบลิงค์ลิสต์มาใช้ในการเช่ือมโยง รายการ โดยเมื่อตารางของแฮชจดั เก็บข้อมลู ที่มีการชนกันของคยี ์ จะทาการเพ่มิ เรคอร์ดในการจัดเก็บ คีย์ โดยใช้วิธีการกาหนดพอยน์เตอร์ในการลิงค์ไปยังข้อมูลต่อไป ซ่ึงถือว่าเป็นแอดเดรสเดียวกัน ดัง ภาพที่ 8.21 [001] 345426 Nida 384959 Meena [002] 281733 Veena 938495 Sita [003] 543729 Prasit [004] [005] 625367 Somsit [006] [007] : [008] : : : [354] [355] ภาพที่ 8.21 การแกก้ ารชนกันของคียด์ ้วยลิงค์ลสิ ต์ เอกสารประกอบการสอนรายวชิ าโครงสรา้ งข้อมูลและอัลกอริทึม

163 จากภาพที่ 8.21 ในแอดเดรส 003 จัดเก็บข้อมูล Prasit ไวเ้ ม่ือคีย์ต่อไปคือ 384959 จะได้ค่า แอดเดรส 003 เช่นกนั ถ้าจะจัดเก็บในเรคอร์ดและใชก้ ารเชื่อมโยงด้วยพอยนเ์ ตอร์ หากมีคยี ต์ อ่ ไปกจ็ ะ ชี้พอยน์เตอร์ต่อไปนกั ซึง่ วธิ กี ารจัดเกบ็ ข้อมลู นั้นจะใชว้ ิธีการแบบ LIFO (Last In First Out) 3. การแก้ปัญหาการชนกนั ของคียด์ ้วยบักเก็ต ในวิธีน้ีของลิงค์ลิสต์น้ันปัญหาที่อาจจะเกิดข้ึนได้ก็คือ หากมีการกาหนดลิสต์ท่ีแน่นอนไว้การ จัดเก็บข้อมูลท่ีมากเกินพื้นที่ก็ไม่สามารถทาได้ทาให้เกิดกรณีที่เรียกว่า Overflow คือข้อมูลมากกว่า พื้นที่จัดเก็บ จึงมีอีกรูปแบบของการแก้ปัญหาการชนกันของคีย์ คือ การสร้างบักเก็ตหรือถังของ แอดเดรสในตาแหน่งต่างๆ ไว้ซ้อนกัน ทาให้สามารถจัดเก็บค่าคีย์ที่ซ้ากนั ได และเม่ือแต่ละบักเก็ตเต็ม แตข่ ้อมูลยังเหลอื กจ็ ะย้ายลงไปยังบักเกต็ ต่อไปท่ยี ังวา่ งอยู่ ดังภาพท่ี 8.22 [001] Bucket 1 192839 Dada 203984 Pitta [002] Bucket 2 281937 Rattiya [003] Bucket 3 384756 Komkit 863723 Nara 192837 Pasit 209487 Malin [004] Bucket 4 ภาพที่ 8.22 การแกก้ ารชนกันของคยี ์ดว้ ย Bucket Hashing ดงั ภาพท่ี 8.22 ในแต่ละบักเกต็ ของคีย์จะถูกแบง่ ออกเป็น 4 ชอ่ ง และทาการเก็บคา่ คียใ์ นชอ่ ง แรก แต่ในกรณีการซ้ากันของคีย์มากกว่าจานวนช่อง เช่น แอดเดรส 002 ค่าคีย์ 209487 จะต้องถูก จัดเกบ็ อยู่ในแอดเดรส 002 แตจ่ านวนชอ่ งเต็มจึงย้ายลงมาเกบ็ ในบักเก็ตท่ี 3 แทน เอกสารประกอบการสอนรายวชิ าโครงสร้างขอ้ มลู และอลั กอรทิ มึ

164 บรรณานกุ รม กชกร ณ นครพนม และคณะ. (2556). เอกสารประกอบการสอนชดุ วชิ า โครงสรา้ งขอ้ มลู และขั้นตอน วิธี หน่วยที่ 9-15 . นนทบุรี : มหาวทิ ยาลัยสโุ ขทัยธรรมธริ าช. กชกร ณ นครพนม และคณะ. (2557). เอกสารประกอบการสอนชดุ วชิ า โครงสร้างขอ้ มูลและขน้ั ตอน วิธี หน่วยที่ 1-8 . นนทบรุ ี : มหาวิทยาลยั สุโขทยั ธรรมธิราช. ครง้ั ท่ี 2. ขนษิ ฐา นามี. (2548). โครงสรา้ งขอ้ มูลและอัลกอริทึม. นนทบุรี : ไอดีซี อนิ โฟ ดาทรบิ ิวเตอร์ เซ็นเตอร์. ณฐั พงษ์ วารีประเสริฐ และสุธี พงศาสกลุ ชยั . (2552). โครงสร้างขอ้ มูลและอัลกอริทึม. กรุงเทพมหานคร : เคทีพี คอมพ์ แอนด์ คอนซัลท.์ นิสาชล โตอดิเทพย.์ (2541). โครงสร้างข้อมลู . กรงุ เทพมหานคร : โอ เอส พริน้ ติง้ เฮาส.์ พิมพค์ ร้ังท่ี 2. บญุ สบื โพธศ์ิ รี, ร่งุ อรณุ ประจักจิตร์ และ สมเจตต์ ภิญญาคง. (2551). โครงสร้างข้อมูลและ อลั กอริทมึ . นนทบุรี : เจรญิ รุ่งเรอื งการพิมพ์. วไิ ลพร กุลตงั วฒั นา (2554). โครงสรา้ งข้อมูลและขน้ั ตอนวธิ .ี อุดรธานี : มหาวทิ ยาลัยราชภฎั อดุ รธาน.ี ววิ ฒั น์ อภสิ ทิ ธภ์ิ ิญโญ และอมร มุสิกสาร. (2550). โครงสรา้ งข้อมูล (Data Structure). กรุงเทพมหานคร : ไอเดียซอฟแวร์เทคโนโลย.ี วษิ ณุ ช้างเนียม. (2556). คูม่ ือเรยี นโครงสร้างข้อมลู และอัลกอริทึม. นนทบุรี : ไอดซี ี อินโฟ ดาทรบิ ิวเตอร์ เซน็ เตอร์. วฒุ ิพงษ์ เข่ือนดนิ . (2553). โครงสรา้ งข้อมูลและอลั กอริทึม. กรงุ เทพมหานคร : ทรปิ เพล้ิ เอด็ ดเู คชน่ั . สานนท์ เจริญฉาย. (). โครงสร้างข้อมลู และอลั กอรทิ ึม กรณตี ัวอยา่ งภาษาซี พร้อม LAB ปฏบิ ัติการ. นนทบรุ ี : เชน พร้นิ ต้ิง. โอภาส เอย่ี มสิรวิ งศ.์ (2549). โครงสรา้ งขอ้ มลู เพอื่ การออกแบบโปรแกรมคอมพิวเตอร.์ กรุงเทพมหานคร : ซีเอ็ดยเู คชั่น. โอภาส เอยี่ มสิริวงศ.์ (2557). อลั กอริทึมและการเขียนโปรแกรมภาษา C. กรุงเทพมหานคร : ซเี อ็ดยเู คชน่ั . เอกสารประกอบการสอนรายวิชาโครงสรา้ งข้อมลู และอัลกอรทิ มึ