บทที่ 8 ทรี (Tree)

ทรี (Tree)

    โครงสร้างข้อมูลที่ออกแบบมาให้มีลักษณะไม่เป็นเชิงเส้น มีการจัดเก็บข้อมูลเชื่อมโยงกันเป็นระดับชั้น โดยเริ่มจากโหนดแรกที่อยู่บนสุดเรียกว่า Root Node เชื่อมโยงไปยังโหนดระดับรองลงไป แต่ละระดับก็มีการเชื่อมโยงโหนดระดับต่อไป ซึ่งเรียกว่า Subtree

  

    โครงสร้างข้อมูลแบบต้นไม้ มีคุณสมบัติดังนี้

   1. มีโหนดที่เรียกว่า รากหรือรูต (Root node) , R
   2. โหนดที่ไม่ใช่รูตแบ่งย่อยออกเป็น n กลุ่ม โดยที่แต่ละกลุ่มไม่มีโหนด ร่วมกันเลย  เช่น กลุ่ม T1 , T2 ,…..Tn (n >=0) แต่ละกลุ่มก็เป็นต้นไม้เหมือนกัน จะเรียกว่าต้นไม้ย่อย (Subtree)
     ลักษณะของทรี

    

        จากรูป

    R   เป็นรูทของต้นไม้ย่อย A,B,C,D

   A  เป็นรูทของต้นไม้ย่อย E,F,G

   F  เป็นรูทของต้นไม้ย่อย J

   B   เป็นรูทของต้นไม้ย่อย H และ I 

      

     ชื่อส่วนต่างๆของต้นไม้

      ระดับของโหนด (Level)

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

      ดีกรีของโหนด คือ จำนวนต้นไม้ย่อยของโหนดนั้น    

      โหนดที่เป็นใบ หมายถึง โหนดที่มีดีกรีเป็น 0 ส่วนโหนดที่มีดีกรีไม่เท่ากับ 0 เรียกว่า โหนดภายใน หรือ interior node  หรือ branch node

    Immediate Successor คือโหนดทั้งหลายของต้นไม้ย่อย i ที่มีค่าระดับต่ำกว่าโหนด i อยู่หนึ่ง 

   Immediate Predecessor คือโหนดที่มีค่าระดับสูงกว่าโหนด i อยู่หนึ่ง

      

     โครงสร้างต้นไม้ (Tree Structure)

    Level แสดงถึงหน่วยระยะทางตามแนวดิ่งของโหนดว่าอยู่ห่างจาก 

    Root Node เป็นระยะเท่าไรและทุกกิ่งมีความยาวเท่ากันคือ 1 หน่วย

    

      Degree แสดงถึงจำนวนของ Subtree ของโหนดนั้น เช่น A มี Degree2,X มี Degree 1

     Leaf Node แสดงถึงโหนดที่มี Degree = 0 เช่น C, D, E, I ,G ส่วนโหนดที่มี Degree <> 0 เรียกว่า   Branch Node หรือ Interior Node

     Predecessor หมายถึง ตัว Node ที่อยู่ก่อนหน้า

     Successor    หมายถึง ตัว Node ที่มาที่หลัง เช่น R, B, H เป็น Predecessor ของ E, I, 

      I เป็น Successor ของ H

     

      ต้นไม้แบบไบนารี (Binary Tree)

        ต้นไม้ไบนารีเป็น rooted binary tree ที่ว่างเปล่า  หรือประกอบด้วยรูตโหนดและต้นไม้ไบนารี 2 กลุ่มที่ไม่มีโหนดร่วมกัน  แต่ละกลุ่มจะมีชื่อเรียก (โดยตำแหน่งที่อยู่หรือที่เขียน) ว่าต้นไม้ย่อยทางซ้าย (left subtree) และต้นไม้ย่อยทางขวา (right subtree) ตามลำดับ คำว่า ว่างเปล่า ในนิยามหมายความว่า ต้นไม้ไบนารีต้นนั้นมีแต่รูตโหนดเพียงโหนดเดียวเท่านั้น

ต้นไม้ไบนารีแบบสมบูรณ์  (Complete Binary Tree)  

     ต้นไม้ไบนารีแบบสมบูรณ์  หมายถึง ต้นไม้ไบนารีที่แต่ละโหนดภายในมีโหนดย่อยซ้ายและขวา (นั่นคือแต่ละโหนดภายในมี left son และ right  son ) และโหนดใบ (leaf nodes) ทั้งหลายอยู่ในระดับที่ n รูป (ก) เป็นต้นไม้ไบนารีแบบสมบูรณ์ที่มี 3 ระดับ

ต้นไม้ไบนารี

      

ต้นไม้ไบนารีแบบสมบูรณ์ที่มีโหนดใบอยู่ที่ระดับ n จะมีโหนดทั้งหมดเท่ากับ 2n-1

