�ݺ�ߣ

โครงสร้างข้อมูลทรี Tree

การปฏิบัติการྺองทรี การปฏิบัติการྺองทรีจะคล้ายกับโครงสร้างที่กล่าวมาข้างต้นซึ่งการปฏิบัติการเหล่านั้นได้แก่ การเพิ่มโหนด การลบโหนด การค้นหาโหนด นอกจากนี้ทรียังมีการปฏิบัติการที่พิเศษกว่าโครงสร้างข้อมูลแบบอื่นเช่นเดียวกัน คือ การท่องไปในทรี ซึ่งได้กล่าวในรายละเอียดในหัวข้อก่อนหน้าแล้ว โดยการท่องจะเป็นการนำข้อมูลของโหนดมาจัดวางในแนวเส้นตรง

การปฏิบัติการྺองทรี รายละเอียดของการปฏิบัติการที่จะกล่าวถึงในหัวข้อต่อไปนี้ จะกล่าวถึงเพียงรายละเอียดเกี่ยวกับการปฏิบัติการของไบนารีทรีเสิร์ซทรี เนื่องจากเป็นทรีที่นำไปประยุกต์ใช้งานกันมาก และในการอธิบายขั้นตอนวิธีการปฏิบัติการจะใช้การแทนที่ข้อมูลแบบพลวัตโดยใช้พอยน์เตอร์และโครงสร้างข้อมูลที่เลือกใช้คือลิงค์ลิสต์แบบโยงคู่ โดยมีรายละเอียดของโหนดข้อมูลดังนี้

การปฏิบัติการྺองทรี node : llink : POINTER data : NTEGER rlink : POINTER END ตัวแปรที่สำคัญที่จะใช้ในขั้นตอนวิธีการปฏิบัติการต่าง ๆ ได้แก่ ตัวแปร root เป็นตัวแปรชี้ไปยังตำแหน่งโหนดราก ตัวแปร x เป็นตัวแปรที่ใช้เก็บข้อมูลที่จะเพิ่มโหนดใหม่ ตัวแปร newnode เป็นตัวแปรสำหรับสร้างโหนดใหม่ ทั้งนี้ขั้นตอนวิธีสำหรับการปฏิบัติการไบนารีเซิร์สทรีในเอกสารนี้ จะเขียนเป็นแบบเรียกตนเอง (Recursive) เนื่องจากเขียนได้สั้น กระทัดรัดและไม่ซับซ้อน

การปฏิบัติการྺองทรี 1. การเพิ่มโหนดข้อมูล การเพิ่มโหนดข้อมูลใหม่เข้าไปในไบนารีเซิร์สทรี จะเป็นไปตามหลักการของไบนารีเซิร์สทรี กล่าวคือ ถ้าข้อมูลที่ต้องการเพิ่ม มีค่าน้อยกว่าข้อมูลในโหนดรากหรือโหนดแม่ ก็จะเพิ่มโหนดใหม่ทางด้านทรีย่อยด้านซ้าย แต่ถ้ามีค่ามากกว่าก็จะนำโหนดใหม่เพิ่มทางด้านทรีย่อยด้านขวา โดยโหนดใหม่เมื่อเพิ่มเข้าไปในไบนารี เซิร์สทรี แล้วจะเป็นโหนดใบหรือโหนดลูกเท่านั้น

การปฏิบัติการྺองทรี Proc : AddBST (root : POINTER, x : INTEGER) BEGIN newnode = NEW (node) newnode  llink = NIL newnode  rlink = NIL newnode  data = x IF root = NIL THEN root = newnode ELSE IF x < root  data THEN AddBST (root  llink ,x) ELSE AddBST (root rlink , x) ENDIF ENDIF ENDPROC

