เรียนรู้ โครงสร้างข้อมูล ตั้งแต่ต้น ก่อนหน้านี้: อัลกอริทึมและความซับซ้อน
1 โครงสร้างข้อมูลคืออะไรโครงสร้างข้อมูล (data structure) คือวิธีจัดระเบียบข้อมูลในหน่วยความจำเพื่อให้การดำเนินการบางอย่างเร็ว เช่น การหารายการ การเพิ่ม การลบ
ไม่มีโครงสร้างใดเร็วในทุกอย่าง การเลือกโครงสร้างคือการเลือกว่าการดำเนินการใดควรมีต้นทุนต่ำ ต้นทุนเขียนด้วยบิ๊กโอ โดย n คือจำนวนรายการ
องค์ประกอบพื้นฐานสองอย่างคืออาร์เรย์และลิงก์ลิสต์
อาร์เรย์ (array) เก็บรายการในหน่วยความจำก้อนเดียวเรียงต่อกัน คอมพิวเตอร์คำนวณได้ว่ารายการ i อยู่ที่ใด การอ่าน a[i] จึงใช้ O(1) การแทรกที่ด้านหน้าต้องเลื่อนทุกรายการ: O(n)
ลิงก์ลิสต์ (linked list) เก็บแต่ละรายการในโหนด พร้อมตัวชี้ไปยังโหนดถัดไป ตัวชี้สุดท้ายเป็น null การแทรกที่หัว (h) เปลี่ยนตัวชี้เพียงตัวเดียว: O(1) แต่การไปถึงรายการ i ต้องตามตัวชี้ i ตัว: O(n)
ลิงก์ลิสต์สองทิศทาง (doubly linked list) มีตัวชี้ไปยังโหนดก่อนหน้าด้วย จึงเดินได้ทั้งสองทาง
ตรวจสอบตนเอง การดำเนินการใดเป็น O(1) สำหรับอาร์เรย์ แต่เป็น O(n) สำหรับลิงก์ลิสต์ทิศทางเดียวการนับรายการทีละรายการ การอ่านรายการที่ดัชนี i การเยี่ยมชมทุกรายการหนึ่งครั้ง การแทรกรายการใหม่ที่ด้านหน้า คำตอบ: การอ่านรายการที่ดัชนี i. อาร์เรย์คำนวณที่อยู่ของรายการ i ได้โดยตรง ลิงก์ลิสต์ต้องตามตัวชี้ i ตัวจากหัว การแทรกที่ด้านหน้าเป็นกรณีตรงข้าม: ถูกสำหรับลิสต์ แพงสำหรับอาร์เรย์
2 สแตกและคิวสแตก (stack) เหมือนกองจาน: เพิ่มและเอาออกที่ด้านบนเท่านั้น รายการที่เข้าทีหลังสุดออกก่อน: LIFO
push วางรายการไว้ด้านบน pop เอารายการบนสุดออก peek อ่านรายการบนสุดโดยไม่เอาออก ทั้งหมดเป็น O(1)การใช้งาน: ฟังก์ชันเลิกทำของโปรแกรมแก้ไข สแตกการเรียกฟังก์ชันของโปรแกรม การตรวจว่าวงเล็บสมดุล การค้นหาตามความลึก คิว (queue) เหมือนแถวที่แคชเชียร์: เข้าต่อท้ายแถวและออกที่หัวแถว รายการที่เข้าก่อนออกก่อน: FIFO
enqueue เพิ่มที่ท้าย dequeue เอาออกจากหน้า ทั้งสองเป็น O(1)การใช้งาน: งานพิมพ์ ข้อความที่รอการจัดการ การค้นหาตามความกว้าง ดีคิว (deque หรือ double-ended queue) เพิ่มและเอาออกได้ทั้งสองปลาย คิวลำดับความสำคัญ (priority queue) เอารายการที่มีความสำคัญสูงสุดออกก่อนเสมอ โดยทั่วไปสร้างเป็นฮีป
ตรวจสอบตนเอง โครงสร้างข้อมูลใดเหมาะกับปุ่ม “เลิกทำ” ของโปรแกรมแก้ไขข้อความที่สุดกราฟ คิว ตารางแฮช สแตก คำตอบ: สแตก. การเลิกทำต้องย้อนการกระทำล่าสุดก่อน: เข้าทีหลังสุดออกก่อน ถ้าเป็นคิวจะเลิกทำการกระทำเก่าที่สุดก่อน
3 ต้นไม้ ฮีป ตารางแฮช และกราฟต้นไม้ (tree) มีโหนดบนสุดหนึ่งโหนดคือราก (root) โหนดอื่นทุกโหนดมีพ่อแม่หนึ่งโหนดพอดี โหนดที่ไม่มีลูกคือใบ (leaf) ต้นไม้ที่มี n โหนดมี n − 1 เส้นเชื่อม
ในต้นไม้ทวิภาค (binary tree) แต่ละโหนดมีลูกไม่เกินสองโหนด ต้นไม้ค้นหาแบบทวิภาค (BST) เพิ่มกฎ: คีย์ในต้นไม้ย่อยซ้ายน้อยกว่าโหนด คีย์ในต้นไม้ย่อยขวามากกว่า
การค้นหาใน BST ตามเส้นทางเดียวลงไป จึงมีต้นทุน O(ความสูง) ต้นไม้สมดุล (AVL, red-black) รักษาความสูงให้ใกล้ log₂ n คีย์ที่แทรกตามลำดับเรียงทำให้เป็นสายโซ่สูง n
ฮีป (heap) คือต้นไม้ทวิภาคที่พ่อแม่ทุกโหนดน้อยกว่าลูก (min-heap) หรือมากกว่า (max-heap) ค่าน้อยที่สุดหรือมากที่สุดอยู่ที่ราก และการแทรกและเอาออกมีต้นทุน O(log n)
ตารางแฮช (hash table) เก็บคู่คีย์–ค่า ฟังก์ชันแฮช เปลี่ยนคีย์เป็นดัชนี การแทรกและค้นหาจึงใช้ O(1) โดยเฉลี่ย คีย์สองตัวที่ได้ดัชนีเดียวกันคือการชน (collision) แก้ด้วย chaining (ลิสต์ต่อช่อง) หรือ open addressing (ลองช่องอื่น)
กราฟ (graph) มีจุดยอดที่เชื่อมด้วยเส้นเชื่อม ซึ่งอาจมีทิศทางหรือน้ำหนัก เก็บเป็นเมทริกซ์ประชิด ใช้หน่วยความจำ O(V²) หรือเป็นลิสต์ประชิด ใช้ O(V + E)
ตรวจสอบตนเอง คีย์ 50, 30, 70, 20 และ 40 ถูกแทรกตามลำดับนี้ลงใน BST ที่ว่างเปล่า ลูกซ้ายของ 30 คืออะไร20 40 70 ไม่มีลูกซ้าย คำตอบ: 20. 20 น้อยกว่า 50 จึงไปทางซ้ายถึง 30 และน้อยกว่า 30 ด้วย จึงไปทางซ้ายอีก 40 มากกว่า 30 และกลายเป็นลูกขวาของ 30
4 วิธีทำทีละขั้นคำถามมักอธิบายงานหนึ่งแล้วถามว่าโครงสร้างใดเหมาะ หรือถามว่าโครงสร้างหน้าตาเป็นอย่างไรหลังการดำเนินการบางอย่าง
หาการดำเนินการที่ต้องเร็ว: เข้าถึงด้วยตำแหน่ง ด้วยคีย์ รายการใหม่สุด รายการเก่าสุด รายการเล็กสุด หรือช่วง จับคู่กับโครงสร้าง: ดัชนี → อาร์เรย์ คีย์ → ตารางแฮช ใหม่สุด → สแตก เก่าสุด → คิว เล็กสุดหรือใหญ่สุด → ฮีป ลำดับเรียงหรือช่วง → ต้นไม้ค้นหาสมดุล ตรวจต้นทุนของการดำเนินการอื่นที่งานต้องการ เป็นบิ๊กโอ สำหรับโจทย์ไล่สถานะ ให้ทำการดำเนินการทีละอย่างและเขียนสถานะหลังแต่ละขั้น ตรวจสถานะสุดท้ายกับกฎของโครงสร้าง: LIFO, FIFO, ลำดับ BST หรือลำดับฮีป 5 ตัวอย่างที่แก้ให้ดูทำตามทุกขั้นตอน ลองทำนายขั้นถัดไปก่อนเปิดดู
ตัวอย่างที่แก้ให้ดู คีย์ 50, 30, 70, 20, 40 และ 60 ถูกแทรกตามลำดับนี้ลงใน BST ที่ว่างเปล่า การท่องแบบ in-order ได้ผลอย่างไร และการค้นหา 60 ต้องเปรียบเทียบกี่ครั้ง
2 30 น้อยกว่า 50 จึงไปทางซ้าย 70 มากกว่า 50 จึงไปทางขวา
50 30 70
3 20: น้อยกว่า 50 น้อยกว่า 30 จึงอยู่ซ้ายของ 30 40: น้อยกว่า 50 มากกว่า 30 จึงอยู่ขวาของ 30 60: มากกว่า 50 น้อยกว่า 70 จึงอยู่ซ้ายของ 70
50 30 70 20 40 60
4 การท่องแบบ in-order เยี่ยมต้นไม้ย่อยซ้าย แล้วโหนด แล้วต้นไม้ย่อยขวา
ได้ 20, 30, 40, 50, 60, 70: คีย์ตามลำดับเรียง ซึ่งเป็นเช่นนี้เสมอสำหรับ BST
5 เปรียบเทียบกับ 50: มากกว่า ไปขวา เปรียบเทียบกับ 70: น้อยกว่า ไปซ้าย เปรียบเทียบกับ 60: พบ
50 30 70 20 40 60
การค้นหาต้องเปรียบเทียบ 3 ครั้ง หนึ่งครั้งต่อหนึ่งระดับ
คำตอบ In-order: 20, 30, 40, 50, 60, 70 การค้นหา 60 ต้องเปรียบเทียบ 3 ครั้ง
6 ข้อผิดพลาดที่พบบ่อยสับสน LIFO กับ FIFO สแตกคืนรายการใหม่สุด คิวคืนรายการเก่าสุด คิดว่าลิงก์ลิสต์เข้าถึงด้วยดัชนีได้เร็ว ต้องเดินจากหัว สมมติว่า BST เป็น O(log n) เสมอ เฉพาะต้นไม้สมดุลเท่านั้น การแทรกตามลำดับเรียงให้ O(n) ลืมการชนในตารางแฮช O(1) เป็นค่าเฉลี่ย ไม่ใช่กรณีเลวร้ายที่สุด สับสนการท่อง Preorder: โหนดก่อน In-order: โหนดตรงกลาง Postorder: โหนดท้ายสุด ใช้เมทริกซ์ประชิดกับกราฟใหญ่ที่เบาบาง สิ้นเปลืองหน่วยความจำ O(V²) ตรวจสอบตนเอง คุณ enqueue 1, 2 และ 3 ลงในคิวว่างตามลำดับนี้ dequeue ครั้งแรกคืนรายการใด1, 2 และ 3 พร้อมกัน 1 2 3 คำตอบ: 1. คิวเป็นเข้าก่อนออกก่อน 1 จึงออกก่อน 3 เป็นคำตอบของสแตก (pop) ซึ่งคืนรายการใหม่สุด
7 ข้อสอบมีหน้าตาอย่างไรง่าย: ศัพท์และข้อเท็จจริงสำคัญ LIFO และ FIFO โหนด ราก หรือใบคืออะไร กฎของ BST ฟังก์ชันแฮชทำอะไรปานกลาง: การประยุกต์แนวคิด โครงสร้างใดเหมาะกับงาน ผลของ push และ pop หรือการแทรกใน BST การท่องต้นไม้ ตารางแฮชแบบ linear probing ต้นทุนบิ๊กโอยาก: กรณีศึกษาและการวิเคราะห์ ต้นไม้สมดุล ฮีปในอาร์เรย์ B-tree, trie, union-find, Bloom filter และการออกแบบ เช่น LRU cacheสำหรับฮีปที่เก็บในอาร์เรย์เริ่มจากดัชนี 0 ลูกของดัชนี i อยู่ที่ 2i + 1 และ 2i + 2 และพ่อแม่อยู่ที่ ⌊(i − 1) / 2⌋
เรียนรู้ทีละขั้นในแอป เรียนรู้ทีละขั้นในแอป