Park-Kachen
08 กันยายน 2552
DTS08-26-08-2552
โครงสร้างข้อมูลทรี
โครงสร้างข้อมูลในบทต่าง ๆ ที่ดังกล่าวผ่านมาเป็นโครงสร้างเชิงเส้น (Linear Data Structure) แต่ละสมาชิกจะมีสมาชิกตัวถัดไปเพียงตัวเดียว สำหรับในบทนี้จะกล่าวถึงโครงสร้างข้อมูลไม่เป็นเชิงเส้น (Nonlinear Data Structure) ซึ่งแต่ละสมาชิกสามารถมีสมาชิกตัวถัดไปได้หลายตัว โดยมีแนวความคิดของโครงสร้างแตกสาขา (Branching Structure) และเป็นที่รู้จักคือ โครงสร้างข้อมูลทรี (Tree) ซึ่งกล่าวถึงในบทนี้กับโครงสร้างข้อมูลกราฟ (Graph)
ทรีทั่วไป
จากลักษณะของทรีทั่วไป (General Tree) มีการกำหนดเป็นระดับซึ่งมีตัวแรก คือรูททรี (Rooted Tree) ซึ่งมีเพียงโหนกเดียวทำหน้าที่เป็นรูท (Root) และมีความแตกต่างจากโหนดอื่น ๆ รูทของทรี T จะกำหนดเป็น Root(T) โดยทรี T เป็นเซตจำนวนที่แน่นอน (Finite Set) ตั้งแต่ 0 หรือมากกว่าของโหนด(V1,V2,….,Vn) ดังนั้น
จะมีเพียงโหนอเดียว(V1) ที่ออกแบบเป็นพิเศษ เรียกว่า Root(T)
โหนดที่เหลือ (V2,….,Vn) จะถูกแบ่งออกเป็นส่วน ๆ เท่ากับ m≥ 0 ที่ต่อกันเป็นเซตชื่อ T1, T2,…..,Tmจะได้ว่าแต่ละ Ti คือ ทรีและเป็นทรีย่อย
หากทรีใด ๆ ไม่มีโหนดเลยเรียกว่านัลทรี (Null Tree)
รูปที่9.1 ตัวอย่างทรีทั่วไป
จากรูปที่ 9.1 เป็นตัวอย่างทรีที่แสดงแต่ละโหนด โดยใช้ตัวอักษรอยู่ภายในวงกลมและมีรูทของทรี Root(T) = A ทรีย่อยของรูท A ประกอบด้วยรูท B,C,D ซึ่งจะได้ B เป็นรูทของทรีที่มีหนึ่งทรีย่อยของรูท E ที่ไม่มีทรีย่อย ทรีที่มีรูท C จะมีสองทรีย่อยคือที่รูท F และรูท G ตามลำดับ
บางครั้งอาจมีการกำหนดลักษณะให้กับเอจ (Edge) ของทรีมีทิศทาง โดยเอจจะเริ่มจากรูทโหนดไปยังรูทของทรีย่อย ดังในรูปที่ 9.2 เป็นทรีคว่ำในลักษณะของโครงสร้างทรีที่นิยมใช้กันโดยรูทอยู่ด้านบนสุด (Top) ดังที่กล่าวมาโหนดที่ออกแบบเป็นพิเศษ คือ รูท มีความแตกต่างจากโหนดอื่น ๆ ด้วยคุณสมบัติที่ว่า In-degree(v) = 0 for v = Root(T)
รูปที่ 9.2 ตัวอย่างโครงสร้างข้อมูลทรีทั่วไปกับเอจที่มีทิศทาง โหนดที่เป็นรูทจะมีจำนวนเอจหรือกิ่งเข้ามาหรือดีกรรีเข้า (In-degree) เท่ากับ 0 เนื่องจากทรีเป็นกราฟเชื่อมกันจึงมีได้เพียงโหนดเดียวที่มีคุณสมบัตินี้ และมีทรีย่อยของ A ดังในรูปที่ 9.3 ซึ่งมีเอจเชื่อมจาก A ไม่ใช่โหนดในทรีเหล่านี้
รูปที่ 9.3 ทรีย่อยของทรีในรูปที่ 9.2
ทรีทั่วไปที่กล่าวถึงมีความหมายเช่นเดียวกับต้นไม้มที่มีการสืบทอด ดังนั้น ถ้ามี Edge(A,B) จะได้ว่า A เป็นโหนดพ่อ (Parent Node) ของ BและB เป็นโหนดลูก (Child Node)ของAแต่ละโหนดที่เป็นลูกจะมีโหนดพ่อเพียงโหนดเดียว สองโหนดขึ้นไปที่มีโหนดพ่อเดียวกันเรียกว่าโหนดพี่น้อง (Sibling Node) สำหรับโหนดที่มีจำนวนเอสชี้ออกไปหรือดีกรีออกเป็นโหนดที่ไม่มีโหนดลูก
ไบนารี่ทรี
ประเภทของทรีทั่วไปที่มีความสำคัญมากที่สุด คือ ไบนารี่ทรี (Binary Tree) เป็นเซตของโหนดที่มีจำนวนแน่นอนซึ่งอาจจะว่างเปล่าหรือเชื่อมต่อกับสองไบนารี่ทรีที่เรียกว่าทรีย่อยซ้าย (Left Subtree) และบททรีย่อยขวา (Right Subtree) โดยมีข้อกำหนดว่าดีกรีออกมากที่สุดเท่ากับ 2 ซึ่งกำหนดให้เป็นทรีย่อยด้านซ้ายและขวา จากรูปที่ 9.4 (a) และ (b) เป็นไบนารี่ทรีที่แตกต่างกันเนื่องจาก รูป (a) มีทรีย่อยซ้าย ส่วน (b) ไม่เป็นไบนารี่ทรีเนื่องจากมีทรีย่อยไม่ช่ด้านซ้ายหรือขวาแต่ชี้ตรงลงมา
(a) ทรี 1 (b) ทรี 2 (c) ทรี 3 รูปที่ 9.4 ตัวอย่างทรีที่เป็นไบนารี่ทรี (a),(b) ลัไม่ใช่ (c)
ไบนารี่ที่มีคุณสมบัติที่แตกต่างจากทรีทั่วไป เมื่อพิจารราไบนารี่ทรีที่มี K ระดับในรูปที่ 9.5 จะเรียกว่าไบนารี่ทรีสมบูรณ์ (Complete Binary Tree) ซึ่งจะมีจำนวนโหนดมากที่สุดที่เป็นไปได้ตามความสูงของไบนารี่ทรี จำนวนเอจก็จะเพิ่มเป็นสองเท่าของระดับก่อนหน้ายกเว้นระดับ 0 และจำนวนโหนดมากที่สุดในระดับ I จะได้ว่าไบนารี่ทรีสมบูรณ์ที่มี k ระดับ จะมีโหนดทั้งหมดเท่ากับ 2k-1 เช่น ไบนารี่ทรีสมบูรณ์ที่มี 3 ระดับจะมี 7 โหนด ถ้ามี 10 ระดับ จะมี 1023 โหนด
posted by Park-Kachen at 06:44
0 Comments:
แสดงความคิดเห็น
<< Home