การปฏิบัติการྺองทรี 2. การลบโหนดข้อมูล เนื่องจากคุณสมบัติของไบนารีเซิร์สทรีที่ข้อมูลของโหนดลูกด้านซ้ายจะต้องน้อยกว่าข้อมูลของโหนดรากหรือโหนดแม่ และข้อมูลของโหนดลูกด้านขวาจะต้องมากกว่าข้อมูลของโหนดรากหรือโหนดแม่ ดังนั้นในการลบโหนดข้อมูลใดออก จะต้องคำนึงถึงคุณสมบัติดังกล่าวด้วยสภาพการณ์ในการลบโหนดออกจากไบนารีเซิร์สทรีสามารถจัดแบ่งเป็น 3 กรณีดังนี้

การปฏิบัติการྺองทรี 2.1 กรณีลบโหนดใบ เป็นกรณีที่ง่ายที่สุด เนื่องจากสามารถลบโหนดออกได้เลย และไม่มีผลกระทบต่อโครงสร้างของไบนารีเซิร์สทรี ดังแสดงในรูป

การปฏิบัติการྺองทรี 2.2 กรณีลบโหนดที่เป็นโหนดแม่ สามารถจัดแบ่งได้เป็น 2 กรณีดังนี้ 2.2.1 โหนดแม่ที่มีโหนดลูกเพียงด้านใดด้านหนึ่งเท่านั้น ในกรณีนี้เมื่อลบโหนดแม่ออกไปแล้วสามารถที่จะนำโหนดลูกนั้นขยับขึ้นไปเป็นโหนดลูกของโหนดแม่ที่อยู่เหนือโหนดที่ถูกลบได้เลย ดังแสดงในรูป

การปฏิบัติการྺองทรี

การปฏิบัติการྺองทรี 2.2.2 โหนดแม่ที่มีโหนดลูกทั้งสองด้าน ลักษณะแบบนี้เมื่อลบโหนดแล้วจะต้องเลือกโหนดลูกด้านใดด้านหนึ่งมาแทนโหนดที่ลบนั้น ถ้าเลือกโหนดลูกด้านซ้ายของทรีย่อยจะต้องเลือกโหนดที่มีค่ามากที่สุดของทรีย่อยด้านซ้ายนั้นมาแทนแต่ถ้าเลือกโหนดลูกของทรีย่อยด้านขวาจะต้องเลือกโหนดที่มีค่าน้อยที่สุดของทรีย่อยด้านขวานั้นมาแทน ดังแสดงในรูป

การปฏิบัติการྺองทรี ในการเขียนขั้นตอนวิธีเพื่อลบโหนดออกจากไบนารีเซิร์สทรีจะต้องเขียนให้สามารถจัดการได้ครบทั้ง 2 กรณีที่กล่าวมาแล้วโดยเฉพาะในกรณีที่ 2 เป็นกรณีที่มีรายละเอียดที่ต้องจัดการโหนดเพื่อคงสภาพโครงสร้างของไบนารีเซิร์สทรีไว้ดังเดิม ดังนั้นในการเขียนขั้นตอนวิธีจะต้องเลือกว่าเมื่อลบโหนดที่ต้องการแล้ว จะนำโหนดลูกในทรีย่อยด้านใดมาแทน ซึ่งขั้นตอนวิธีในเอกสารนี้ได้เลือกโหนดลูกในทรีย่อยด้านขวามาแทน ดังนั้นจึงมีขั้นตอนวิธีเพิ่มขึ้นมาอีก 1 ขั้นตอน ได้แก่ ขั้นตอนวิธีเพื่อค้นหาโหนดในทรีย่อยด้านขวาที่มีค่าน้อยที่สุด เพื่อเลือกขึ้นไปแทนโหนดที่ถูกลบ ซึ่งวิธีนี้จะถูกเรียกใช้โดยขั้นตอนวิธีการลบ

