ต้นไม้ (โครงสร้างข้อมูล)

**ต้นไม้** () เป็น แบบชนิดข้อมูลนามธรรม ประเภทหนึ่ง มีลักษณะการเรียงเป็นกิ่งก้านสาขาแตกแขนงออกไป จะไม่มีวงวน (loop) โยงในสมาชิกตัวต่าง ๆ 
โดยสมาชิกจะถูกเก็บไว้ในประเภทข้อมูลชนิดวัตถุ (Object) หรือโครงสร้าง (Structure) เรียกว่า**ปม (node) ** ซึ่งจะมีตัวแปรซึ่งเก็บตัวชี้ (Pointer) ไปยังปมอื่น ๆ ได้

ต้นไม้ถูกใช้ในการจัดการข้อมูลที่เปรียบเทียบกันได้ (comparable) อย่างรวดเร็วเช่น ตัวเลข หรือ การเรียงลำดับความสำคัญของข้อมูล เช่น การคำนวณที่มีวงเล็บ เป็นอาทิ

## ส่วนประกอบของต้นไม้
* **ปม (node) ** หมายถึงสิ่งที่เก็บสมาชิกของต้นไม้
* **ราก (root) ** หมายถึงปมที่เราใช้เริ่มค้นหาภายในต้นไม้ ถ้าเป็น null หมายถึงต้นไม้ว่าง (empty tree)
* **ปมลูก (child node) ** หมายถึงปมที่แตกออกมาจากของปมดังกล่าว ส่วนปมที่ปมดังกล่าวแตกมาเรียกว่า **ปมพ่อ (parent node) ** และเรียกปมพ่อของปมพ่อว่า **ปมปู่ (grandparent node) ** และเรียกตามลำดับการนับญาติฝ่ายพ่อไปเรื่อย ๆ ส่วนปมลูกของปมลูกก็จะเป็น**ปมหลาน (grandchild node) ** ไปเรื่อย ๆ ตามลำดับการเรียกญาติฝ่ายลูก
* ปมที่มีปมพ่อเป็นปมเดียวกันเรียกว่า **ปมพี่น้อง (sibling node) **
* ปมที่มี m ลูก เราจะเรียกว่า ** ปมแบบ m ** (m-type node)
* **ใบ (leaf node) ** หมายถึงปมที่ไม่มีปมลูก
* การเขียนต้นไม้มักเขียนปมรากอยู่ข้างบน และเขียนแตกแขนงลงมาให้ปมใบอยู่ข้างล่าง
* **ความลึกของปม (node depth) ** หมายถึงจำนวนครั้งของความสัมพันธ์เชิงพ่อ-ลูก ระหว่าง ปมรากถึงปมใด ๆ
* **ความสูง (tree height) ** หมายถึงความลึกของใบที่ลึกที่สุด สำหรับต้นไม้ที่มีแต่รากจะสูง 0 และต้นไม้ว่างอาจตั้งได้ว่าสูง -1
* **ต้นไม้ย่อย (subtree) ** หมายถึงต้นไม้ย่อยที่ใช้สมาชิกของต้นไม้ที่เราพิจารณา ไปเป็นรากส่งผลให้ ปมลูกปมหลานที่อยู่ใต้สมาชิกตัวนั้นกลายเป็นสมาชิกของต้นไม้ย่อยไปด้วย

