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
โครงสร้างข้อมูลที่ออกแบบมาให้มีลักษณะไม่เป็นเชิงเส้น มีการจัดเก็บข้อมูลเชื่อมโยงกันเป็นระดับชั้น โดยเริ่มจากโหนดแรกที่อยู่บนสุดเรียกว่า Root Node เชื่อมโยงไปยังโหนดระดับรองลงไป แต่ละระดับก็มีการเชื่อมโยงโหนดระดับต่อไป ซึ่งเรียกว่า Subtree
โครงสร้างข้อมูลแบบต้นไม้ มีคุณสมบัติดังนี้
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
ต้นไม้ไบนารีแบบสมบูรณ์ที่มีโหนดใบอยู่ที่ระดับ 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 วิธี
การท่องผ่านโหนด หมายถึง การเข้าไปในโครงสร้างต้นไม้เพื่อนำข้อมูลในโหนดมาแสดง หรือเพื่อการค้นหา หรือการประมวลผล การเดินเยี่ยมโหนดมี 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
ไม่มีความคิดเห็น:
แสดงความคิดเห็น