Cấu trúc dữ liệu (Tree)

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

Cấu trúc dữ liệu (Tree)

AVL Tree Rotations

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 chiều cao thông qua các phép quay đơn và quay kép.

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

// Kiểm tra hệ số cân bằng (balance factor) và thực hiện xoay trái/phải.
Cấu trúc dữ liệu (Tree)

Binary Heap Operations

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

Mô tả nguyên lý

Cấu trúc dữ liệu dạng cây nhị phân hoàn chỉnh thỏa mãn tính chất đống (Min/Max Heap).

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

// Thực hiện các thao tác insert, extract-min / extract-max.
Cấu trúc dữ liệu (Tree)

Binary Search Tree (BST) Insertion

Thời gian (Time) O(log n) cân bằng, O(n) tồi
Không gian (Space) O(h)

Mô tả nguyên lý

Chèn một nút mới vào cây tìm kiếm nhị phân đảm bảo tính chất trái nhỏ hơn, phải lớn hơn.

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

// So sánh giá trị nút hiện tại và đệ quy rẽ trái hoặc phải.
Cấu trúc dữ liệu (Tree)

Fenwick Tree (Binary Indexed Tree)

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

Mô tả nguyên lý

Cấu trúc dữ liệu tối ưu thực hiện truy vấn tổng tiền tố và cập nhật phần tử mảng.

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

// Thao tác dựa trên các bit lsb (least significant bit).
Cấu trúc dữ liệu (Tree)

Red-Black Tree Insertion

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

Mô tả nguyên lý

Cây tìm kiếm nhị phân tự cân bằng với các nút được tô màu Đỏ hoặc Đen.

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

// Duy trì quy tắc màu sắc và cân bằng cây qua các phép đổi màu và quay cây.
Cấu trúc dữ liệu (Tree)

Segment Tree Range Query

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

Mô tả nguyên lý

Cấu trúc dữ liệu dạng cây giúp truy vấn khoảng và cập nhật giá trị phần tử cực nhanh.

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

// Xây dựng cây phân đoạn lưu trữ tổng hoặc giá trị min/max theo đoạn.
Cấu trúc dữ liệu (Tree)

Trie (Prefix Tree) Search

Thời gian (Time) O(M) với M là độ dài từ
Không gian (Space) O(N * M)

Mô tả nguyên lý

Cây tiền tố chuyên dùng để lưu trữ và tìm kiếm từ khóa hoặc gợi ý tự động (Autocomplete).

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

// Lưu trữ các ký tự theo từng nhánh phân cấp ký tự từ gốc.