จากรูป จำนวนโหนดเท่ากับ 23-1 =  7 โหนด

     การเปลี่ยน Tree ให้เป็น Binary Tree

     ต้นไม้แบบออดินารี(ordinary) คือต้นไม้ที่มีดีกรีสูงสุดของแต่ละโหนดเป็นเท่าไรก็ได้ ซึ่งการเปลี่ยนให้เป็น binary tree เป็นการจัดให้แต่ละโหนดมีดีกรีสูงสุดเท่ากับสอง  มีขั้นตอนดังนี้

 1. พิจารณาที่กิ่งทางซ้ายสุดที่อยู่ใต้พ่อเดียวกัน

 2. ต่อกิ่งของโหนดทางซ้ายสุดในขั้นที่ 1 ไปทางขวาตามลำดับอาวุโสกับพี่น้องที่เกิดจากพ่อเดียวกัน 

 3. ทำขั้นที่ 1 และ 2 จนครบทุกโหนด

 4. ปรับมุมของแต่ละกิ่ง ประมาณ 45 องศา

      

    การท่องต้นไม้ (Tree Traversal)

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

 1. Pre-Order Traversal (RTLTR)

        2. In-Order Traversal (TLRTR)

        3. Post-Order Traversal (TLTRR)

   การท่องผ่าน Binary Tree
        การท่องผ่านโหนด หมายถึง การเข้าไปในโครงสร้างต้นไม้เพื่อนำข้อมูลในโหนดมาแสดง หรือเพื่อการค้นหา หรือการประมวลผล การเดินเยี่ยมโหนดมี 3 วิธี

 1. Inorder traversal หรือ Symmetric order    จะทำการเยี่ยมโหนดในต้นไม้ย่อยทางซ้ายแบบอินออเดอร์ ก่อนเยี่ยมโหนดรากและเยี่ยมโหนดในต้นไม้ย่อยทางขวาแบบอินออเดอร์ (Left/ Root/Right)

 2. Preorder traversal จะทำการเยี่ยมโหนดรากก่อน เยี่ยมโหนดในต้นไม้ย่อยทางซ้ายแบบพรีออเดอร์ และเยี่ยมโหนดในต้นไม้ย่อยทางขวาแบบพรีออเดอร์ (Root/ Left/ Right)

 3. Postorder traversal หรือ Endorder  จะทำการเยี่ยมโหนดในต้นไม้ย่อยทางซ้ายแบบ โพสออเดอร์ ก่อนเยี่ยมโหนดในต้นไม้ย่อยทางขวาแบบ  โพสออเดอร์ และเยี่ยมโหนดราก   (Left/ Right/ Root)

    

     1.แบบอินออเดอร์ (Left/ Root/Right)  จากภาพจะได้ BAC   

     2.แบบพรีออเดอร์(Root/ Left/ Right) จากภาพจะได้ ABC

     3.แบบโพสออเดอร์(Left/ Right/ Root) จากภาพจะได้ BCA 

     Expression Tree

    เป็นต้นไม้แบบไบนารีที่ โหนดใบคือ operands, เช่นค่าคงที่หรือตัวแปร, และโหนดรากคือ operators

จากรูปแสดง   Expression tree ของ (a + b * c) + ((d * e + f ) * g)

     Expression Tree 

     คือต้นไม้ที่สร้างขึ้นจากตัวกระทำ(operand)     และเครื่องหมาย(operators) ทางคณิตศาสตร์ของนิพจน์ โดยการวางตัวกระทำที่โหนดใบ(leave node) และวางเครื่องหมายไว้ที่โหนดภายใน

      สำหรับเครื่องหมายที่เป็นเครื่องหมายเดี่ยว(unary operator) จะมีกิ่งต้นไม้ย่อยเพียงข้างเดียว เรามักจะวาง เครื่องหมายเดี่ยวไว้ทางซ้ายของตัวกระทำ ซึ่งเครื่องหมายที่จัดเป็นเครื่องหมายเดี่ยว ได้แก่ -   log()   cos() และมีเครื่องหมายเดี่ยว ที่ถูกจัดวางไว้ทางขวาของตัวกระทำ ได้แก่  แฟกทอเรียลฟังก์ชัน   เลขยกกำลังต่างๆ

    

     การสร้าง Expression Tree

      อ่านสัญลักษณ์จากนิพจน์ที่ละตัว ถ้าตัวที่อ่านมาเป็น operand ให้สร้างโหนดของ tree หนึ่งโหนดแล้ว push มันลงใน stack ถ้าตัวที่อ่านมาเป็น operator ให้ pop จาก stack 2 ครั้ง ซึ่งจะได้ trees T1 และ T2 (T1 นำออกก่อน) แล้วให้นำมาสร้างเป็น tree ใหม่ที่มีราก (root) เป็นตัว operator และมี left และ right children เป็น T2 และ T1 ตามลำดับ จากนั้นให้ใส่ tree ใหม่นี้กลับลง stack