นิยาม HBLT พิจารณา Binary Tree ที่แทน Empty Subtree ด้วย External Node โหนดอื่นๆ เรียก Internal Nodes เพิ่ม External Nodes เข้าไป = Extended Binary Tree ไม่นับ Leaf Edges = Binary Tree จริง นับรวม = Extended Binary Tree นิยาม s(x) = ความยาว Shortest Path จาก x ไป External Node ใน Subtree ของ x x

Insertion ผ่าน Meld Operation Insert เข้า Max HBLT ทำได้ด้วย Max Meld Operation (Merge 2 Max HBLTs) สมมติแทรก x เข้า HBLT ชื่อ H สร้าง HBLT เล็กจาก x แล้ว Meld กับ H หลัง Meld H จะมีทุกองค์ประกอบรวม x Melding จึงเป็น Operation พื้นฐานสำหรับ Insert ใน HBLT

การลบ Max Element ใน Max HBLT Root มีค่าสูงสุด ถ้าลบ Root แล้ว Left และ Right Subtrees จะแยกออกเป็น 2 Max HBLTs แยกกัน โดย Meld ทั้งสองเข้าด้วยกันอีกครั้ง จะได้ Max HBLT เดียวที่มีทุกองค์ประกอบ ยกเว้นตัวที่ลบ

กลยุทธ์ Meld แบบ Recursive A และ B เป็น HBLTs 2 ต้นที่จะ Meld: ถ้าต้นไหนว่าง ให้อีกต้นเป็นผลลัพธ์ ถ้าทั้งคู่ไม่ว่าง: เปรียบเทียบ Root ค่ามากกว่าเป็น Root ของ Melded HBLT สมมติ A มี Root ใหญ่กว่า L = Left Subtree ของ A C = Max HBLT จากการ Meld Right Subtree ของ A กับ B ผลลัพธ์: Root = A, Subtrees

ปัญหาของ Array Representation Array Representation ใช้พื้นที่มากเกินไปเมื่อเก็บข้อมูลที่เปลี่ยนแปลง ต้องจัดสรรพื้นที่ใหญ่พอสำหรับค่าสูงสุด ใช้ Array Doubling เพิ่มขนาด ตัวอย่าง: ขนาดปัจจุบัน 8192 เต็ม เพิ่มเป็น 16384 คัดลอก 8192 แล้ว Deallocate เก่า ก่อน Deallocate ขนาดรวม = 3×8192 (เก่า + ใหม่) ไ

กฎการลบโหนด Arbitrary การลบโหนด Arbitrary จาก Max/Min HBLT ไม่ใช่ Standard Operation สำหรับ Priority Queue หรือ HBLT ถ้าต้องการลบโหนด K: Detach Subtree ที่ Root = K ออกจากต้นไม้ แทนที่ด้วย Meld ของ Subtrees ของ K อัปเดต s Values จากเส้นทาง K ถึง Root และ Swap Subtrees ตามเส้นทางนั้นเพื่อรักษา HBLT

นิยาม WBLT Leftist Tree แบบนี้พิจารณาจำนวนโหนดใน Subtree แทนที่จะเป็นความยาว Shortest Path จาก Root สู่ External Node นิยาม Weight w(x) ของโหนด x = จำนวน Internal Nodes ใน Subtree ที่ Root = x ถ้า x เป็น External Node w(x) = 0 ถ้าเป็น Internal Node w(x) = 1 + ผลรวม w ของลูกๆ ตัวอย่าง Binary Tree:

Max-WBLT Operations HBLT มี Operations: Insert, Delete, Initialize คล้าย WBLT แต่ Meld Operation ทำได้ใน Single Top-to-Bottom Pass ข้อได้เปรียบของ WBLT Meld ทำได้ใน Single Pass เพราะหา w values ได้ขณะลงมา (Top-down) อัปเดต w และ Swap Subtrees ได้ตามต้องการ สำหรับ HBLT หา s values ขณะลงมาไม่ได้ เพ

Robin-Hood Hashing เป็นเทคนิค Open Addressing พยายามทำให้ Search Time เท่าเทียมด้วย Collision Resolution ที่เป็นธรรม เมื่อแทรก x ที่ตำแหน่ง xᵢ ถ้ามี y อยู่แล้ว (yⱼ = xᵢ) ตัวที่ อายุน้อยกว่า (Younger) ต้องไปต่อ i ≤ j แล้วลอง xᵢ₊₁, xᵢ₊₂... มิฉะนั้น ใส่ x ที่ xᵢ ย้าย y ไป yⱼ₊₁, yⱼ₊₂... ผลการวิเคราะห์

Dictionary และ Binary Search Tree เมื่อ Implement Abstract Data Type Dictionary โหนดจะเชื่อมโยงกับค่า (Values) Dictionary คือเซตของ Keys ที่มี Total Ordering อาจมีข้อมูลเพิ่มเติมเชื่อมกับแต่ละ Key ถ้าใช้ Tree Implement: แต่ละโหนดเก็บ Unique Keys สำหรับโหนด u ในต้นไม้ ทุก Key ใน u.left u.key เรียก

