ทำความรู้จักกับโครงสร้างข้อมูลแบบต้นไม้ (Tree)

โครงสร้างข้อมูลแบบต้นไม้ (Tree) เป็นโครงสร้างข้อมูลที่สามารถนำไปปรับใช้กับการค้นหาข้อมูลแบบ Binary Search Tree และการจัดเรียงข้อมูล (Sorting) ได้ ซึ่งเป็นแนวคิดนักวิทยาการคอมพิวเตอร์เลียนแบบมาจากต้นไม้ในชีวิตจริง

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

เป็นการนำข้อมูลในอาเรย์ (Array) มาจัดอยู่ในแนวคิดของ Tree ดังตัวอย่างนี้ ซึ่งเมื่อเราต้องการจะอ้างอิงไปหา node ต่างๆ จะมีชื่อเรียกเฉพาะ เช่น node บนสุดเรียกว่า "Root Node" รองลงมาเรียกว่า Siblings หรือ Parents Node และ node ที่อยู่ปลายสุดของต้นไม้เรียกว่า Leaf Nodes หรือ Child Nodes โดยจะเรียกเส้นที่เชื่อมต่อ nodes ต่างๆ ว่า Edges

Binary Tree

หมายถึง โครงสร้างต้นไม้ที่จะมี Sibling Nodes ได้ไม่เกิน 2 Nodes (รากศัพท์ Bi หมายถึง สอง)

การแปลง Tree เป็น Binary Tree

การแปลง Tree เป็น Binary Tree มีวิธีการอยู่หลายวิธีการ แต่ในบทความนี้ผมจะแนะนำวิธีการที่ผมได้เรียนมาในวิชาโครงสร้างข้อมูล ซึ่งมีวิธีการคือ การตัด Edges ของทุกชั้นออกให้เหลือแค่เพียง Edges ด้านซ้ายสุด โดยจะสร้างเส้นเชื่อมต่อใหม่โดยเชื่อมต่อ nodes ในแต่ละชั้นใหม่ และบิดเส้นดังกล่าวไปทางซ้ายประมาณ 45 องศา จะได้โครงสร้างต้นไม้ใหม่ทีเป็น Binary Tree

Tree Traversal การท่องไปในต้นไม้

การท่องไปในต้นไม้ (Tree Traversal) เป็นการเรียงลำดับ Nodes ต่างๆ ตามลำดับ ซึ่งจะมีอยู่ 3 แบบ ได้แก่ Pre-Order, In-Order และ Post-Order มีรายละเอียดดังนี้

Pre-Order เป็นการท่องโดยจะเรียงลำดับ Root มาไว้ข้างหน้า ตามด้วย Siblings ซ้าย และ ขวา โดยหาก Sibling มี Leaf Node ก็จะถือว่าตัวมันเป็น Root และต้องเรียง Leaf Node เข้ามาด้วย จากตัวอย่างเมื่อเรียงลำดับตาม pre-order ได้ ABD มาจนถึง E ก็จะต้องตามด้วย  Leaf Node ของ E อย่าง H ซึ่งก็บังเอิญว่า ตัวของ H เองก็เป็น Sibling Node เช่นกัน หลัง H จึงต้องใส่ I ตามไปด้วย จึงจะสามารถไปเรียงลำดับทางด้านขวาต่อได้

In-Order เป็นการท่องโดยจะเรียงลำดับ Root ไว้ตรงกลางระหว่าง ซ้ายและขวา เวลาเรียงตามตัวอย่างในภาพ จึงจะเรียงจาก DB และเมื่อถึง E จะเห็นว่า E เป็น Sibling Node ที่มี Child Nodes อยู่ และ H ก็มี Child Node เช่นกัน จึงต้องเรียง จาก nodes นอกสุดซึ่งคือ I เข้ามา ตามด้วย H ถึงจะสามารถนำ E มาใส่ตามลำดับได้

Post-Order เป็นการท่องโดยเชียงลำดับ Root ไว้ท้ายสุด ตามตัวอย่างก็จะเรียง D มาก่อน ตามด้วย H แต่บังเอิญว่า H มี Child Node จึงต้องเรียง I มาก่อน ตามด้วย H ได้เป็น DIHE และ B จากนั้นจะไปเรียงทางขวาต่อโดยเรียง F (ซ้าย) G (ขวา) และ C ได้เป็น FGC เมื่อได้สองข้างแล้วเอามารวมกันก็จะได้ DIHEFGC ตามด้วย Root นั้นก็คือ A

