Google         youtube            psv            สพม.11

การวิ่งตามเส้นทางในทรี

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

การวิ่งแบบพรี-ออเดอร์ (Pre-order)

            มีลักษณะการวิ่งในแนวลึกก่อน (Depth-first Order) มีอัลกิริทึมการทำงานในตารางที่  9.1

ตารางที่ 9.1 อัลกอริทึมการวิ่งแบบพรี-ออเดอร์

ตัวอย่างการวิ่งแบบพรี-ออเดอร์ดังในรูปที่ 9.13 (a)และการวิ่งผ่านโหนดตามลำดับได้เป็น A,B,D,E,C,F

การวิ่งแบบอิน-ออเดอร์ (In-Order)

            มีการวิ่งลักษณะแบบสมดุล (Symmetric Order) มีอัลกิริทึมการทำงานดังในตารางที่ 9.2

ตารางที่ 9.2 อัลกิริทึมการวิ่งแบบอิน-ออเดอร์

ตังอย่างการวิ่งแบบอิน-ออเดอร์ในรูปที่ 9.13 (b) และการวิ่งผ่านโหนดตามลำดับ ได้เป็น D,B,E,A,C,F

การวิ่งแบบโพสต์-ออเดอร์(Post-Oder)

                มีอัลกิริทึมการทำงาน

 อัลกิริทึมการวิ่งแบบโพสต์-ออเดอร์

ตัวอย่างการวิ่งแบบโพสต์-ออเดอร์ในรูปที่ 9.13 (c) และการวิ่งผ่านโหนดตามลำดับเป็น D,E,B,C,F,A

ไบนารี่ทรีกับการวิ่งตามลำดับแบบพรี-ออเดอร์  อิน-ออเดอร์  โพสต์-ออเดอร์

การ วิ่งผ่านตามเส้นทางโดยใช้ออเดอร์ทั้ง 3 ชนิดกับทรีนิพจน์ในรูปที่ 9.12 จะได้เป็นนิพจน์ Postfix เมื่อมีการวิ่งแบบพรี-ออเดอร์ ได้เป็นนิพจน์ Infix เมื่อมีการวิ่งแบบอิน-ออเดอร์และได้เป็น นิพจน์ Postfix เมื่อมีการวิ่งแบบโพสต์-ออเดอร์ ตามลำดับดังนี้

ทรี a  พรี-ออเดอร์                                               +cde

อิน-ออเดอร์            : c*d+e

โพสต์-ออเดอร์      cd*c+

ทรี a  พรี-ออเดอร์                                               : /+*+ab/cdefg

อิน-ออเดอร์            : a+b*c/d+e^f/g

