bokkypoobah/BokkyPooBahsRedBlackTreeLibrary

🌲 BokkyPooBahs Red-Black Tree Library — Cây tìm kiếm tự cân bằng O(log n) cho Solidity

Thư viện Solidty dùng thuật toán Red-Black Tree lặp (không đệ quy), tối ưu gas, hỗ trợ insert/delete/search O(log n).

Đây là thư viện Solidity giúp duy trì một chỉ mục uint đã sắp xếp cho dữ liệu trên chuỗi. Sử dụng cây tìm kiếm nhị phân Red-Black tự cân bằng, mọi thao tác thêm, xóa, tìm kiếm đều chạy trong O(log n). Phù hợp cho trường hợp dùng như sổ lệnh on-chain trong DEX, cung cấp thuật toán matching đơn cửng minh.

✨ Điểm nổi bật

• Thuật toán lặp (iterative): tránh đệ quy, tiết kiệm gas.
• O(log n): insert, delete, search đều hiệu quả.
• Gas tối ưu: insert trống 68,459 gas; insert 10k keys ~127,210 gas; delete ~44k–81k gas.
• Chỉ mục sắp xếp: dùng để truy cập dữ liệu mapping theo thứ tự.
• Key 0 cấm: tránh xung đột giá trị mặc định.
• Bug bounty: đang được kiểm thử, chưa dùng production nếu chưa audit.

💡 Vì sao đáng chú ý

Khác với cây tìm kiếm nhị phân thường (có thể mất cân bằng thành danh sách liên kết khi thêm tuần tự), Red-Black Tree duy trì độ cân bằng bằng quy tắc tô màu nút. Phù hợp cho DEX cần sổ lệnh công bằng, minh bạch trên blockchain.

---

#Solidity #RedBlackTree #SmartContract #BinarySearchTree #GasOptimization #Ethereum #TiniX