Merge Algorithm ใช้รวม 2 Sorted Lists ให้กลายเป็น 1 List ใช้ใน Merge Sort เพื่อรวม Sorted Lists ให้ใหญ่ขึ้น แนวทาง มี 2 Pointers ชี้ที่ List 1 และ List 2 เปรียบเทียบค่า นำค่าน้อยกว่าเข้า Merged List เพิ่ม Pointer ของ List นั้น ทำซ้ำจน List ใด List หนึ่งหมด แล้วต่อ List ที่เหลือท้าย Merged List ภา

B-Tree คืออะไร B-Trees เป็น m-way Search Tree เฉพาะทาง ใช้กันอย่างแพร่หลายสำหรับ Disk Access B-Tree อันดับ m มี Key สูงสุด m-1 และ Children สูงสุด m เก็บข้อมูลเยอะในโหนดเดียวได้ ความสูงต่ำ relativo นี่คือข้อได้เปรียบใหญ่ คุณสมบัติเพิ่มเติมจาก m-way Tree ทุกโหนดมี Children สูงสุด m ตัว โหนดที่ไม่ใ

R-Trees คืออะไร R-Trees ใช้จัดเก็บ Spatial Data Indexes อย่างมีประสิทธิภาพ เหมาะสำหรับ Spatial Queries และ Storage ใช้ใน: Indexing ข้อมูลหลายมิติ (Multidimensional) จัดการข้อมูลเกม (Game Data) เก็บพิกัดภูมิศาสตร์ (Geospatial Coordinates) Virtual Maps Implementation ตัวอย่าง R-Tree R-Tree ที่สอด

Red-Black Tree คืออะไร Red-Black Trees เป็น Self-Balancing Binary Search Tree มีเงื่อนไขสำหรับแต่ละโหนด: ทุกโหนดมีสี: Red หรือ Black Root ต้องเป็น Black เสมอ ไม่มีโหนด Red 2 ตัวติดกัน (Parent-Child) ทุกเส้นทางจากโหนดใดๆ (รวม Root) ไปยัง Descendant NULL Node ต้องมีจำนวน Black Nodes เท่ากัน ตัวอย่

การเขียนนิพจน์คณิตศาสตร์ (Notation) นิพจน์คณิตศาสตร์เขียนได้ 3 รูปแบบที่เทียบเท่ากัน: Infix (ปกติ) Prefix Postfix Prefix Notation (Polish Notation) Operator อยู่หน้า Operands เช่น +ab เทียบเท่า Infix a + b Postfix Notation (Reverse Polish Notation) Operator อยู่หลัง Operands เช่น ab+ เทียบเท่า

Tournament Tree Complete Binary Tree มี External Nodes n ตัว และ Internal Nodes n-1 ตัว External Nodes = ผู้เล่น Internal Nodes = ผู้ชนะการแข่งขันระหว่าง 2 ผู้เล่น เรียกอีกอย่างว่า Selection Tree คุณสมบัติ เป็น Rooted Tree มีทิศทาง Parent → Children มีรากเพียง 1 ตัว ค่า Parent ≤ (หรือ ≥) ค่า Chil

นิยาม Unrooted Binary Tree เป็น Undirected Graph ที่เชื่อมต่อและไม่มี Cycle โหนดที่มีเพื่อนบ้าน 1 ตัวคือ Leaf โหนดที่เหลือคือ Internal Nodes Degree = จำนวนเพื่อนบ้าน ในต้นไม้ที่มีโหนดมากกว่า 1 ใบไม้คือโหนดที่ Degree = 1 Free Tree Free Tree เป็น Binary Tree ที่ Internal Nodes ทุกตัวมี Degree = 3 อย

ตัวอย่าง Rooted Tree ตัวอย่าง Unrooted Tree ความแตกต่างหลัก Rooted Tree: โหนดที่มีลูกแทน Common Ancestor ล่าสุดของลูกๆ เส้นขอบอาจแทนการประมาณเวลา Unrooted Tree: ไม่มีรากบรรพบุรุษ (Ancestral Root) แสดงลำดับการแยกกิ่ง (Branching Order) แต่ไม่บอกตำแหน่ง Root หรือ Common Ancestor สุดท้าย

ปัญหาของ Hash Function เดียว สำหรับ Hash Function ใดๆ หากขนาดตาราง m น้อยกว่า Universe Size u มาก จะมี Subset ใหญ่ของ U ที่มี Hash Value เหมือนกัน แนวทางแก้: Universal Hashing ใช้เซตของ Hash Functions (ℌ) เลือกตัวที่ทำงานดีกับ S หากฟังก์ชันส่วนใหญ่ดีกับ S สามารถสุ่มเลือกได้ ℌ เป็น Universal ถ้า:

Hashing with Chaining Chaining เป็นเทคนิคแก้ไข Collision ไม่สามารถหลีกเลี่ยง Collision ได้ แต่พยายามลดและจัดเก็บหลายองค์ประกอบสำหรับ Hash Value เดียวกัน ตัวอย่าง Hash Function h(x) = x mod 7 (ค่า 0-6) ข้อมูล: {15, 47, 23, 34, 85, 97, 65, 89, 70} ค่าแฮช: Hashing with Chaining: แทรกที่หัวลิสต์เพื่