Red-Black Tree Self-Balanced BST โหนดสี Red หรือ Black มี 3 Operations: Search, Insert, Delete ตัวอย่าง Tree แนวคิดการ Insert Insert เหมือน BST ปกติ เริ่มจาก Root ตรวจสอบสี แทรกตำแหน่งที่เหมาะสม แต่ Red-Black Tree ต้องมีขั้นตอนเพิ่มเติม เงื่อนไข Red-Black Tree ที่สมดุล Root ต้องเป็น Black เสมอ
Expression Trees Expression Trees: Leaf Nodes = Operands (ค่าที่จะนำไปคำนวณ) Internal Nodes = Operators (ตัวดำเนินการ) ตัวอย่าง 4 + ((7 + 9) * 2) มี Expression Tree ดังนี้: อัลกอริทึมสร้าง Expression Tree If T is not NULL: If T→data is an operand: return T.data A = solve(T.left)
Yens k-Shortest Path Algorithm แทนที่จะให้ Single Shortest Path เดียว Yens Algorithm ให้ k Shortest Paths เพื่อให้ได้ 2nd, 3rd, ... Shortest Paths สถานการณ์ตัวอย่าง เดินทางจาก A ไป B มีหลายเส้นทาง ต้องการ Shortest Path และข้ามเส้นทางที่น้อยกว่าในแง่ Time Complexity สะพานมียอด B จาก A ไป C ไม่มีใค
Linear Data Structure (โครงสร้างข้อมูลเชิงเส้น) องค์ประกอบเรียงลำดับตามลำดับ (Sequentially) เข้าถึงทุกองค์ประกอบได้โดย Traversal แบบ Linear ทุกอย่างอยู่ Level เดียว (No Hierarchy) ง่ายต่อการ Implement และใช้งาน ใช้ Memory มาก ไม่ Memory-friendly Time Complexity เพิ่มขึ้นตามขนาดข้อมูล ตัวอย่าง: Lis
Descriptive Data Mining (ข้อมูลขุดเชิงบรรยาย) พยายามเข้าใจอดีตจากการวิเคราะห์ข้อมูลที่จัดเก็บ ข้อมูลที่ให้มานั้นแม่นยำ (Accurate) ให้ Standard Reporting และ Ad-hoc Reporting ใช้ Reactive Approach (ตอบสนองต่ออดีต) ใช้ Data Aggregation และ Data Mining บอกลักษณะข้อมูลใน Target Dataset คำถาม: เกิดอะไร
Classification (การจำแนกประเภท) ให้ผลลัพธ์เป็น Discrete Values (ค่าตัวเลขไม่ต่อเนื่อง/หมวดหมู่) จัดกลุ่มข้อมูลเป็นกลุ่มต่างๆ ตามเกณฑ์ต่างๆ Unordered (ไม่มีลำดับ) ใช้ Mapping Function แมปค่าไปยัง Pre-defined Classes ตัวอย่าง: Decision Tree, Logistic Regression Regression (การถดถอย/พยากรณ์) ให้ผล
Primary Key รับรองว่าข้อมูลในคอลัมน์เฉพาะเป็น Unique ช่วยระบุ Record ใน Relational Database ให้ Unique อนุญาตเพียง 1 Primary Key ต่อ Table เป็นการรวม UNIQUE + NOT NULL Constraints ไม่สามารถเป็น NULL ได้ ค่าไม่สามารถลบจาก Parent Table ได้ Constraint สามารถกำหนด Implicit ได้สำหรับ Temporary Tables
Data (ข้อมูล) ข้อมูลประเภทใดๆ ที่จัดเก็บในหน่วยความจำคอมพิวเตอร์ นำไปใช้เพื่อวัตถุประสงค์ต่างๆ ได้ในภายหลัง อาจมีข้อมูลที่ให้ข้อมูล (Informative) หรือไม่ก็ได้ อาจผ่านการประมวลผล (Processed) หรือไม่ก็ได้ ใน DBMS: จัดเก็บเป็น File ที่ Navigate ได้ หรือใน Directories (Hierarchical) ใน DBMS: หมายถึงทุ
Interval Heaps คืออะไร Complete Binary Tree แต่ละโหนด (ยกเว้นตัวสุดท้าย) มี 2 องค์ประกอบ ให้ Priority ของ 2 ตัวในโหนด P คือ a และ b (a ≤ b) โหนด P แทน Closed Interval [a, b] a = Left Endpoint, b = Right Endpoint [c, d] อยู่ใน [a, b] ก็ต่อเมื่อ a ≤ c ≤ d ≤ b ใน Interval Heap: Intervals ของ Left/Rig
B-Tree Query (Searching) คล้าย BST Query ตัวอย่าง 56 และ < 81 เข้า Subtree ระหว่าง 56-81 ถึง Leaf เจอ 66 อัลกอริทึม BTreeSearch(root, key) Input: Root, Key Output: Value หรือ Null x := Read root if x index node: if object o with o→key = key: return o→val find child x→child[i] containin
ตัวอย่าง B-Tree การแทรก คล้าย BST แต่มีกติกา: โหนดมี m Children, m-1 Elements แทรกแล้ว < m-1 → ใส่ตรง แทรกแล้ว = m-1 → หา Median ของทั้งหมด Median ขึ้น Root ทำซ้ำ แล้ว Split ซ้าย/ขวา ตัวอย่าง: แทรก 79 Root 56 → Right Subtree < 81 → Left Subtree แทรกใน Root ได้ [66, 78, 79] Median = 78 ขึ้นไป Roo
ตัวอย่าง B-Tree กระบวนการลบ ค้นหา (เหมือน Query) ลบพร้อมรักษา: โหนดต้องมี ≥ m/2 Elements ลบแล้ว < m-1 → Adjust ลบโหนดทั้งโหนด → Merge Children ถ้าขนาด = m → Split 2 ส่วน Median ขึ้น ตัวอย่าง: ลบ 46 Children: [45] และ [47, 49] → Merge → [45, 47, 49] → 47 ขึ้นไป อัลกอริทึม BTreeDelete(x, key)
B+ Trees คืออะไร B+ Trees เป็น Extended Version ของ B-Trees รองรับ Insert, Delete, Search ดีกว่า B-Tree ความแตกต่างจาก B-Tree B-Tree: Keys และ Records อยู่ทั้ง Internal และ Leaf Nodes B+ Tree: Records อยู่ Leaf Nodes เท่านั้น Internal Nodes เก็บ Keys เท่านั้น Leaf Nodes ของ B+ Tree เชื่อมเป็น Lin
B+ Tree Query (Searching) คล้าย B-Tree Query รองรับ Range Query ตัวอย่าง B+ Tree การค้นหา 60 แต่ < 75 ไป Right Child ของ 60 ได้ 63 แต่เป็น Internal Node ไม่ใช่ Data จริง ต้องไป Right Child อีกครั้ง ที่ Leaf Level จะเจอ 63 เป็น Record จริง Range Query 63 ถึง 78: หา Leaf ของ 63 แล้วเดิน Linked L
ตัวอย่าง B+ Tree การแทรก คล้าย B-Tree แทรกที่ Leaf ถ้าอยู่ใน Internal Node จะมี Copy อยู่ที่ Leaf (Right Child ของตัวเอง) 60 และ < 75 เข้า Middle Subtree แทรกหลัง 63 โหนดแยก 2 ส่วน 65 ขึ้นไป และ 65 อยู่ที่ Right Node ด้วย อัลกอริทึม BPlusTreeInsert(root, key) Input: Root, Key to insert (assum
ตัวอย่าง B+ Tree กระบวนการลบ (2 ส่วน) ค้นหาองค์ประกอบ (เหมือน Query) ลบพร้อมรักษาเงื่อนไข: โหนดต้องมีอย่างน้อย m/2 องค์ประกอบ ถ้าลบแล้วเหลือ < m-1 ให้ Adjust ถ้าลบโหนดทั้งโหนด ให้ Merge Children ถ้าขนาด = m ให้ Split กลับ 2 ส่วน Median ขึ้นไป ตัวอย่าง: ลบ 78 มี Children 2 ตัว: [75, 77] และ [7
Interval Tree คืออะไร Interval Trees เป็นต้นไม้ที่เชื่อมโยงกับ Intervals (ช่วง) Interval = Range เช่น [a, b] หมายถึงช่วงจาก a ถึง b Elementary Intervals Interval [10, 20] สร้าง 3 ช่วง: -∞ ถึง 10, 10 ถึง 20, 20 ถึง ∞ เพิ่ม Interval [15, 25]: เพิ่ม Interval [18, 22]: ตาราง Sub-intervals Inte
โจทย์ที่ Segment Tree แก้ มี Array arr[0,...,n-1] ต้องการรองรับ 2 Operation: Query: หาผลรวม Index l ถึง r (0 ≤ l ≤ r ≤ n-1) Update: เปลี่ยนค่า arr[i] = x (0 ≤ i ≤ n-1) Segment Tree Representation Leaf Nodes = องค์ประกอบของ Array เดิม Internal Nodes = ผลรวมของ Leaves ใต้โหนดนั้น (Merge Operation
K-ary Tree คืออะไร K-ary Tree เป็น Rooted Tree ที่แต่ละโหนดมีลูกได้สูงสุด k ตัว k = 2 → Binary Tree k = 3 → Ternary Tree Binary/Ternary Trees เป็น Specialized K-ary Trees K-ary Trees คือการทั่วไป (Generalization) ตัวอย่าง K-ary Tree Root มี 4 ลูก ลูกที่ 1 มี 3 ลูก ลูกที่ 2 ไม่มีลูก ลูกที่ 3 มี
Acyclic Digraphs คืออะไร Acyclic Digraphs = Directed Graphs ที่ไม่มี Directed Cycles ย่อว่า DAG (Directed Acyclic Graphs) ทุก Finite DAG มีโหนดอย่างน้อย 1 โหนดที่ Out-degree = 0 ตัวอย่าง DAG 1 โหนด: DAG 2 โหนด: DAG 3 โหนด:
