บทที่ 26 tree BST และ heap
จบบทนี้ น้องจะอ่านต้นไม้จากข้อมูลเข้าได้ทุกรูปแบบที่โจทย์ใช้บ่อย ทั้งพ่อของแต่ละโหนดและลูกซ้ายลูกขวา ท่องต้นไม้ได้ทั้ง preorder inorder postorder และทีละชั้น คำนวณขนาด ความสูง ผลรวมของต้นไม้ย่อย และเส้นผ่านศูนย์กลางได้ใน O(N) โดยไม่พังเมื่อชุดทดสอบเป็นต้นไม้เส้นตรงสองแสนโหนด ซึ่งเป็นกับดักที่ทำให้โปรแกรมที่ถูกทุกบรรทัดได้ runtime error นอกจากนี้จะเขียน binary search tree และ binary heap ได้เองตั้งแต่ต้น เห็นกับตาว่าต้นไม้ค้นหาที่เขียนเองเอียงจนช้ากว่า set พันเท่าได้อย่างไร ทำไม set ในบทที่ 20 ไม่เป็นแบบนั้น และ priority_queue ข้างในทำงานอย่างไร โจทย์ผังองค์กร สายตระกูล เส้นทางในหมู่บ้าน และโจทย์ที่ต้องจำลองโครงสร้างข้อมูลตามกติกาที่กำหนด ในค่าย 2 และ TOI ใช้ทุกเรื่องในบทนี้
ในบทนี้
| หน้า | ได้อะไร |
|---|---|
| 26.1 ต้นไม้และการเก็บในโปรแกรม | ราก ลูก ใบ ความลึก ความสูง binary tree เก็บด้วย pointer ด้วยอาเรย์ลูกซ้ายขวา และด้วยรายชื่อลูก อ่านพ่อของแต่ละโหนดและหาราก |
| 26.2 ท่องต้นไม้ | preorder inorder postorder ของต้นไม้นิพจน์ ท่องทีละชั้นด้วย queue ขนาดและความสูงของต้นไม้ย่อย และเส้นผ่านศูนย์กลาง |
| 26.3 ต้นไม้ลึกกับ stack ที่เขียนเอง | recursion พังที่ความลึกราวสองหมื่นห้าพัน preorder และ inorder ด้วย stack และ postorder ด้วยการย้อนลำดับ |
| 26.4 binary search tree | ใส่ ค้นหา inorder ได้ค่าเรียง ลบสามกรณี ต้นไม้เอียงเมื่อใส่ข้อมูลที่เรียงแล้ว และ red-black tree ใน set |
| 26.5 binary heap | heap ในอาเรย์ sift up sift down สร้าง heap ใน O(N) heap sort และเทียบกับ priority_queue |