Topological sort หรือ topological ordering ของ directed graph คือ linear ordering ของ vertices ที่สำหรับทุก directed edge UV จาก vertex u ไป vertex v u จะมาก่อน v ใน ordering นี้มีความหมายเฉพาะใน directed graphs มีหลายที่ที่ topological sort นำไปใช้ได้ เช่น ตามสูตรอาหาร มี steps ที่ต้องทำก่อนถึง st

ใน graph theory shortest path problem คือโจทย์หา path ระหว่างสอง vertices (nodes) ใน graph ที่ sum of weights ของ constituent edges ถูก minimize ที่นี่เราต้อง modify add edge และ add directed methods ให้รองรับการเพิ่ม weights ให้ edges ด้วย มาดูวิธีเพิ่มได้อย่างไร: ตัวอย่างโค้ด /** * เพิ่ม 2 edges

Dijkstras algorithm เป็นอัลกอริทึมหา shortest paths ระหว่าง nodes ใน weighted graph เราจะใช้ addEdge และ addDirectedEdge methods ใหม่เพื่อเพิ่ม weights ให้ edges เมื่อสร้าง graph มาดูการทำงานของอัลกอริทึมนี้: สร้าง distance collection และตั้งค่า distances ของ vertices ทั้งหมดเป็น infinity ยกเว้น s

Dijkstras algorithm ใช้หา shortest path จาก node หนึ่งไปทุก node อื่นๆ มีกรณีที่เราต้องหา shortest paths จากทุก node ไปทุก node อื่น นี่คือที่มาของ All pairs shortest path algorithms อัลกอริทึมที่ใช้มากที่สุดคือ Floyd Warshall algorithm Floyd Warshall algorithm ทำงานดังนี้: Initialize N x N matrix

Tree traversal (หรือ tree search) หมายถึงกระบวนการ visit (ตรวจสอบและ/หรือ update) แต่ละ node ใน tree data structure ทุก node เพียงครั้งเดียว Traversal เหล่านี้จัดประเภทตามลำดับที่ nodes ถูก visit

ใน traversal method นี้ left subtree จะถูก visit ก่อน แล้ว root และทีหลัง right sub-tree เราควรจำเสมอว่าแต่ละ node อาจเป็น subtree เองก็ได้ ถ้า binary tree ถูก traverse in-order ผลลัพธ์จะได้ sorted key values ใน ascending order เริ่มจาก A ตาม in-order เราไป left subtree B B ก็ถูก traverse in-order

ใน traversal method นี้ root node จะถูก visit ก่อน แล้ว left subtree และสุดท้าย right subtree เริ่มจาก A ตาม pre-order เรา visit A ก่อน แล้วไป left subtree B B ก็ถูก traverse pre-order เช่นกัน กระบวนการดำเนินต่อไปจน visit ทุก nodes ผลลัพธ์ pre-order traversal: A → B → D → E → C → F → G อัลกอริธมที

ใน traversal method นี้ root node จะถูก visit สุดท้าย จึงชื่อว่า post-order ก่อนอื่นเรา traverse left subtree แล้ว right subtree และสุดท้ายคือ root node เริ่มจาก A ตาม post-order เราไป left subtree B ก่อน B ก็ถูก traverse post-order เช่นกัน กระบวนการดำเนินต่อไปจน visit ทุก nodes ผลลัพธ์ post-order

การลบ Node จาก tree ค่อนข้างซับซ้อนถ้าดูจากระยะไกล มี 3 กรณีที่ต้องพิจารณาเมื่อลบ node ซึ่งอธิบายใน comment ของฟังก์ชันต่อไปนี้ เหมือนเดิมเราจะสร้าง method ในคลาสและ helper สำหรับ recursive call Class method deleteNode(key) { // ถ้าลบ node สำเร็จ จะได้ reference กลับมา return !(deleteNodeHelper

นี่คือการนำ BinarySearchTree Class ไปใช้งานอย่างสมบูรณ์: ตัวอย่างโค้ด class BinarySearchTree { constructor() { this.root = null; } insertIter(data) { let node = new this.Node(data); if (this.root === null) { this.root = node; return; } let currNode = this.root;

AVL tree (ตั้งชื่อจากผู้คิดค้น Adelson-Velsky และ Landis) เป็น self-balancing binary search tree Self-balancing tree คือ tree ที่ทำ rotation ภายใน subtrees เพื่อให้สมดุลทั้งซ้ายและขวา Tree แบบนี้มีประโยชน์อย่างยิ่งในกรณีที่ insertions ทำให้ tree หนักด้านใดด้านหนึ่ง Balanced trees ทำให้ lookup times

AVL tree ตรวจสอบความสูงของ left และ right sub-trees และรับรองว่าความต่างไม่เกิน 1 ความต่างนี้เรียกว่า Balance Factor เช่นใน tree ต่อไปนี้ tree แรกสมดุล สอง tree ถัดไปไม่สมดุล: ใน tree ที่สอง left subtree ของ C สูง 2 right subtree สูง 0 ความต่างคือ 2 ใน tree ที่สาม right subtree ของ A สูง 2 left หา

เพื่อปรับสมดุล AVL tree อาจทำ rotation 4 แบบ: Left rotation Right rotation Left-Right rotation Right-Left rotation สองแบบแรกเป็น single rotations สองแบบถัดไปเป็น double rotations เพื่อให้มี unbalanced tree เราต้องมี tree สูงอย่างน้อย 2 ด้วย tree เรียบง่ายนี้ มาเข้าใจทีละแบบ: Left Rotation ถ้า tre

เราสามารถเรียนรู้วิธีเพิ่ม node ใน AVL Tree การ insert ใน AVL trees เหมือน BST เพียงแค่ต้องทำขั้นตอนเพิ่มเติมคือ balance tree ระหว่าง insert เมื่อเราเคลื่อนลงต้นไม้ สิ่งนี้ต้องคำนวณ balance factor ที่เราเคยเห็น และตาม configuration เราต้องเรียก rotation methods ที่เหมาะสม ซึ่งเข้าใจง่ายด้วยคำอธิบาย

บางครั้งเราต้องรวม container สองตัวด้วย join function และได้ container ใหม่ เราจะเขียน static join method ที่รับ 2 HashTables และสร้าง HashTable ใหม่พร้อมค่าทั้งหมด เพื่อความเรียบง่าย เราจะให้ค่าจากตัวที่สอง override ค่าตัวแรกถ้ามีคีย์ซ้ำกัน ตัวอย่างโค้ด combo.put(k, v)); return combo; } ทดสอบกา

นี่คือการนำ HashTable class ไปใช้งานอย่างสมบูรณ์ ซึ่งยังสามารถปรับปรุงได้โดยใช้ data structures และ collision resolution algorithms ที่มีประสิทธิภาพมากขึ้น ตัวอย่างโค้ด class HashTable { constructor() { this.container = []; // เติม container ด้วย array ว่างๆ // สำหรับเพิ่ม elements ใน

Tree แสดงโครงสร้างลำดับชั้น เช่น organization hierarchy charts, file systems ฯลฯ เพื่อให้เป็นทางการมากขึ้น Tree สามารถกำหนดได้แบบ recursive (locally) ว่าเป็น collection of nodes (เริ่มที่ root node) โดยแต่ละ node เป็น data structure ประกอบด้วย value พร้อม list of references ไปยัง nodes (children) โ

Binary Tree เป็นโครงสร้างข้อมูลพิเศษสำหรับเก็บข้อมูล Binary tree มีเงื่อนไขพิเศษคือแต่ละ node สามารถมี child ได้สูงสุด 2 ตัว Binary tree มีข้อดีของทั้ง ordered array และ linked list คือ search เร็วเท่า sorted array และ insertion/deletion เร็วเท่า linked list นี่คือภาพประกอบ binary tree พร้อมคำศัพท์

Binary Search Tree มีพฤติกรรมพิเศษ: left child ของ node ต้องมีค่าน้อยกว่า parent และ right child ต้องมีค่ามากกว่า parent เราจะเน้นที่ต้นไม้แบบนี้ใน section นี้ Operations on Binary Search Trees เราจะกำหนด operations ต่อไปนี้บน BST: Inserting a key into a tree In-order traversal in a tree Pre-orde

แต่ละ element ใน tree คือ node เราต้องกำหนด node ก่อนที่จะไปกำหนด binary tree เพราะ tree ประกอบด้วย nodes เราจะสร้าง node definition เรียบง่ายที่มี 3 properties คือ left, right และ data left - เก็บ reference ไปยัง left child ของ node นี้ right - เก็บ reference ไปยัง right child ของ node นี้ data -