Cấu trúc dữ liệu

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 6)

Cấu trúc dữ liệu

B-Tree Insertion & Search

Thời gian (Time) O(log n)
Không gian (Space) O(n)

Mô tả nguyên lý

Cây tự cân bằng nhánh rộng tối ưu cho hệ thống lưu trữ đĩa.

Cài đặt mẫu (Implementation)

// Quản lý các nút chứa nhiều khóa và nhiều con nhánh phân cấp.
Cấu trúc dữ liệu

Bloom Filter

Thời gian (Time) O(k)
Không gian (Space) O(m)

Mô tả nguyên lý

Cấu trúc dữ liệu tiết kiệm bộ nhớ kiểm tra sự tồn tại phần tử.

Cài đặt mẫu (Implementation)

// Sử dụng mảng bit kết hợp k hàm băm độc lập.
Cấu trúc dữ liệu

Count-Min Sketch

Thời gian (Time) O(k)
Không gian (Space) O(width * depth)

Mô tả nguyên lý

Ước tính tần suất xuất hiện của các phần tử trong dòng dữ liệu lớn.

Cài đặt mẫu (Implementation)

// Ma trận bảng băm đếm tần số với nhiều hàm băm độc lập.
Cấu trúc dữ liệu

DSU with Rollback

Thời gian (Time) O(log N) mỗi thao tác
Không gian (Space) O(N)

Mô tả nguyên lý

Cấu trúc tập hợp rời rạc hỗ trợ hoàn tác (rollback) các phép hợp nhất qua ngăn xếp.

Cài đặt mẫu (Implementation)

// Không sử dụng nén đường đi (path compression) mà dùng union by rank để có thể khôi phục trạng thái.
Cấu trúc dữ liệu

Skip List

Thời gian (Time) O(log n)
Không gian (Space) O(n)

Mô tả nguyên lý

Danh sách liên kết phân tầng tốc độ tương đương cây cân bằng.

Cài đặt mẫu (Implementation)

// Danh sách liên kết đa tầng cho phép nhảy qua các đoạn nút nhanh chóng.
Cấu trúc dữ liệu

Treap (Tree + Heap)

Thời gian (Time) O(log n)
Không gian (Space) O(n)

Mô tả nguyên lý

Cây nhị phân tìm kiếm kết hợp Đống dựa trên khóa ưu tiên ngẫu nhiên.

Cài đặt mẫu (Implementation)

// Sử dụng phép quay cây dựa trên độ ưu tiên ngẫu nhiên của nút.