วันอาทิตย์ที่ 23 เมษายน พ.ศ. 2560


                                                                         บทที่ 5 


ทรี  ( Trees )
ทรี

                       ทรีเปรียบเสมือนกับต้นไม้ที่มีราก (Root) และมีลำต้นที่แผ่กิ่งก้านสาขา  โดยแต่ละ
กิ่ง(Branch)ก็จะมีการผลิใบ (Leaf) ไปทั่ว ซึ่งเป็นไปตามความสัมพันธ์ในลักษณะแบบลำดับชั้น
(Hierarchical Relationship) และตัวทรีมีโครงสร้างแบบลำลับชั้นนี้เอง จึงมักนำไปใช้เพื่อนำ
เสนอเป็นแผนผังองค์กร (Organization Chart) โครงสร้างไดเรกทอรี (Diractory) หรือแม้กระ
ทั่งสมาชิกครอบครัวของทรีเอง
                   ทรีประกอบด้วยโหนด (Node) ที่ใช้สำหรับบรรจุข้อมูล โดยจะมีกิ่งซึ่งเป็นเส้นที่เชื่อม
โยงโหนดเข้าด้วยกันที่เรียกว่าบรานช์ (Branch) จำนวนของบรานช์ที่สัมพันธ์กับโหนดเรียกว่าดีกรี
(Degree) และ ถ้าหากทรีนั้นเป็นทรีที่ไม่ใช่ที่ว่าง โหนดแระจะเรียกว่ารูท (Root) โดยโหนดทุก ๆ
โหนดยกเว้นรูทโหนดจะมีเพียง 1 Predecessor ในขณะที่ Successor อาจเป็น 0 หรือ 1 หรือ
มากกว่า 1 ก็ได้








  1. โหนดแรก (Root Node)

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

โหนดพ่อ (Parents) คือโหนด A,B และ F ซึ่งก็คือโหนดที่มี Successor

โหนดลูก (Children) คือโหนด B,E,F,C,D,G,H และ I ซึ่งก็คือโหนดที่มี Predecessor

โหนดพี่น้อง (Siblings) คือโหนด {B,E,F},{C,D}และ{G,H,I}

- โหนดใบ (Leaf Node) คือโหนด C,D,E,G,H และ I ซึ่งก็คือโหนดที่ไม่มี Successor
ดีกรีทั้งหมดของทรี มีค่าเท่ากับ 8
- ดีกรีทั้งหมดของโหนด F มีค่าเท่ากับ 3
จำนวนของ Leaf โหนด มีค่าเท่ากับ 6
ระดับความสูงหรือความลึกของทรี คำนวณได้จากสูตร Height =2+1=3
                  นอกจากนี้  ทรียังสามารถแบ่งย่อยออกเป็นซับทรี  (Subtrees) หรือเรียกว่าทรีย่อย
ซึ่งซับทรีเหล่านี้จะเป็นโครงสร้างที่มีการเชื่อมโยงถัดจากรูทโหนด  สำหรับโหนดแรกของซับทรีก็
คือรูทโหนดของซับทรีนั้น ๆ  และยังใช้เป็นชื่อเรียกของซับทรีนั้นด้วย  นอกจากนี้ซับทรียังสามารถ
แบ่งส่วนย่อยออกเป็นซับทรีย่อย ๆ ได้อีก







รูปแบบการนำเสนอโครงสร้างข้อมูลทรี (Tree Representation)

                เราสามารถนำเสนอโครงสร้างข้อมูลทรีให้แตกต่างกันได้ถึง 3 รูปแบบด้วยกันคือ

1. แบบโครงสร้างทรีทั่วไป (General Tree)
                   เป็นรูปแบบการนำเสนอเหมือนกับผังองค์กรทั่วไปที่ลดหลั่นเป็นลำดับชั้น ซึ่งรูปแบบดังกล่าว ถือว่าเป็นรูปแบบของทรีที่นิยมใช้งานโดยทั่วไป โดยตัวอย่างแสดงไว้ดังรูปที่6.3 (a)

2.แบบย่อหน้า (Indented List)
                เป็นรูปแบบที่คล้ายกับการเขียนโปรแกรมเชิงโครงสร้าง  ที่ใช้ย่อหน้าเป็นตัวกำหนดรูป
แบบของโครงสร้างในส่วนระดับย่อย ๆ ลงไป โดยตัวอย่างดังกล่าวแสดงไว้ดังรูปที่ 6.3 (b)