การประยุกต์ใช้ทรี 1. การค้นหาข้อมูล ทรีที่มีคุณสมบัติทำให้การค้นหาข้อมูลได้รวดเร็วคือไบนารีเซิร์สทรี ซึ่งมีคุณสมบัติคือ สำหรับโหนดรากหรือโหนดแม่ใด ค่าข้อมูลของโหนดลูกด้านซ้ายจะมีค่าน้อยกว่าและค่าข้อมูลของโหนดลูกด้านขวาจะมีค่ามากกว่าเสมอ ดังนั้นในการค้นหาข้อมูลในโหนดใด ของไบนารีเซิร์สทรีจะพบว่าจะเป็นการค้นหาโดยที่ไม่ต้องเข้าถึงทุกโหนด การเปรียบเทียบ 1 ครั้งจะทำให้ลดข้อมูลที่เป็นไปไม่ได้ลงครึ่งหนึ่งของข้อมูลทั้งหมด ดังตัวอย่างที่แสดงในรูป ซึ่งมีข้อมูลอยู่ 10 ชุดในโครงสร้างแบบไบนารีเซิร์สทรี จะเห็นว่า 100 เป็นข้อมูลของโหนดราก ถ้าต้องการค้นหาข้อมูล 110 จะต้องเริ่มต้นเปรียบเทียบที่โหนดรากก่อน และค่า 110 มีค่ามากกว่าค่าข้อมูลของโหนดราก ดังนั้นข้อมูลของโหนดในทรีย่อยด้านซ้ายของโหนดราก จะถูกตัดออกไปและไม่นำมาพิจารณาอีก ข้อมูลที่สนใจต่อไป จะเป็นข้อมูลในทรีย่อยด้านขวาของโหนดรากเท่านั้น

การประยุกต์ใช้ทรี ทำนองเดียวกันนำค่า 110 ไปเปรียบเทียบกับโหนดต่อไป คือโหนดที่มีข้อมูล 120 ปรากฏว่าค่า 110 มีค่าน้อยกว่าก็จะทำให้ต้องพิจารณาข้อมูลของโหนดในทรีย่อยด้านซ้ายแทนและตัดข้อมูลของโหนดในทรีย่อยด้านขวาออกไป จะทำการเปรียบเทียบแบบนี้จนกระทั่งพบข้อมูลตามที่ต้องการ

2. การแปลงค่านิพจน์อินฟิกส์ โพสต์ฟิกส์ และพรีฟิกส์ โครงสร้างของทรีแบบนิพจน์ทรี สามารถใช้การท่องแบบพรีออร์เดอร์ โพสต์ออร์เดอร์ และอินออร์เดอร์ ทำให้ได้ข้อมูลในรูปแบบอินฟิกส์ โพสต์ฟิกส์ หรือพรีฟิกส์ได้ โดยการท่องแบบพรีออร์เดอร์ จะทำให้ได้ข้อมูลแบบโพสฟิกส์ และการท่องแบบอินออร์เดอร์ ก็จะทำให้ข้อมูลแบบอินฟิกส์ ดังแสดงในรูป การประยุกต์ใช้ทรี

3. การเรียงลำดับ การเรียงลำดับโดยใช้การท่อง ไบนารีเซิร์สทรีนอกจากจะประยุกต์ใช้ในด้านการค้นหาข้อมูลแล้ว ยังสามารถนำไปประยุกต์ในการจัดเรียงข้อมูลได้อีกด้วย กล่าวคือ จะใช้รูปแบบการท่องทำให้ได้ข้อมูลจากน้อยไปหามากหรือจากมากไปหาน้อย โดยการท่องแบบอินออร์เดอร์จะทำให้ได้ข้อมูลจากน้อยไปหามาก และการท่องแบบรีเวอร์สอินออร์เดอร์จะทำให้ได้ข้อมูลจากมากไปหาน้อย จากการท่องทั้ง 2 แบบ ถ้านำไปท่องกับไบนารีเซิร์สทรีตามรูป จะทำให้ได้ผลลัพธ์การท่องดังนี้ ผลการท่องแบบอินออร์เดอร์ : 80 90 93 95 98 100 110 115 118 120 125 130 140 ผลการท่องแบบรีเวอร์สอินออร์เดอร์ : 140 130 125 120 118 115 110 100 98 95 93 90 80 การประยุกต์ใช้ทรี

www.themegallery.com Thank You !

�ݺ�ߣ

Tree02

More Related Content

Tree02