Rebalancing Algorithms (อัลกอริทึมการปรับสมดุลใหม่) ในโครงสร้างข้อมูล

Rebalancing Algorithms

1. Day-Stout-Warren (DSW) Algorithm

Rebalance BST ให้สมดุลใน O(n) Time (Linear in Number of Nodes)

DSW Algorithm Steps (Pseudocode)

1. Allocate "Pseudo-root" Node → Actual Root = Right Child ของ Pseudo-root
2. Call tree-to-vine: Convert Tree → Sorted Linked List (Vine) ใช้ Pseudo-root
3. Call vine-to-tree: Convert Vine → Balanced Tree ใช้ Pseudo-root + Tree Size
4. Actual Root = Pseudo-root's Right Child
5. Dispose Pseudo-root

tree-to-vine: Right Rotations ทำให้ Tree กลายเป็น Linked List (Vine) Lean Right
vine-to-tree: Left Rotations แบบคำนวณ (Compression) สร้าง Balanced Tree

2. "Copy-on-Write" Tree

ถ้ายอมรับ Lack of Linearizability (Write แล้ว Read ทันทีไม่เจอ แต่เจอภายหลัง 100ms-10s):

• Writes ทั้งหมดโดย Single Thread (with Rebalancing)
• Periodically Copy Tree → Read-Only Copy สำหรับ Reading Threads (No Concurrency Control)
• Publish Atomically

3. Concurrent Skip List

Alternative: Concurrent Skip List
- Logarithmic Average Case Search/Delete/Insert
- Parallelizable ได้ง่ายกว่า
- Java มี Lock-free Implementation มาตรฐาน (java.util.concurrent.ConcurrentSkipListMap)

สรุป

เลือก Rebalancing Strategy ตาม Use Case:
- Offline/Periodic Rebuild → DSW (Simple, Optimal)
- High Read, Low Write, Eventual Consistency OK → Copy-on-Write
- High Concurrency Reads/Writes → Concurrent Skip List / Chromatic Tree