3.แบบวงเล็บ (Parenthetical List)
                 รูปแบบนี้มีความคล้ายคลึงกับการแทนข้อมูลด้วยนิพจน์คณิตศาสตร์ด้วยการใช้เครื่องหมาย
วงเล็บกำกับ  ซึ่งนำเสนอไว้ดังรูปที่ 6.3 ( c )


ไบนารีทรี (Binary Tees)
                  ไบนารีทรีจัดเป็นทรีชนิดหนึ่งที่มีความสำคัญมาก โดยมีคุณสมบัติสำคัญคือเป็นทรีที่
สามารถมีลุกได้ไม่เกินสองโหนด ในทุกๆ โหนดอาจมีลูกเพียงด้านซ้ายหรือด้านขวา หรืออาจมีลูกทั้ง
ซ้ายและขวา หรืออาจไม่มีลูกเลยก็ได้ หรือกล่าวอีกในหนึ่งก็คือ เป็นทรีที่แต่ละโหนดจะมีซับทรี<=2
นั่นเอง พิจารณาจากรูปที่ 6.4 ซึ่งเป็นไบนารีทรีที่ประกอบด้วย 2 ซับทรีโดยแต่ละซับทรีทั้งด้านซ้าย
และด้านขวาต่างก็มีคุณสมบัติเป็นไบนารีทรี






คุณสมบัติของไบนารีทรี (Properties)
                   ด้วยคูณสมบัติของไบนารีทรีจึงทำให้ไบนารีทรีมีคุณสมบัติพิเศษกว่าทรีทั่วไป ซึ่งประ
กอบด้วยคุณสมบิติที่สามารถนำไปคำนวณเพื่อหาผลลัพธ์ได้ดังต่อไปนี้
 - ความสูงน้อยที่สุดของทรี (Minimum Height)                   หากต้องการจัดเก็บโหนดจำนวน N โหนดในไบนารีทรี ความสูงน้อยที่สุดของทรีดัง
กล่าวสามารถคำนวณได้จากสูตร

Hmin = [log2N]+
- จำนวนโหนดน้อยที่สุด (Minimum Nodes)
                
เราสามารถคำนวณเพื่อการตัดสินใจว่า จำนวนโหนดน้อยที่สุดที่สามารถมีได้ใน
ไบนารีทรีมีจำนวนเท่าไรได้จากสูตร

Nmin =H
- จำนวนโหนดมากที่สุด (Maximum Nodes)
               
 สำหรับสูตรการคำนวณหาจำนวนโหนดมากที่สุดที่มีได้ในไบนารีทรี จะพิจารณาจาก
ความเป็นจริงด้านคุณสมบัติของไบนารีทรีคือ แต่ละโหนดสามารถมีลูกได้สูงสุดไม่เกิน 2 โหนด
ซึ่งสามารถคำนวณได้จากสูตร

Nmix =2H-1
- ความสมดุล (Balance)
                
ความสมดุลของไบนารีทรีจะสามารถทราบได้จากค่า Balance Factor เท่ากับ
0 ซึ่งค่าดังกล่าวคำนวณได้จากการนำความสูงของซับทรีด้านซ้าย (HL) มาหักลบกับความสูงของ
ซับทรีด้านขวา (HR) ที่เป็นไปตามสูตรดังนี้

B = Hl-HR

และจากสูตรดังกล่าว  ความสมดุลของทรีจากรูปที่ 6.5 ก็คือ (a)=0,(b)=0,(c)=1,(d)=1,(e)=0,
(f)=1,(g)=-2 และ (h)=2






- แบบสมบูรณ์จะมี Subtree ด้านซ้ายและขวาเท่ากัน
             
   




- แบบเกือบสมบูรณ์ Subtree  ทางด้านซ้ายจะไม่มี
                
              
         

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



การท่องเข้าไปในไบนารีทรี (Binary tree traversals)
                          การท่องเข้าไปในไบนารีทรีซึ่งแต่ละโหนดอย่างน้อยจะต้องถูกกระทำ 1 ครั้งโดยตัว
อย่างการกระทำ เช่น การค้นหาที่ต้องเดินทางผ่านโหนดแต่ละโหนดตามลำดับ เป็นต้น และโดยปกติ
วิธีการท่องเข้าไปในทรีจะมีอยู่2วิธีด้วยกันคือ วิธีท่องแบบแนวลึก (Depth-First) วิธีการท่องแบบ
แนวกว้าง (Breadth First)

