Google    Youtube      Psv     สพม.11

หน่วยที่9โครงสร้างข้อมูลทรี

โครงสร้างข้อมูลทรี

      โครงสร้างข้อมูลในบทต่าง  ๆ  ที่ดังกล่าวผ่านมาเป็นโครงสร้างเชิงเส้น  (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)  ดังนั้น

1.       จะมีเพียงโหนอเดียว(V1)  ที่ออกแบบเป็นพิเศษ  เรียกว่า  Root(T)

2.       โหนดที่เหลือ  (V2,….,Vn)  จะถูกแบ่งออกเป็นส่วน  ๆ  เท่ากับ  m≥ 0  ที่ต่อกันเป็นเซตชื่อ  T1, T2,…..,Tmจะได้ว่าแต่ละ  Ti  คือ  ทรีและเป็นทรีย่อย

3.       หากทรีใด  ๆ  ไม่มีโหนดเลยเรียกว่านัลทรี  (Null  Tree)

ทรีทั่วไป

ทรีที่แสดงแต่ละโหนด  โดยใช้ตัวอักษรอยู่ภายในวงกลมและมีรูทของทรี  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  โหนด

ระดับ  0

ระดับ  1

…..                                                                   ระดับ  2

…..                                      ระดับ  3

.

.

.

ระดับ  k-2

ระดับ  k-1

รูปที่  9.5  ไบนารี่ทรีสมบูรณ์ที่มีจำนวนโหนอครบทุกระดับ

ไบนารี่ทรีสมบูรณ์เรียกอีกอย่างหนึ่งได้ว่าไบนารี่ทรีครบถ้วน  (Strictly  Binary  Tree)  หมายความว่าทุก  ๆ  โหนดในทรีที่ไม่ใช่โหนดปลายจะต้องมีทรีย่อยหรือโหนดลูกทั้งซ้ายและขวาแต่ไบนารี่ครบถ้วนไม่จำเป็นต้องเป็นไบนารี่ทรีสมบูรณ์  สองไบนารีทรีจะมีลักษณะที่เหมือนกัน  ถ้ามรโครงสร้างแบบเดียวกัน  และสองไบนารี่ทรีที่มีลักษณะที่เท่ากันก็ต่อเมื่อมีโครงสร้างแบบเดียวกันและข้อมูลในแต่ละโหนดต้องเป็นแบบเดียวกัน  ดังในรูปที่  9.6  เป็นไบนารี่ทรีที่เหมือรกันแต่ไม่เท่ากัน

รูปที่  9.6  ตัวอย่างสองไบนารี่ทรีครบถ้วนที่เหมือนกันแต่ไม่เท่ากัน

ไบนารรี่ทรีจะเรียกว่าไบนารี่ทรีเกือบสมบูรณ์  (Almost  Complete  Binary  Tree)  เมื่อระดับ  0  ถึงระดับ  k-1  จะมีโหนดเฉพาะบางส่วนอาจเป็นโหนดซ้ายหรือโหนดขวา  ดังในรูปที่  9.7

รูปที่  9.7  ไบนารี่ทรีเกือบสมบูรณ์ที่มีบางโหนดในระดับสุดท้าย

การทำเส้นทางของไบนารี่ทรีมีความยาวมากที่สุดให้สั้นที่สุดโดยการทำให้เป็นไบนารี่ทรีเกือบสมบูรณ์  ก็จะได้เส้นทางซึ่งเป็นความสูงน้อยที่สูด  (Hmin)  ของไบนารี่ทรีที่มีจำนวน  N  โหนดคือ

Hmin= [ Log2  N]

เมื่อ N=1  จะได้  Hminเท่ากับ  0  เมื่อ  N=3  จะได้  Hminเท่ากับ 1 ที่ระดับ  1  มีโหนดเต็ม  เมื่อ  N  =  7  จะได้  Hminเท่ากับ  2  ที่ระดับ  2  มีโหนดเต็ม  ในกรณีโชคร้ายเมื่อไบนารี่ทรีมีโหนดลูกด้านเดียวทำให้มีความยาวดังในรูปที่  9.8  ก็จะได้ความสูงมากที่สุด ของไบนารี่ทรีที่มี N โหนดคือ

Hmax = N

รูปที่  9.8  ไบนารี่ทรีมีความสูงมากที่สุดเมื่อมี  N  โหนด

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

การสร้างไบนารี่

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

การใช่อาร์เรย์ป็นไบนารี่ทรี

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

(a)                                                                       (b)

รูปที่  9.9  ตัวอย่างการใช้อาร์เรย์สร้างไบนารี่ทรี

จากไบนารี่ทรีในส่วนบนสร้างให้อยู่ในรูปแบบของอาร์เรย์ได้เป็นในส่วนล่าง  ซึ่งการนำอาร์เรย์มาใช้เป็นไบนารี่ทรีเพื่อความสะดวกในการใช้งาน  คือ

1.       รูทโหนดจะอยู่ในตำแหน่งที่  0  ของอาร์เรย์เสมอ

2.       โหนดใด  ๆ  ของไบนารี่ทรีที่ไม่ใช่รูทในตำแหน่งที่  I  ของอาร์เรย์  สามารถถอยกลับไปยังโหนอพ่อในตำแหน่งที่  (i-1)/2  ของอาร์เรย์  ถ้ารูทโหนดกำหนดเป็น

1  โหนดพ่ออยู่ในตำแหน่งที่  I  mod  2

3.       โหนดใด  ๆ  ของไบนารี่ทรีในตำแหน่งที่  I  ของอาร์เรย์  สามารถวิ่งไปยังโหนดลูกได้

คือ

–          โหนดลูกด้านซ้ายอยู่ในตำแหน่งที่  2i+1  ถ้ารูทโหนดเป็น  1  จะอยู่ในตำแหน่งที่  2i

–          โหนดลูกด้านขวาอยู่ในตำแหน่งที่  2i+2  ถ้ารูทโหนดเป็น  1  จะอยู่ในตำแหน่งที่  2i+1  สามชิก  อย่างไรก็ตาม  เมื่อใช้เป็นไบนารี่ทรีที่ไม่สมบูรณ์จะทำให้เกิดตำแหน่งว่างดังในรูปที่  9.9  (b)  และใช้จำนวนสมาชิกมากกว่าเมื่อเปรียบเทียบกับรูป  (a)

การใช้ลิ้งลิสต์เป็นไบนารี่ทรี

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

(a)                                     (b)

รูปที่  9.10  โครงสร้างโหนดที่ใช้ในไบนารี่ทรี

จากไบนารี่ทรีในรูปที่  9.11  (a)  สร้างให้อยู่ในรูปแบบของริ้งลิสต์ได้เป็นในรูป  (b)

(a)                                                 (b)

รูปที่  9.11  ตัวอย่างไบนารี่ทรีและรูปแบบที่เป็นลิ้งค์ลิสต์

เมื่อสร้างไบนารี่ทรีขึ้นมาใช้งานและเพื่อความสะดวกและประสิทธิภาพจึงต้องมีการนำชุดปฏิบัติการมาช่วย  ถ้าให้ตัวแปร p  เป็นพ้อยเตอร์ที่ชี้ไปยังโหนด  N   ในไบนารี่ทรีจะได้ชุดปฏิบัติการดังนี้

Info(p)  เป็นการส่งค่าที่เก็บอยู่ในโหนดที่  p  ชี้กลับมาให้

Left(p)  เป็นการส่งโหนดลูกด้านซ้ายของโหนดที่  p  ชี้กลับมาให้

Right(p) เป็นการส่งโหนดลูกด้านขวาของโหนดที่  p  ชี้กลับมาให้

Father(p)  เป็นการส่งโหนดพ่อของโหนดที่  p ชี้กลับมาให้

ไบนารี่ทรีใช้เป็นโครงสร้างของข้อมูลแบบต่างๆ

 

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