Binary Search Tree หรือ Sorted Binary Tree

เป็นหนึ่งในวิธีการจัดเรียงโครงสร้างของ Binary Tree เรียกว่า Sorted Binary Tree หรือ Binary Search Tree ให้โครงสร้างต้นไม้หนึ่ง สามารถทำการค้นหาข้อมูลภายใน ที่มีประสิทธิภาพเท่ากับ O(log n) ในกรณีแย่สุดอาจมีประสิทธิภาพเท่ากับ O(n) ซึ่ง Binary Search Tree นั้นถูกคิดค้นเมื่อปี 1960 โดย P.F. Windley, A.D. Booth, A.J.T. Colin, และ T.N. Hibbard 

โดยจะมีวิธีการจัดเรียงข้อมูลใน Binary Tree ก่อน จึงจะสามารถนำไปค้นหาได้ มีวิธีการดังนี้

จากในภาพตัวอย่าง node ที่เป็น root มีค่าเท่ากับ 10 หากมีค่าที่ป้อนเข้ามาใหม่ โดยค่านั้นมีค่า น้อยกว่า root ข้อมูลจะไปอยู่ทางซ้ายของ root และหากมีค่า มากกว่า root จะไปอยู่ทางขวาของ root ดังนั้น

1. ค่าที่ป้อนเข้ามาเท่ากับ 7 ก็จะไปอยู่ทางซ้ายของ 10
2. ค่าที่ป้อนเข้ามาใหม่เท่ากับ 17 ก็จะไปอยู่ทางขวาของ 10
3. ค่าที่ป้อนเข้ามาใหม่เท่ากับ 4 ก็จะไปอยู่ทางซ้ายของ 10 ซึ่งมี 7 อยู่ จึงต้องทำเงื่อนไขเดิมเช็คกับ 7 ได้ผลน้อยกว่า 7 จึงไปอยู่ทางซ้ายของ 7
4. ค่าที่ป้อนเข้ามาใหม่เท่ากับ 8 ก็จะไปอยู่ทางซ้ายของ 10 ซึ่งมี 7 อยู่ เมื่อเทียบแล้วมากกว่า 7 จึงไปอยู่ทางขวาของ 7
5. ค่าที่ป้อนเข้ามาใหม่เท่ากับ 17 ก็จะไปอยู่ทางขวาของ 10
6. ค่าที่ป้อนเข้ามาใหม่เท่ากับ 15 ก็จะไปอยู่ทางขวาของ 10 ซึ่งมี 17 อยู่ เมื่อเทียบแล้วน้อยกว่า 17 จึงไปอยู่ทางซ้ายของ 17
7. ค่าที่ป้อนเข้ามาใหม่เท่ากับ 20 ก็จะไปอยู่ทางขวาของ 10 ซึ่งมี 17 อยู่ เมื่อเทียบแล้วมากกว่า 17 จึงไปอยู่ทางขวาของ 17

เมื่อต้องการจะค้นหาข้อมูลภายใน Binary Search Tree ให้นำค่าที่ต้องการจะค้นหา เช็คตามเงื่อนไขเดิมตั้งแต่ Root ลงมา ตัวอย่างหากต้องการเช็คว่ามีตัวเลข 8 อยู่หรือไม่ จะมีขั้นตอนดังนี้

1. 8 เมื่อเทียบกับ 10 พบว่า 8 มีค่าน้อยกว่า 10 จึงไปเช็คต่อในทางซ้ายของ 10
2. 8 เมื่อเทียบกับ 7 พบว่า 8 มีค่ามากกว่า 7 จึงไปเช็คต่อในทางขวาของ 7
3. 8 เมื่อเทียบกับ 8 พบว่า 8 มีค่าเท่ากับ 8 จึงพบข้อมูล

การค้นหาตัวเลข 8 ใช้เวลา 3 รอบ หากต้องการเช็คว่ามีตัวเลข 19 อยู่หรือไม่ จะมีขั้นตอนดังนี้

1. 19 เมื่อเทียบกับ 10 พบว่า 19 มีค่ามากกว่า 10 จึงไปเช็คต่อในทางขวาของ 10
2. 19 เมื่อเทียบกับ 17 พบว่า 19 มีค่ามากกว่า 17 จึงไปเช็คต่อในทางขวาของ 17
3. 19 เมื่อเทียบกับ 20 พบว่า 19 น้อยกว่า 20 แต่เช็คครบทุกชั้นแล้ว จึงเท่ากับไม่พบข้อมูล