วิธีการท่องแบบแนวลึก (Depth-First Traversals)
                    เป็นวิธีการท่องเข้าไปในทรีด้วยการเดินทางผ่านรูทโหนดลงไปยังโหนดลูก ๆ ซึ่งมี
ทั้งฝั่งด้านซ้ายและด้านขวา ดังนั้นจึงมีการบัญญัติคำย่อเพื่อใช้งานดังนี้คือ

         N แทนรูทโหนด
         L แทนซับทรีด้านซ้าย
         R แทนซับทรีด้านขวา

                          สำหรับวิธีการท่องแบบแนวลึก ในที่นี้จะขอกล่าวเพียง 3 วิธีมาตรฐานที่นิยมใช้
กันอย่างแพร่หลาย ซึ่งประกอบด้วยวิธี Preorder,Inorder และ Postorder
  (a) Preorder traversal       
   
(b) Inorder traversal         
          
- แบบพรีออร์เดอร์ (Proerder Traversal : NLR)
                           วิธีการท่องเข้าไปในทรีแบบ Proerder จะท่องในรูปแบบของ NLR คือ
จะเริ่มต้นกระทำที่รูทโหนดก่อนเป็นลำดับแรก จากนั้นก็ตามด้วยซับทรีด้านซ้ายและซับทรี
ด้านขวา

- แบบอินออร์เดอร์ (Postorder Traversal:LRN)
                           วิธีการท่องเข้าไปในทรีแบบ Inorder จะท่องในรูปแบบของ NLR คือ
จะเริ่มต้นกระทำที่ด้านซ้ายก่อนเป็นลำดับแรก  จากนั้นก็ตามด้วยรูทโหนด  และท้ายสุดก็คือ
ซับทรีด้านขวา
- แบบโพสต์ออร์เดอร์ (Postorder Traversal : LRN)

                           วิธีสุดท้ายของการท่องเข้าไปในทรี ก็คือแบบ Postorder ซึ่งจะท่องใน
รูปแบบของ LRN คือ จะกระทำที่รูทโหนดเป็นลำดับสุดท้าย  ด้วยการเริ่มต้นที่ซับทรีด้านซ้าย
และตามด้วยซับทรีด้านขวาก่อน จากนั้นก็จะจบลงที่รูทโหนด 
- วิธีการท่องแบบแนวกว้าง (Breadth-First Traversals)
                    เป็นวิธีสุดท้ายของการท่องเข้าไปในทรีด้วยการกระทำทีละระดับจากบน
ลงล่าง  โดยจะเริ่มต้นจากรูทโหนด  แล้วจึงค่อยเข้าถึงแต่ละโหนดในแต่ละระดับตามแนว
กว้างจากซ้ายไปขวา จนกระทั่งครบทุกระดับ ซึ่งแสดงตัวอย่างการทำงานได้ดังรูปที่ 6.11


การค้นหาข้อมูลในไบนารีเสริช์ทรี (BST Search)
                     สำหรับในหัวข้อต่อไปนี้จะศึกษาเกี่ยวกับ 3 อัลกอริทึมเพื่อการค้นหาข้อมูล ซึ่งประ
กอบด้วยการค้นหาโหนดที่มีค่าต่ำสุด ค่าสูงสุด และการค้นหาโหนดตามที่ต้องการ
การค้นหาโหนดที่มีค่าต่ำสุด (Find the Smallest Node)
                 
จากไบนารีเสิร์ชทรีดังรูปที่ 6.17 จะเห็นได้ว่าโหนดที่มีค่าต่ำสุดก็คือ 12 ซึ่งจะอยู่ตำ
แหน่งโหนดใบด้านซ้ายของทรี ดังนั้นการค้นหาโหนดที่เก็บค่าต่ำสุดในทรี ก็สามารถทำได้ง่ายมาก
ด้วยการเดินตามไปยัง บรานช์ทางซ้ายมือไปจนกระทั่งถึงโหนดใบ (Leaf Node) แล้วก็จะพบ
โหนดที่มีค่าต่ำที่สุดในไบนารีเสิร์ชทรีเอง
การค้นหาที่มีค่าสูงสุด (Find the Largest Node)
                      การค้นหาโหนดที่มีค่าสูงสุดใน BST จะเป็นวิธีแบบตรงกันข้ามกับแบบแรก ดังนั้น
