ผลต่างระหว่างรุ่นของ "ต้นไม้ (โครงสร้างข้อมูล)"
The Mark-7032 (คุย | ส่วนร่วม) ไม้ยมกไม่ถูกหลัก และมีแทบทุกจุดที่แก้ไข |
|||
บรรทัด 10: | บรรทัด 10: | ||
| children = [[ต้นไม้ค้นหาแบบทวิภาค]] |
| children = [[ต้นไม้ค้นหาแบบทวิภาค]] |
||
}} |
}} |
||
'''ต้นไม้''' ({{Lang-en|Tree}}) เป็น [[แบบชนิดข้อมูลนามธรรม]] ประเภทหนึ่ง มีลักษณะการเรียงเป็นกิ่งก้านสาขาแตกแขนงออกไป จะไม่มีวงวน (loop) โยงในสมาชิกตัว |
'''ต้นไม้''' ({{Lang-en|Tree}}) เป็น [[แบบชนิดข้อมูลนามธรรม]] ประเภทหนึ่ง มีลักษณะการเรียงเป็นกิ่งก้านสาขาแตกแขนงออกไป จะไม่มีวงวน (loop) โยงในสมาชิกตัวต่าง ๆ |
||
โดยสมาชิกจะถูกเก็บไว้ใน[[ประเภทข้อมูล]]ชนิดวัตถุ (Object) หรือโครงสร้าง (Structure) เรียกว่า'''ปม (node) ''' ซึ่งจะมีตัวแปรซึ่งเก็บตัวชี้ (Pointer) ไปยังปม |
โดยสมาชิกจะถูกเก็บไว้ใน[[ประเภทข้อมูล]]ชนิดวัตถุ (Object) หรือโครงสร้าง (Structure) เรียกว่า'''ปม (node) ''' ซึ่งจะมีตัวแปรซึ่งเก็บตัวชี้ (Pointer) ไปยังปมอื่น ๆ ได้ |
||
ต้นไม้ถูกใช้ในการจัดการข้อมูลที่เปรียบเทียบกันได้ (comparable) อย่างรวดเร็วเช่น ตัวเลข หรือ การเรียงลำดับความสำคัญของข้อมูล เช่น การคำนวณที่มีวงเล็บ เป็นอาทิ |
ต้นไม้ถูกใช้ในการจัดการข้อมูลที่เปรียบเทียบกันได้ (comparable) อย่างรวดเร็วเช่น ตัวเลข หรือ การเรียงลำดับความสำคัญของข้อมูล เช่น การคำนวณที่มีวงเล็บ เป็นอาทิ |
||
บรรทัด 18: | บรรทัด 18: | ||
* '''ปม (node) ''' หมายถึงสิ่งที่เก็บสมาชิกของต้นไม้ |
* '''ปม (node) ''' หมายถึงสิ่งที่เก็บสมาชิกของต้นไม้ |
||
* '''ราก (root) ''' หมายถึงปมที่เราใช้เริ่มค้นหาภายในต้นไม้ ถ้าเป็น null หมายถึงต้นไม้ว่าง (empty tree) |
* '''ราก (root) ''' หมายถึงปมที่เราใช้เริ่มค้นหาภายในต้นไม้ ถ้าเป็น null หมายถึงต้นไม้ว่าง (empty tree) |
||
* '''ปมลูก (child node) ''' หมายถึงปมที่แตกออกมาจากของปมดังกล่าว ส่วนปมที่ปมดังกล่าวแตกมาเรียกว่า '''ปมพ่อ (parent node) ''' และเรียกปมพ่อของปมพ่อว่า '''ปมปู่ (grandparent node) ''' และเรียกตามลำดับการนับญาติฝ่ายพ่อไป |
* '''ปมลูก (child node) ''' หมายถึงปมที่แตกออกมาจากของปมดังกล่าว ส่วนปมที่ปมดังกล่าวแตกมาเรียกว่า '''ปมพ่อ (parent node) ''' และเรียกปมพ่อของปมพ่อว่า '''ปมปู่ (grandparent node) ''' และเรียกตามลำดับการนับญาติฝ่ายพ่อไปเรื่อย ๆ ส่วนปมลูกของปมลูกก็จะเป็น'''ปมหลาน (grandchild node) ''' ไปเรื่อย ๆ ตามลำดับการเรียกญาติฝ่ายลูก |
||
* ปมที่มีปมพ่อเป็นปมเดียวกันเรียกว่า '''ปมพี่น้อง (sibling node) ''' |
* ปมที่มีปมพ่อเป็นปมเดียวกันเรียกว่า '''ปมพี่น้อง (sibling node) ''' |
||
* ปมที่มี m ลูก เราจะเรียกว่า ''' ปมแบบ m ''' (m-type node) |
* ปมที่มี m ลูก เราจะเรียกว่า ''' ปมแบบ m ''' (m-type node) |
||
* '''ใบ (leaf node) ''' หมายถึงปมที่ไม่มีปมลูก |
* '''ใบ (leaf node) ''' หมายถึงปมที่ไม่มีปมลูก |
||
* การเขียนต้นไม้มักเขียนปมรากอยู่ข้างบน และเขียนแตกแขนงลงมาให้ปมใบอยู่ข้างล่าง |
* การเขียนต้นไม้มักเขียนปมรากอยู่ข้างบน และเขียนแตกแขนงลงมาให้ปมใบอยู่ข้างล่าง |
||
* '''ความลึกของปม (node depth) ''' หมายถึงจำนวนครั้งของความสัมพันธ์เชิงพ่อ-ลูก ระหว่าง ปมรากถึงปม |
* '''ความลึกของปม (node depth) ''' หมายถึงจำนวนครั้งของความสัมพันธ์เชิงพ่อ-ลูก ระหว่าง ปมรากถึงปมใด ๆ |
||
* '''ความสูง (tree height) ''' หมายถึงความลึกของใบที่ลึกที่สุด สำหรับต้นไม้ที่มีแต่รากจะสูง 0 และต้นไม้ว่างอาจตั้งได้ว่าสูง -1 |
* '''ความสูง (tree height) ''' หมายถึงความลึกของใบที่ลึกที่สุด สำหรับต้นไม้ที่มีแต่รากจะสูง 0 และต้นไม้ว่างอาจตั้งได้ว่าสูง -1 |
||
* '''ต้นไม้ย่อย (subtree) ''' หมายถึงต้นไม้ย่อยที่ใช้สมาชิกของต้นไม้ที่เราพิจารณา ไปเป็นรากส่งผลให้ ปมลูกปมหลานที่อยู่ใต้สมาชิกตัวนั้นกลายเป็นสมาชิกของต้นไม้ย่อยไปด้วย |
* '''ต้นไม้ย่อย (subtree) ''' หมายถึงต้นไม้ย่อยที่ใช้สมาชิกของต้นไม้ที่เราพิจารณา ไปเป็นรากส่งผลให้ ปมลูกปมหลานที่อยู่ใต้สมาชิกตัวนั้นกลายเป็นสมาชิกของต้นไม้ย่อยไปด้วย |
||
== ต้นไม้พิเศษ == |
== ต้นไม้พิเศษ == |
||
* '''ต้นไม้ค้นหา (search tree) '''หมายถึงต้นไม้ที่ตามปม |
* '''ต้นไม้ค้นหา (search tree) '''หมายถึงต้นไม้ที่ตามปมใด ๆ ต้นไม้ย่อยจะน้อยกว่า มากกว่า หรืออยู่ระหว่าง สมาชิกของปมนั้น ในลักษณะการเรียงลำดับ สำหรับต้นไม้ค้นหาที่มีปมแบบ m ใด ๆ ย่อมมีสมาชิกให้เปรียบเทียบ m-1 ตัวในปมนั้น เช่น ปมแบบสาม จะมีสมาชิกสองตัว |
||
* '''ต้นไม้ m ภาค (m-ary tree) ''' หมายถึงต้นไม้ที่ใช้แต่ปมแบบ m กล่าวคือมี m ลูก |
* '''ต้นไม้ m ภาค (m-ary tree) ''' หมายถึงต้นไม้ที่ใช้แต่ปมแบบ m กล่าวคือมี m ลูก |
||
* '''[[ต้นไม้แบบทวิภาค]] (binary tree) ''' หมายถึงต้นไม้ที่มีแต่ปมแบบสอง |
* '''[[ต้นไม้แบบทวิภาค]] (binary tree) ''' หมายถึงต้นไม้ที่มีแต่ปมแบบสอง |
||
* '''[[ต้นไม้ค้นหาแบบทวิภาค]] (binary search tree) ''' หมายถึงต้นไม้ที่มีแต่ปมแบบสอง โดยต้นไม้ย่อยของลูกซ้าย (left child subtree) จะมีค่าน้อยกว่าปม |
* '''[[ต้นไม้ค้นหาแบบทวิภาค]] (binary search tree) ''' หมายถึงต้นไม้ที่มีแต่ปมแบบสอง โดยต้นไม้ย่อยของลูกซ้าย (left child subtree) จะมีค่าน้อยกว่าปมนั้น ๆ และต้นไม้ย่อยของลูกขวา (right child subtree) จะมีค่ามากกว่าปมนั้น ๆ |
||
* '''ต้นไม้ประกันการทำงาน''' หมายถึงต้นไม้ที่ประกันความเร็วการทำงานเป็น [[สัญกรณ์โอใหญ่|O (log n)]] |
* '''ต้นไม้ประกันการทำงาน''' หมายถึงต้นไม้ที่ประกันความเร็วการทำงานเป็น [[สัญกรณ์โอใหญ่|O (log n)]] |
||
* '''ต้นไม้ประกันความสูง''' หมายถึงต้นไม้ที่ประกันความสูงเป็น [[สัญกรณ์โอใหญ่|O (log n)]] ต้นไม้ประกันความสูงย่อมเป็นต้นไม้ประกันการทำงานไปด้วย |
* '''ต้นไม้ประกันความสูง''' หมายถึงต้นไม้ที่ประกันความสูงเป็น [[สัญกรณ์โอใหญ่|O (log n)]] ต้นไม้ประกันความสูงย่อมเป็นต้นไม้ประกันการทำงานไปด้วย |
||
* '''ต้นไม้ได้ดุล''' (balanced tree) หมายถึงต้นไม้ที่มีความสูงต่ำสุดเท่าที่เป็นไปได้สำหรับชุดข้อมูล |
* '''ต้นไม้ได้ดุล''' (balanced tree) หมายถึงต้นไม้ที่มีความสูงต่ำสุดเท่าที่เป็นไปได้สำหรับชุดข้อมูลใด ๆ ต้นไม้ได้ดุลย่อมเป็นต้นไม้ที่ประกันความสูงไปด้วย |
||
* '''ต้นไม้เติมเต็ม''' (completed tree) หมายถึงต้นไม้ที่ปม |
* '''ต้นไม้เติมเต็ม''' (completed tree) หมายถึงต้นไม้ที่ปมใด ๆ สามารถมีลูกได้ก็ต่อเมื่อปมพี่น้องทางซ้ายมีลูกเท่านั้น ต้นไม้เติมเต็มย่อมเป็นต้นไม้ได้ดุลไปด้วย |
||
* '''[[ฮีป]]''' (heap) หมายถึงต้นไม้ที่เมื่อพิจารณาในต้นไม้ย่อย |
* '''[[ฮีป]]''' (heap) หมายถึงต้นไม้ที่เมื่อพิจารณาในต้นไม้ย่อยใด ๆ ในต้นไม้ รากจะมีความสำคัญ (priority) มากที่สุด |
||
== จุดเด่นของต้นไม้ == |
== จุดเด่นของต้นไม้ == |
||
'''ต้นไม้'''เป็นโครงสร้างที่เน้นข้อมูลที่เปรียบเทียบกันได้ (comparable) เช่นต้นไม้ค้นหา หรือมีลำดับความสำคัญเป็นขั้นตอน เช่นฮีป มักใช้ในการจัดการค้นหาอย่างรวดเร็วเป็น [[สัญกรณ์โอใหญ่|O (log n)]] หรือการจัดลำดับความสำคัญ เช่นการจัด[[นิพจน์]] ซึ่งเรียงลำดับการทำงานโดยต้นไม้นิพจน์ |
'''ต้นไม้'''เป็นโครงสร้างที่เน้นข้อมูลที่เปรียบเทียบกันได้ (comparable) เช่นต้นไม้ค้นหา หรือมีลำดับความสำคัญเป็นขั้นตอน เช่นฮีป มักใช้ในการจัดการค้นหาอย่างรวดเร็วเป็น [[สัญกรณ์โอใหญ่|O (log n)]] หรือการจัดลำดับความสำคัญ เช่นการจัด[[นิพจน์]] ซึ่งเรียงลำดับการทำงานโดยต้นไม้นิพจน์ |
||
บรรทัด 49: | บรรทัด 49: | ||
ต้นไม้เน้นการทำงานอย่างรวดเร็วโดยการตัดทอนกิ่งที่ไม่สนใจ เช่นต้นไม้ค้นหาแบบทวิภาคที่สามารถไล่ไปตามกิ่งของต้นไม้ ทำให้อย่างมากที่สุด การค้นหาก็จะผ่านจำนวนข้อมูลเท่ากับความสูงของต้นไม้ ซึ่งความสูงของต้นไม้ที่น้อยที่สุดเป็น [[สัญกรณ์โอใหญ่|O (log n)]] จึงทำให้บริการที่เร็วที่สุดเป็น [[สัญกรณ์โอใหญ่|O (log n)]] อย่างไรก็ตาม หากจัดการไม่เหมาะสม ความสูงของต้นไม้อาจยืดเป็น [[สัญกรณ์โอใหญ่|O (n)]]ได้ส่งผลให้บริการช้า จึงต้องมีการจำกัดความสูงและคงสมดุลของต้นไม้ให้เหมาะสม |
ต้นไม้เน้นการทำงานอย่างรวดเร็วโดยการตัดทอนกิ่งที่ไม่สนใจ เช่นต้นไม้ค้นหาแบบทวิภาคที่สามารถไล่ไปตามกิ่งของต้นไม้ ทำให้อย่างมากที่สุด การค้นหาก็จะผ่านจำนวนข้อมูลเท่ากับความสูงของต้นไม้ ซึ่งความสูงของต้นไม้ที่น้อยที่สุดเป็น [[สัญกรณ์โอใหญ่|O (log n)]] จึงทำให้บริการที่เร็วที่สุดเป็น [[สัญกรณ์โอใหญ่|O (log n)]] อย่างไรก็ตาม หากจัดการไม่เหมาะสม ความสูงของต้นไม้อาจยืดเป็น [[สัญกรณ์โอใหญ่|O (n)]]ได้ส่งผลให้บริการช้า จึงต้องมีการจำกัดความสูงและคงสมดุลของต้นไม้ให้เหมาะสม |
||
== การแวะผ่านต้นไม้ == |
== การแวะผ่านต้นไม้ == |
||
การแวะผ่านต้นไม้ (tree traversal) หมายถึงการทำงานผ่านต้นไม้ |
การแวะผ่านต้นไม้ (tree traversal) หมายถึงการทำงานผ่านต้นไม้ใด ๆ เช่นการไล่พิมพ์สมาชิก การสร้างแถวลำดับเก็บทุกสมาชิกของต้นไม้ ฯลฯ ที่จำเป็นต้องผ่านสมาชิกทุก ๆ ตัวในต้นไม้ ซึ่งการเรียงลำดับการแวะผ่านต้นไม้จำเป็นต้องใช้[[ความสัมพันธ์เวียนเกิด]] การแวะผ่านต้นไม้มีสามแบบดังต่อไปนี้ |
||
* '''การแวะผ่านก่อนลำดับ (preorder traversal) ''' หมายถึงการแวะผ่านโดยให้ความสำคัญรากก่อนแล้วจึงแวะผ่านต้นไม้ย่อยของลูกจากซ้ายไปขวา |
* '''การแวะผ่านก่อนลำดับ (preorder traversal) ''' หมายถึงการแวะผ่านโดยให้ความสำคัญรากก่อนแล้วจึงแวะผ่านต้นไม้ย่อยของลูกจากซ้ายไปขวา |
||
* '''การแวะผ่านตามลำดับ (inorder traversal) ''' หมายถึงการแวะผ่านโดยให้ความสำคัญต้นไม้ย่อยของลูกซ้ายก่อน และกลับมาแวะที่ราก แล้วจึงแวะผ่านต้นไม้ย่อยทางขวา และกลับมาแวะที่ราก เช่นนี้ไป |
* '''การแวะผ่านตามลำดับ (inorder traversal) ''' หมายถึงการแวะผ่านโดยให้ความสำคัญต้นไม้ย่อยของลูกซ้ายก่อน และกลับมาแวะที่ราก แล้วจึงแวะผ่านต้นไม้ย่อยทางขวา และกลับมาแวะที่ราก เช่นนี้ไปเรื่อย ๆสลับกันไป จนถึงต้นไม้ย่อยของลูกสุดท้าย |
||
* '''การแวะผ่านหลังลำดับ (postorder traversal) ''' หมายถึงการแวะผ่านต้นไม้ย่อยของลูกเรียงจากซ้ายไปขวา แล้วจึงแวะผ่านรากทีหลัง |
* '''การแวะผ่านหลังลำดับ (postorder traversal) ''' หมายถึงการแวะผ่านต้นไม้ย่อยของลูกเรียงจากซ้ายไปขวา แล้วจึงแวะผ่านรากทีหลัง |
||
== โครงสร้างข้อมูลที่เป็นต้นไม้ == |
== โครงสร้างข้อมูลที่เป็นต้นไม้ == |
รุ่นแก้ไขเมื่อ 15:13, 28 สิงหาคม 2564
ต้นไม้ | |
---|---|
การเรียงตัวของต้นไม้ในมโนทัศน์ของโครงสร้างข้อมูล | |
ความสำคัญของลำดับ | เรียงจากน้อยไปมาก |
การซ้ำกันของสมาชิก | ไม่อนุญาตให้ซ้ำกัน |
เวลาที่ใช้ในการเข้าถึง | การแวะผ่านต้นไม้ (tree traversal) |
โครงสร้างที่นำไปใช้ | ต้นไม้ค้นหาแบบทวิภาค |
ต้นไม้ (อังกฤษ: Tree) เป็น แบบชนิดข้อมูลนามธรรม ประเภทหนึ่ง มีลักษณะการเรียงเป็นกิ่งก้านสาขาแตกแขนงออกไป จะไม่มีวงวน (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 ภาคจะมีความสูงต่ำสุดที่เป็นไปได้คือ
บริการที่มักจะมี
- การเพิ่ม ลบ และค้นสมาชิก
- การหาตัวมากที่สุด หรือน้อยที่สุด
- การไล่สมาชิกตามการแวะผ่านต้นไม้ (tree traversal)
ความเร็วที่ใช้ในการทำงาน
ต้นไม้เน้นการทำงานอย่างรวดเร็วโดยการตัดทอนกิ่งที่ไม่สนใจ เช่นต้นไม้ค้นหาแบบทวิภาคที่สามารถไล่ไปตามกิ่งของต้นไม้ ทำให้อย่างมากที่สุด การค้นหาก็จะผ่านจำนวนข้อมูลเท่ากับความสูงของต้นไม้ ซึ่งความสูงของต้นไม้ที่น้อยที่สุดเป็น O (log n) จึงทำให้บริการที่เร็วที่สุดเป็น O (log n) อย่างไรก็ตาม หากจัดการไม่เหมาะสม ความสูงของต้นไม้อาจยืดเป็น O (n)ได้ส่งผลให้บริการช้า จึงต้องมีการจำกัดความสูงและคงสมดุลของต้นไม้ให้เหมาะสม
การแวะผ่านต้นไม้
การแวะผ่านต้นไม้ (tree traversal) หมายถึงการทำงานผ่านต้นไม้ใด ๆ เช่นการไล่พิมพ์สมาชิก การสร้างแถวลำดับเก็บทุกสมาชิกของต้นไม้ ฯลฯ ที่จำเป็นต้องผ่านสมาชิกทุก ๆ ตัวในต้นไม้ ซึ่งการเรียงลำดับการแวะผ่านต้นไม้จำเป็นต้องใช้ความสัมพันธ์เวียนเกิด การแวะผ่านต้นไม้มีสามแบบดังต่อไปนี้
- การแวะผ่านก่อนลำดับ (preorder traversal) หมายถึงการแวะผ่านโดยให้ความสำคัญรากก่อนแล้วจึงแวะผ่านต้นไม้ย่อยของลูกจากซ้ายไปขวา
- การแวะผ่านตามลำดับ (inorder traversal) หมายถึงการแวะผ่านโดยให้ความสำคัญต้นไม้ย่อยของลูกซ้ายก่อน และกลับมาแวะที่ราก แล้วจึงแวะผ่านต้นไม้ย่อยทางขวา และกลับมาแวะที่ราก เช่นนี้ไปเรื่อย ๆสลับกันไป จนถึงต้นไม้ย่อยของลูกสุดท้าย
- การแวะผ่านหลังลำดับ (postorder traversal) หมายถึงการแวะผ่านต้นไม้ย่อยของลูกเรียงจากซ้ายไปขวา แล้วจึงแวะผ่านรากทีหลัง