โพสต์-ออเดอร์       ab/+cd/*ef^+g/

ไบนารี่เสิร์ชทรี

                ไบนารี่เสิร์ชทรี (Binary Search Tree, BST) เป็นไบนารี่ทรีที่รวบรวมค่าของ N เรคคอร์ดซึ่งเป็นคีย์  (Key) ตั้งแต่  K1 , K2 ,…….Kn โดยแต่ละโหนด Ri  จะมี  Ki เพียง คีย์เดียวสำหรับ i=1,2,….,N คีย์เป็นค่าสร้างความแตกต่าง (Identifier)  ให้ แต่ละโหนด ในการค้นหาโหนดที่ต้องการจะกระทำโดยค้นหาค่าของคีย์ และโหนด Ri  ของไบนารี่เสิร์ชทรีจะถูกจัดการตามคุณสมบัติ ดังนี้

1. ทุก ๆ คีย์ของโหนดที่อยู่ในทรีย่อยด้านซ้ายของ Ri   เป็นค่าที่มาก่อนหรือน้อยกว่าคีย์ของ Ri

If      Ri    €  Left (Ri)

Then  Kj   <  Ki

            1. ทุก ๆ คีย์ของโหนดที่อยู่ในทรีย่อยด้านขวาของ Ri   เป็นค่าที่ตามหลังหรือมากกว่าคีย์ของ Ri

If      Ri    €  Right (Ri)

Then  Kj   >  Ki

 

จะ ไดว่าคีย์ที่มาก่อนจะถูกพิจารณาตามลำดับเชิงเส้นและขึ้นกับลำดับการรวบรวม ดังในรูปที่ 9.14 เมื่อพิจารณาตามคุณสมบัติที่ผ่านมาการค้นหาจะได้คีย์ A,B,C,D ตามลำดับและมี หลายวิธีที่จะจัดการกับไบนารี่เสิร์ชทรี จากรูปดังกล่าวจะมีไบนารี่เสิร์ชทรีหลายแบบแต่ลำดับของคีย์เหมือนกัน

การค้นหาโดยตรง

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

 อัลกิริทึมการค้นหาโดยตรง

การ ค้นหาโดยตรงนอกจากใช้แบบรีเคอร์ซีพ (Recursive) อาจใช้แบบการวนซ้ำก็ได้ ตัวอย่างการค้นหาโหนด C แบบรีเคอร์ซีฟดังในรูปที่ 9.15 เริ่มไปที่รูทโหนด D ของไบนารี่ทรี

ในรูป (a) พบว่าไม่ว่างและตรวจสอบพบว่า C<D จึงวิ่งไปทางทรีย่อยด้านซ้ายที่มีรูทโหนดทรี B

ในรูป (b) พบว่าไม่ว่างและตรวจสอบพบว่า C<B จึงวิ่งไปทางทรีย่อยด้านขวาที่มีรูทโหนดทรีC

ใน รูป (c) พบว่าไม่ว่างและตรวจสอบว่ามีค่าเท่ากัน จึงแจ้งกลับมาว่าพบที่โหนดนี้ สำหรับกรณีหาโหนดที่ต้องการไม่พบการวิ่งจะไปถึงโหนดปลายและไปต่อไม่ได้อีก คือ ตัวชี้มีค่าเป็น Null พร้อมกับแจ้งว่าไม่พบ

ไบนารี่ทรีกับการค้านหาโดยตรงแบบรีเคอร์ซีพ

ใน การค้นหาโดยตรงจะมีประสิทธิภาพเพียงใดก็ขึ้นกับโหนดที่ต้องการหาอยู่ใน ตำแหน่งใดของทรี ซึ่งพิจารณาจากจำนวนการเปรียบเทียบค่า (Comparison) เช่น ไบนารี่ทรีในรูปที่ 9.13

ถ้าต้องการโหนด D จำนวนการเปรียบเทียบค่าของทรีในรูป (a) 1 ครั้ง ทรีในรูป (b) 4 ครั้ง

ทรีในรูป (c) 3 ครั้ง  และทรีในรูป (d)  2 ครั้ง

การเพิ่มโหนดใหม่ในไบนารี่ทรี

                การ ปฏิบัติการแทรกโหนดใหม่ไว้ในไบนารี่ทรีและการลยโหนดออกจากไบนารี่ทรีมี ลักษณะตรงไปตรงมา ดังในรูปที่ 6.16 เป็นการเพิ่มโหนด G ที่รูทโหนด X ของทรีย่อยด้านขวาซึ่งมีได้มี 2 กรณี คือ เพิ่มโหนด G เป็นโหนดปลายในรูป (A) และไม่เป็นในรูป (B) โดยขึ้นกับโหน ด X มีทรีย่อยหรือไม่

การเพิ่มโหนดใหม่ 2 กรณีไว้ในไบนารี่ทรี

แต่ โดยทั่งไปการเพิ่มโหนดใหม่จะนำไปไว้ที่หโนดปลายเสมอตามโครงสร้างของไบนารี่ ทรีโดยอับกอริทึม การแทรกจะมีความคล้ายกับอัลกอริทึมการค้นหาที่ผ่านมา ดังในตารางที่ 9.5 เมื่อมีโหนดใหม่ที่มีคีย์ K เข้ามา

อัลกอริทึมการแทรกโหนดใหม่

การ ทำงานดังกล่าวเป็นแบบรีเคอร์ซีฟและใช้กับตัวอย่างการแทรกโหนดใหม่โดยมีไบนา รี่ทรีสร้างขึ้นมาดังในรูปที่ 9.17(a) และต้องการแทรกโหนดที่มีคีย์ R

ไบนารี่ทรีที่จะมีการแทรกโหนดใหม่

จาก ไบนารี่ทรีเมื่อแทรกโหนดที่มีคีย์ R เข้ามาจะเริ่มต้นที่รูทและเปรียบค่าของ คีย์ R เข้ามาจะเริ่มต้นที่รูทและเปรียบเทียบค่าของคีย์ R กับรูทใน รูป (a) จะได้ R>O จึงจะวิ่งไปทางทรีย่อยด้านขวา จากนั้นเปรียบเทียบค้าของคีย์ R กับรูทของรีย่อยในรูป(b) จะได้ R<T ก็จะ วิ่งไปทางทรีย่อยด้านซ้าย ซึ่งเป็นโหนดปลายในรูป (c) เมื่อเปรียบเทียบค่ากับคีย์ R จะได้  R>P และ ไม่มีทรีย่อยด้านขวา แสดงให้ทราบว่าคีย์ R ยังไม่มีในทรี จึงแทรกโหนกที่มีคีย์  R เป็นโหนดลูกด้านขวาเข้าไปได้เป็นรูป (d)

การลบโหนดออกจากไบนารี่ทรี

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

                1.เมื่อโหนดที่ต้องการลบเป็นโหนดปลาย  การ ลบจะไม่ยุ่งยาก เพียงแต่เปลี่ยนตัวชี้ของโหนดพ่อให้มีค่าเป็น Null ดังในรูปที่ 9.18 (a) ต้องการลบโหนดปลาย D  หลังจากค้นหาโหนดที่ต้องการลบ ก็จะกำหนดตัวชี้ด้านขวาของโหนด C ซึ่งเป็นโหนดพ่อให้มีค่าเป็น Null แทน โหนดปลาย D ก็ถุกปล่อยทิ้งไปได้เป็นรูป (b)  ซึ่งตัวชี้ที่ถูกเปลี่ยน เป็น Null นี้จะขึ้นกับโหนดลูกที่จะลบเป็นด้านซ้ายหรือด้านขวา

การลบโหนดปลาย D ออกจากไบนารี่ทรี

2.เมื่อโหนดที่ต้องการลบมีดหนดลูกหนึ่งโหนด    การ ลบจะไม่ยุ่งยากเช่นกันเพียงเปลี่ยนตัวชี้ของโหนดพ่อให้ชี้ไปยังโหนดลูกของ โหนดที่ต้องการลบแทน ดังในรูปที่ 9.19 (a) ต้องการลบโหนด E หลังจากต้นหาพบโหนดที่ต้องการบลบ ก็จะกำหนดตัวชี้ด้านขวาของโหนด A  ซึ่งเป็นโหนดพ่อชี้ไปยังโหนด C  ที่เป็น โหนดลูกแทน ส่วนโหนด E ก็ถูกปล่อยทิ้งไปเป็นรูป (b)

การลบโหนด E ที่มีโหนดลูกหนึ่งโหนด

3. เมื่อโหนดที่ต้องการลบมีโหนดลูกสองโหนด  การลบโหนดจะกระทำได้สองแบบ คือ

3.1 นำค่าที่มากที่สึดในทรีย่อยด้านซ้าย (Inorder Predecessor) จากโหนดพรีดีเซสเซอร์ (Predecessor Node) มาแทนค่าในโหนดที่ต้องการลบ และโหนดพรีดีเซสเซอร์

3.2 นำค่าที่น้อยที่สุดในทรีย่อยด้านขวา (Inorder Successor) จากโหนดซัคเซสเซอร์ (Successor Node) มาแทนค่าในโหนดลูกสองโหนดแบบที่สองดังในรูปที่ 9.20 (a) ที่ต้องการลบ J หลังจากค้นพบโหนดที่ต้องการลบ จากนั้นทำการหาค่าที่น้อยที่สุดในทรีย่อยด้านขวาโดยการวิ่งลงมาตามเส้นทาง จากโหนดลูกด้านขวาได้เป็นรูป (b) ซึ่งพบที่โหนดซัคเซคเซอร์ Kและนำค่า K ไป เก็บไว้แทนค่า J ได้เป็นรูป (c) หลังจากนั้นทำการลบโหนดซัคเซสเซอร์ K ออกไป โดยให้ฌหนด M ซึ่งเป็นโหนดพ่อชี้ไปยัวโหนด C ที่เป็นโหนดลูกแทน ได้ดังรูป (d)

การใช้ไบนารี่เสิร์ชทรีแทรกข้อมูลเก็บไว้ทีละค่า

                หลัง จากเก็บครบทุกค่า ต่อไปเป็นการวิ่งตามเส้นทางต่อไปแต่ละโนดแบบอิน-ออเดอร์ในรูปที่ 9.22 และดึงค่าออกมาจากแต่ละโหนดก็จะได้ค่าที่เรียงตามลำดับ คือ 22,33,44,55,66,77,88,99 เมื่อเขียนโปรแกรมดังในตารางที่ 9.6 คือ โปรแกรมBinaryTree.c

การใช้ไบนารี่เสิร์ชทรีจัดเรียงลำดับข้อมูล

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s