การค้นหาจะเริ่มต้นจากรูทโหนดและเดินตามไปยังบรานช์ฝั่งขวา จนกระทั่งพบโหนดที่มีค่าสูงสุด
การค้นหาโหนดตามที่ต้องการ (Find a Requseted Node)
                การค้นหาข้อมูลตามที่ต้องการในไบนารีเสิร์ชนั้นทำงานอย่างไร โดยพิจารณาจากรูป
ที่ 6.18 โดยสมมติว่าค่า Target  ที่ต้องการค้นหาคือ 19 และเมื่อได้นำค่านี้ไปเทียบกับรูทโหนด
(ค่ากึ่งกลางในอาร์เรย์)แล้วก็จะพบว่าค่าที่ต้องการค้นหานั้นมีค่าน้อยกว่ารูทโหนด  ดังนั้นจึงทำการ
เปรียบเทียบค่า Target กับทรีด้านซ้ายเท่านั้น  ซึ่งก็คือซับทรี  16 นั่นเอง  ผลปรากฏว่าค่าที่ต้อง
การมีค่ามากกว่ารูทโหนดของซับทรี จึงทำการตรวจสอบกับโหนดด้านขวาต่อไปจนพบในที่สุด
           

การดำเนินงานในไบนารีเสิร์ชทรี (BST Operations)
                สำหรับการดำเนินงานในไบนารีเสิร์ชในที่นี้  จะกล่าวถึงฟังก์ชันการแทรกโหนดและ
การลบโหนดออกจากไบนารีเสิร์ชทรี
การแทรกโหนด (Insertion)
                    ฟังก์ชันการแทรกโหนด  ก็คือการเพิ่มข้อมูลเข้าไปใน BST ในการแทรกข้อมูลที่
ต้องการนั้น  หากเป็นทรีว่าง ก็จะดำเนินการติดตามบรานซ์เพื่อไปยังซับทรีที่ว่างโดยโหนดใหม่ที่
แทรกที่ตำแหน่งโหนดใบ  หรือโหนดที่คล้ายกับโหนดใบ  (Leaflike  Node) ซึ่งก็คือโหนดที่มีหนึ่ง
ซับทรีที่เป็นทรีว่าง  หรือกล่าวอีกนัยหนึ่งก็คือ  การแทรกโหนดใด ๆ ก็ตามจะกระทำการแทรกที่
โหนดใบในตำแหน่งที่ยังคงไว้ซึ่งคุณสมบัติของ BST
          






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

เอวีแอลเสิร์ชทรี  (AVL Search Trees)        
               หลังจากที่ได้ศึกษารายละเอียดเกี่ยวกับไบนารีเสิร์ชทรีแล้ว  คุณสมบัติของ BST
สามารถนำไปประยุกต์ใช้งานให้เกิดประโยชน์มากมาย  แต่อย่างไรก็ตาม  ก็มีปัญหาหนึ่งซึ่งถือ
ว่าเป็นปัญหาหลีกของ BST ก็ว่าได้  นั่นก็คือความไม่สมดุลของทรี  ซึ่งต่อมาจึงมีการคิดค้นและ
พัฒนาโครงสร้างทรีแบบเอวีแอลขึ้นเอวีแอลทรีก็คือไบนารีเสิร์ชทรีที่ซับทรีด้านซ้ายและซับทรี
ด้านขวาจะมีค่า Balance Factor เท่ากับ +1.0 หรือ -1 เท่านั้น ที่เป็นไปตามสูตรด้านล่างต่อ
ไปนี้  โดยที่ HL คือความสูงของซับทรีด้านซ้ายส่วน HR ก็คือซับทรีด้านขวา  ซึ่งทั้งสองจะอยู่
ภายใต้สัญลักษณ์ | | ที่หมายถึงเครื่องหมาย Absolute
                ค่า Balance Factor ของทุกโหนดจะต้องมีค่าเท่ากับ +1 ,0 หรือ-1 ดังนั้นผลลัพธ์
ที่ได้จากหนึ่งในสามนี้ หมายถึง
  • +1 หมายถึง ซ้ายสูง (Left High : LH)
  • 0   หมายถึง สูงเท่ากัน (Even High :EH)
  • -1  หมายถึง ขวาสูง (Right High : RH)
































































































































ไม่มีความคิดเห็น:

แสดงความคิดเห็น