Data Structure: Tree … มาปลูกต้นไม้กันมั้ย?

โครงสร้างข้อมูลมีหลายประเภท เช่น Array Linked-List Stack-Queue แต่ละอย่างก็มีข้อดีข้อเสียต่างกัน ซึ่งสำหรับคนที่เคยใช้ Array และรู้วิธีคิดค่า big O (อ่านว่า "บิ๊ก-โอ" .. เป็นสัญลักษณ์ที่เอาไว้บอกว่าโค้ดที่เราเขียนขึ้นมาน่ะมันทำงานได้ดีแค่ไหน ยิ่งน้อยยิ่งดีหมายความว่าทำงานเสร็จเร็ว) จะรู้ว่าฟังก์ชั่นพื้นฐานของ Data Structure 3 อย่างคือ Insert-Find-Delete นั้น สำหรับ Array มันทำงานได้ค่อนข้างช้าด้วย O(n)

ถ้าคุณเถียงว่า O(n) มันก็ไม่ได้ช้ามากไม่ใช่เหรอ .. ใช่! มันไม่ช้ามากจนรับไม่ได้ แต่ถ้ามันมีวิธีที่มันเร็วกว่านี้จะดีกว่าไหม

นัก คอมพิวเตอร์ (หรือจะรวมพวกนักวิทยาศาสตร์ นักคณิศาสตร์เข้าไปด้วยก็ได้นะ) ในสมัยก่อนเขาคิดมาให้แล้วว่านี่เป็นโครงสร้างการเก็บข้อมูลที่เร็วกว่า Array ในทุกด้านเลยล่ะ !!

ป.ล.เร็วกว่า ไม่ได้หมายความว่ามันใช้ง่ายกว่านะ

งั้นมาดูกันว่า Tree มันเป็นยังไง...

เอ่อ ความจริงมันก็คือโครงสร้างที่ตั้งชื่อตามต้นไม้ในโลกจริงนั่นแหละ (ความจริงผู้เขียนไม่เห็นคิดว่ามันจะเหมือนต้นไม้เท่าไหร่เลย เหมือนพีรามิดมากกว่าอีก)

เพียงแต่ว่า เราต้องเอาต้นไม้เนี้ยมากลับหัวก่อน ซึ่งก็จะได้แบบนี้

สรุปก็คือ โครงสร้างแบบ Tree นั้นก็คือการเอา Node มาเชื่อมต่อกัน (คล้ายๆ กับ Linked-List เลยใช่มั้ยล่ะ?) โดย Node แต่ล่ะตัวจะเชื่อมไปยัง Node ถัดๆ ไปได้หลายตัว และเชื่อมแบบเป็นชั้นๆ ลงไปเรื่อยๆ

โครงสร้างของ Tree

คอนเซ็ปของ Tree ก็แค่ Node บนสุดเราจะเรียกว่า root ซึ่งเป็นคล้ายๆ หัวของ Tree ต้นนั้น

สำหรับ Node แต่ละตัว (รวมทั้ง root ด้วย) สามารถมี Node ลูกได้ ซึ่งตัวมันเองจะเรียกว่า "parent" และเรียกลูกของมันทุกตัวรวมๆ ว่า "child"

ดัง นั้น Node แต่ละตัวสามารถเป็นได้ทั้ง parent และ child เช่นตามรูปข้างบน ถ้าเราดูที่ Node B มันคือ child (ถ้าเจาะจงให้ละเอียดกว่านี้คือ child ทางซ้าย หรือ left-child นั่นเอง) ของ Node A ... แต่กลับกัน ถ้า Node B มี Node ลูกต่อไปอีก มันจะเปลี่ยนสถานะไปเป็น parent ทันที

ข้อ กำหนดของ Tree ไม่ตายตัวว่าจะมีจำนวน child ต่อแต่ล่ะ Node เท่าไหร่ แต่ก็มี Tree ที่กำหนดไว้เหมือนกันว่าจำนวนลูกต้องมีเท่าไหร่เช่น Binary Tree

Binary Tree

เป็น Tree ประเภทที่ใช้บ่อยและเป็นที่นิยมมาก ... ไบนารี หรือที่แปลว่า "2" นั่นแปลว่า Tree ประเภทนี้จะมี Node ลูกได้แค่ 2 ตัวเป็นอย่างมากเท่านั้น แต่ไม่จำเป็นต้องมี 2 ตัวตลอดนะ มีแค่ตัวเดียวหรือไม่มีเลยก็ได้ไม่ผิดกฎ

แต่กฎสำคัญของ binary tree นั้นคือการที่มันจะเรียงลำดับข้อมูลใน Tree เอง

Node ทางซ้าย จะต้องมีค่าน้อยกว่า Node ทางขวาเสมอ เช่น เรามี Node A B C แบบรูปข้างบน

ค่าที่แต่ละ Node เก็บอยู่จะต้องเรียงแบบ B < A < C เท่านั้น

สำหรับ เรื่อง Tree นั้นยังมีอีก (เยอะ!) มาก แต่วันนี้เอาไว้แค่นี้ก่อน เดี๋ยวจะมาต่อเรื่อง การ Search ข้อมูลที่เก็บอยู่ใน Tree ในรูปแบบ BFS และ DFS