Cấu trúc dữ liệu: câu hỏi luyện tập có giải thích

1Cấu trúc dữ liệu là gì

Cấu trúc dữ liệu là cách tổ chức dữ liệu trong bộ nhớ để một số thao tác nhanh: tìm một phần tử, thêm một phần tử, xóa một phần tử.

Không cấu trúc nào nhanh với mọi thứ. Chọn một cấu trúc nghĩa là chọn thao tác nào nên rẻ. Chi phí của chúng được viết bằng Big O, với n là số phần tử.

Hai khối xây dựng cơ bản là mảng và danh sách liên kết.

Một mảng lưu các phần tử trong một khối bộ nhớ, cái này nối tiếp cái kia. Máy tính có thể tính ra vị trí của phần tử i, nên đọc a[i] mất O(1). Chèn vào đầu nghĩa là phải dịch mọi phần tử: O(n).

Một danh sách liên kết lưu mỗi phần tử trong một nút có con trỏ tới nút kế tiếp. Con trỏ cuối là null. Chèn vào đầu (h) chỉ thay đổi một con trỏ: O(1). Nhưng để tới phần tử i bạn phải đi theo i con trỏ: O(n).

Một danh sách liên kết đôi còn có con trỏ tới nút trước, nên bạn có thể đi theo cả hai chiều.

2Ngăn xếp và hàng đợi

Một ngăn xếp (stack) giống một chồng đĩa: bạn chỉ thêm và lấy ra ở trên cùng. Phần tử vào sau cùng là phần tử ra đầu tiên: LIFO.

• push đặt một phần tử lên trên, pop lấy phần tử trên cùng ra, peek đọc phần tử trên cùng mà không lấy ra. Tất cả đều là O(1).
• Công dụng: chức năng hoàn tác của trình soạn thảo, ngăn xếp lời gọi của chương trình, kiểm tra dấu ngoặc cân bằng, tìm kiếm theo chiều sâu.

Một hàng đợi (queue) giống hàng người xếp ở quầy thanh toán: bạn vào cuối hàng và rời đi ở đầu hàng. Phần tử vào đầu tiên là phần tử ra đầu tiên: FIFO.

• enqueue thêm vào cuối, dequeue lấy ra từ đầu. Cả hai đều là O(1).
• Công dụng: các lệnh in, tin nhắn đang chờ xử lý, tìm kiếm theo chiều rộng.

Một deque (hàng đợi hai đầu) cho phép thêm và lấy ra ở cả hai đầu. Một hàng đợi ưu tiên luôn lấy ra phần tử có độ ưu tiên cao nhất trước; nó thường được xây dựng bằng một đống (heap).

3Cây, đống, bảng băm và đồ thị

Một cây có một nút trên cùng, gọi là gốc. Mọi nút khác có đúng một nút cha. Các nút không có con là lá. Cây có n nút thì có n − 1 cạnh.

Trong một cây nhị phân mỗi nút có nhiều nhất hai con. Một cây tìm kiếm nhị phân (BST) thêm một quy tắc: khóa trong cây con bên trái nhỏ hơn nút, khóa trong cây con bên phải lớn hơn.

Tìm kiếm trong BST đi theo một đường xuống, nên chi phí là O(chiều cao). Một cây cân bằng (AVL, đỏ-đen) giữ chiều cao gần log₂ n. Các khóa chèn theo thứ tự đã sắp xếp tạo thành một chuỗi có chiều cao n.

Một đống (heap) là cây nhị phân trong đó mỗi nút cha nhỏ hơn các con của nó (min-heap) hoặc lớn hơn (max-heap). Giá trị nhỏ nhất hoặc lớn nhất nằm ở gốc, và chèn và xóa tốn O(log n).

Một bảng băm lưu các cặp khóa–giá trị. Một hàm băm biến khóa thành chỉ số, nên chèn và tra cứu mất O(1) trung bình. Hai khóa có cùng chỉ số là một va chạm, được giải quyết bằng xích (một danh sách cho mỗi ô) hoặc địa chỉ mở (thử một ô khác).

Một đồ thị có các đỉnh nối với nhau bằng các cạnh, có thể có hướng hoặc trọng số. Nó được lưu bằng ma trận kề, O(V²) bộ nhớ, hoặc bằng danh sách kề, O(V + E).

4Phương pháp từng bước

Các câu hỏi thường mô tả một tác vụ và hỏi cấu trúc nào phù hợp, hoặc hỏi một cấu trúc trông thế nào sau một số thao tác.

1. Tìm thao tác phải nhanh: truy cập theo vị trí, theo khóa, phần tử mới nhất, phần tử cũ nhất, phần tử nhỏ nhất, hoặc một khoảng.
2. Ghép nó với một cấu trúc: chỉ số → mảng, khóa → bảng băm, mới nhất → ngăn xếp, cũ nhất → hàng đợi, nhỏ nhất hoặc lớn nhất → đống, thứ tự đã sắp xếp hoặc khoảng → cây tìm kiếm cân bằng.
3. Kiểm tra chi phí của các thao tác khác mà tác vụ cần, theo Big O.
4. Với câu hỏi theo dõi, hãy thực hiện từng thao tác một và ghi lại trạng thái sau mỗi thao tác.
5. Kiểm tra trạng thái cuối so với quy tắc của cấu trúc: LIFO, FIFO, thứ tự BST hoặc thứ tự đống.

5Một ví dụ có lời giải

Theo dõi từng bước. Hãy thử đoán bước tiếp theo trước khi mở nó.

6Lỗi thường gặp

• Nhầm LIFO với FIFO. Ngăn xếp trả về phần tử mới nhất, hàng đợi trả về phần tử cũ nhất.
• Nghĩ rằng danh sách liên kết cho phép truy cập nhanh theo chỉ số. Nó phải đi từ đầu.
• Cho rằng BST luôn là O(log n). Chỉ cây cân bằng mới vậy; chèn theo thứ tự đã sắp xếp cho O(n).
• Quên va chạm trong bảng băm. O(1) là trung bình, không phải trường hợp xấu nhất.
• Nhầm các cách duyệt. Duyệt trước: nút trước. Duyệt giữa: nút ở giữa. Duyệt sau: nút sau cùng.
• Dùng ma trận kề cho một đồ thị thưa lớn. Nó lãng phí O(V²) bộ nhớ.

7Các câu hỏi thi trông như thế nào

• Dễ: thuật ngữ và sự kiện chính. LIFO và FIFO, nút, gốc hay lá là gì, quy tắc BST, hàm băm làm gì.
• Trung bình: vận dụng khái niệm. Cấu trúc nào phù hợp với một tác vụ, kết quả của push và pop hay của các lần chèn BST, các cách duyệt cây, bảng băm với dò tuyến tính, chi phí theo Big O.
• Khó: ca bài tập và phân tích. Cây cân bằng, đống trong mảng, B-tree, trie, union-find, bộ lọc Bloom và các thiết kế như bộ nhớ đệm LRU.

Với một đống lưu trong mảng bắt đầu từ chỉ số 0, các con của chỉ số i nằm ở 2i + 1 và 2i + 2, và cha của nó nằm ở ⌊(i − 1) / 2⌋.