## ต้นไม้พิเศษ
* **ต้นไม้ค้นหา (search tree) **หมายถึงต้นไม้ที่ตามปมใด ๆ ต้นไม้ย่อยจะน้อยกว่า มากกว่า หรืออยู่ระหว่าง สมาชิกของปมนั้น ในลักษณะการเรียงลำดับ สำหรับต้นไม้ค้นหาที่มีปมแบบ m ใด ๆ ย่อมมีสมาชิกให้เปรียบเทียบ m-1 ตัวในปมนั้น เช่น ปมแบบสาม จะมีสมาชิกสองตัว
* **ต้นไม้ m ภาค (m-ary tree) ** หมายถึงต้นไม้ที่ใช้แต่ปมแบบ m กล่าวคือมี m ลูก
* **[[ต้นไม้แบบทวิภาค]] (binary tree) ** หมายถึงต้นไม้ที่มีแต่ปมแบบสอง
* **[[ต้นไม้ค้นหาแบบทวิภาค]] (binary search tree) ** หมายถึงต้นไม้ที่มีแต่ปมแบบสอง โดยต้นไม้ย่อยของลูกซ้าย (left child subtree) จะมีค่าน้อยกว่าปมนั้น ๆ และต้นไม้ย่อยของลูกขวา (right child subtree) จะมีค่ามากกว่าปมนั้น ๆ
* **ต้นไม้ประกันการทำงาน** หมายถึงต้นไม้ที่ประกันความเร็วการทำงานเป็น O (log n)
* **ต้นไม้ประกันความสูง** หมายถึงต้นไม้ที่ประกันความสูงเป็น O (log n) ต้นไม้ประกันความสูงย่อมเป็นต้นไม้ประกันการทำงานไปด้วย 
* **ต้นไม้ได้ดุล** (balanced tree) หมายถึงต้นไม้ที่มีความสูงต่ำสุดเท่าที่เป็นไปได้สำหรับชุดข้อมูลใด ๆ ต้นไม้ได้ดุลย่อมเป็นต้นไม้ที่ประกันความสูงไปด้วย
* **ต้นไม้เติมเต็ม** (completed tree) หมายถึงต้นไม้ที่ปมใด ๆ สามารถมีลูกได้ก็ต่อเมื่อปมพี่น้องทางซ้ายมีลูกเท่านั้น ต้นไม้เติมเต็มย่อมเป็นต้นไม้ได้ดุลไปด้วย
* **[[ฮีป (โครงสร้างข้อมูล)|ฮีป]]** (heap) หมายถึงต้นไม้ที่เมื่อพิจารณาในต้นไม้ย่อยใด ๆ ในต้นไม้ รากจะมีความสำคัญ (priority) มากที่สุด
## จุดเด่นของต้นไม้
**ต้นไม้**เป็นโครงสร้างที่เน้นข้อมูลที่เปรียบเทียบกันได้ (comparable) เช่นต้นไม้ค้นหา หรือมีลำดับความสำคัญเป็นขั้นตอน เช่นฮีป มักใช้ในการจัดการค้นหาอย่างรวดเร็วเป็น O (log n) หรือการจัดลำดับความสำคัญ เช่นการจัดนิพจน์ ซึ่งเรียงลำดับการทำงานโดยต้นไม้นิพจน์
## สมบัติของต้นไม้ในทางคณิตศาสตร์ที่มักใช้

* ต้นไม้ m ภาคจะมีความสูงต่ำสุดที่เป็นไปได้คือ  \lfloor log_m n \rfloor 
## บริการที่มักจะมี
* การเพิ่ม ลบ และค้นสมาชิก
* การหาตัวมากที่สุด หรือน้อยที่สุด
* การไล่สมาชิกตามการแวะผ่านต้นไม้ (tree traversal)
## ความเร็วที่ใช้ในการทำงาน
ต้นไม้เน้นการทำงานอย่างรวดเร็วโดยการตัดทอนกิ่งที่ไม่สนใจ เช่นต้นไม้ค้นหาแบบทวิภาคที่สามารถไล่ไปตามกิ่งของต้นไม้ ทำให้อย่างมากที่สุด การค้นหาก็จะผ่านจำนวนข้อมูลเท่ากับความสูงของต้นไม้ ซึ่งความสูงของต้นไม้ที่น้อยที่สุดเป็น O (log n) จึงทำให้บริการที่เร็วที่สุดเป็น O (log n) อย่างไรก็ตาม หากจัดการไม่เหมาะสม ความสูงของต้นไม้อาจยืดเป็น O (n)ได้ส่งผลให้บริการช้า จึงต้องมีการจำกัดความสูงและคงสมดุลของต้นไม้ให้เหมาะสม
## การแวะผ่านต้นไม้
การแวะผ่านต้นไม้ (tree traversal) หมายถึงการทำงานผ่านต้นไม้ใด ๆ เช่นการไล่พิมพ์สมาชิก การสร้างแถวลำดับเก็บทุกสมาชิกของต้นไม้ ฯลฯ ที่จำเป็นต้องผ่านสมาชิกทุก ๆ ตัวในต้นไม้ ซึ่งการเรียงลำดับการแวะผ่านต้นไม้จำเป็นต้องใช้ความสัมพันธ์เวียนเกิด การแวะผ่านต้นไม้มีสามแบบดังต่อไปนี้
* **การแวะผ่านก่อนลำดับ (preorder traversal) ** หมายถึงการแวะผ่านโดยให้ความสำคัญรากก่อนแล้วจึงแวะผ่านต้นไม้ย่อยของลูกจากซ้ายไปขวา
* **การแวะผ่านตามลำดับ (inorder traversal) ** หมายถึงการแวะผ่านโดยให้ความสำคัญต้นไม้ย่อยของลูกซ้ายก่อน และกลับมาแวะที่ราก แล้วจึงแวะผ่านต้นไม้ย่อยทางขวา และกลับมาแวะที่ราก เช่นนี้ไปเรื่อย ๆสลับกันไป จนถึงต้นไม้ย่อยของลูกสุดท้าย
* **การแวะผ่านหลังลำดับ (postorder traversal) ** หมายถึงการแวะผ่านต้นไม้ย่อยของลูกเรียงจากซ้ายไปขวา แล้วจึงแวะผ่านรากทีหลัง
## โครงสร้างข้อมูลที่เป็นต้นไม้
* ต้นไม้ค้นหาแบบทวิภาค

## ดูเพิ่ม
* ต้นไม้ (ทฤษฎีกราฟ)

หมวดหมู่:แบบชนิดข้อมูลนามธรรม

หมวดหมู่:ชนิดข้อมูล