Cấu trúc dữ liệu — Mảng, Danh sách liên kết, Cây và Đồ thị

Cấu trúc dữ liệu là cách tổ chức dữ liệu để những tác vụ phổ biến như tìm kiếm, chèn, xóa và duyệt trở nên dễ hơn. Nếu bạn muốn hiểu mảng, danh sách liên kết, cây và đồ thị, cách nhanh nhất là đặt hai câu hỏi: dữ liệu có hình dạng gì, và thao tác nào cần có chi phí thấp?

Nếu dữ liệu là một dãy, mảng thường là điểm bắt đầu. Nếu mỗi phần tử chủ yếu trỏ đến phần tử tiếp theo, danh sách liên kết có thể phù hợp. Nếu dữ liệu có nhiều cấp, hãy dùng cây. Nếu các phần tử có thể kết nối theo nhiều hướng, hãy dùng đồ thị.

Đây là quy tắc ngắn gọn nhưng hữu ích nhất:

• Mảng: tốt nhất cho thứ tự theo chỉ số.
• Danh sách liên kết: tốt nhất cho các liên kết cục bộ theo chuỗi.
• Cây: tốt nhất cho cấu trúc phân cấp.
• Đồ thị: tốt nhất cho mạng lưới.

Mảng, danh sách liên kết, cây và đồ thị thực sự làm gì

Mảng lưu các phần tử theo một thứ tự cố định và cho phép bạn tham chiếu trực tiếp đến một vị trí, chẳng hạn như "phần tử $7$". Trong cách cài đặt liên tiếp thông thường, việc truy cập trực tiếp theo chỉ số đó là $O(1)$.

Danh sách liên kết lưu các phần tử dưới dạng các nút, trong đó mỗi nút trỏ đến một nút khác. Bạn có thể đi từ nút này sang nút khác, nhưng để đến phần tử thứ $n$ thì thường phải duyệt qua các nút trước đó, nên truy cập theo vị trí thường là $O(n)$.

Cây lưu dữ liệu theo nhiều cấp. Mỗi nút có thể có các nút con, nên cấu trúc này biểu diễn tự nhiên các quan hệ lồng nhau như thư mục bên trong thư mục. Chi phí tìm kiếm và cập nhật phụ thuộc vào loại cây và việc cây có được giữ cân bằng hay không.

Đồ thị lưu các nút và các cạnh. Không giống cây, một nút có thể kết nối với nhiều nút khác theo những cách tùy ý, và chu trình được phép tồn tại. Vì vậy, đồ thị là mô hình tự nhiên cho đường đi, mạng xã hội và sơ đồ phụ thuộc.

So sánh nhanh: khi nào mỗi cấu trúc dữ liệu phù hợp

Cấu trúc	Mô hình hình dung tốt nhất	Thường làm tốt	Hạn chế phổ biến
Mảng	Một hàng phần tử được đánh số	Truy cập trực tiếp theo chỉ số	Chèn và xóa ở giữa thường phải dời các phần tử
Danh sách liên kết	Một chuỗi các nút	Chèn hoặc xóa gần một nút đã biết	Truy cập ngẫu nhiên chậm
Cây	Một hệ phân nhánh phân cấp	Biểu diễn nhiều cấp và quan hệ cha-con	Hành vi phụ thuộc nhiều vào loại cây
Đồ thị	Một mạng lưới kết nối	Tính liên thông, đường đi và quan hệ	Thuật toán thường phức tạp hơn

Ví dụ minh họa: chọn cấu trúc trong một ứng dụng trong trường

Giả sử bạn đang xây dựng một ứng dụng trong trường có màn hình thời khóa biểu, danh mục môn học và bản đồ đi bộ. Cách dễ nhất để chọn cấu trúc dữ liệu là ghép từng tính năng với hình dạng dữ liệu của nó.

Các tab ngày trong tuần của màn hình thời khóa biểu tự nhiên là một mảng:

$$[\text{Mon}, \text{Tue}, \text{Wed}, \text{Thu}, \text{Fri}]$$

Tính năng chính ở đây là truy cập trực tiếp theo vị trí. "Hiển thị tab $3$" là điều hợp lý, và thứ tự có ý nghĩa.

Danh mục môn học tự nhiên là một cây:

$$\text{Department} \rightarrow \text{Course} \rightarrow \text{Section}$$

Mỗi cấp chứa cấp tiếp theo. Đây là một cấu trúc phân cấp, nên cây là mô hình gọn gàng nhất.

Các lối đi giữa các tòa nhà tự nhiên là một đồ thị. Một tòa nhà có thể kết nối với nhiều tòa nhà khác, và các đường đi có thể quay lại điểm cũ. Nếu bạn muốn tìm tuyến ngắn nhất từ thư viện đến phòng thí nghiệm, bạn đang giải một bài toán đồ thị chứ không phải bài toán cây.

Danh sách liên kết phù hợp với một phần hẹp hơn của cùng ứng dụng đó: chuỗi các màn hình vừa truy cập gần đây, nếu thao tác chính là tiến hoặc lùi từng bước một. Trong trường hợp đó, mỗi màn hình chủ yếu chỉ cần liên kết đến các màn hình lân cận thay vì truy cập nhanh đến màn hình thứ $20$.

Bài học ở đây là "tốt nhất" còn tùy vào công việc. Một sản phẩm có thể dùng nhiều cấu trúc dữ liệu vì các phần khác nhau của dữ liệu có những quan hệ khác nhau.

Cách phân biệt chúng thật nhanh

Nhiều học sinh, sinh viên ban đầu học những khái niệm này như các từ vựng cần nhớ. Điều đó khiến chủ đề trở nên trừu tượng, nhưng câu hỏi thực tế thì đơn giản hơn.

Hãy hỏi: thao tác nào cần có chi phí thấp?

Nếu bạn muốn "nhảy đến vị trí $i$" có chi phí thấp, mảng là lựa chọn mạnh. Nếu bạn muốn "đi theo kết nối tiếp theo" có chi phí thấp, các cấu trúc liên kết sẽ hữu ích. Nếu bạn muốn "đi xuống theo phân cấp", cây là phù hợp. Nếu bạn muốn "tìm xem hai thứ có được kết nối hay không", đồ thị là phù hợp.

Những lỗi thường gặp khi học cấu trúc dữ liệu

Cho rằng luôn có một cấu trúc nhanh nhất

Không có người chiến thắng trong mọi trường hợp. "Nhanh" phụ thuộc vào thao tác bạn thực hiện thường xuyên nhất và vào cách cài đặt.

Xem cây là tự động hiệu quả

Một số loại cây hỗ trợ tìm kiếm rất hiệu quả, nhưng điều đó phụ thuộc vào loại cây và vào các điều kiện cấu trúc như tính cân bằng. Một cây có hình dạng xấu có thể hoạt động kém hơn nhiều so với cây cân bằng.

Chọn danh sách liên kết chỉ vì nghe nói chèn là rẻ

Việc chèn có thể rẻ khi bạn đã có đúng nút cần thao tác. Nhưng việc tìm ra nút đó vẫn có thể tốn thời gian.

Dùng cây khi dữ liệu thực ra là đồ thị

Nếu một phần tử có thể có nhiều cha, có liên kết chéo hoặc có chu trình, việc ép dữ liệu vào cây có thể che giấu cấu trúc thật và khiến các thao tác về sau trở nên gượng ép.

Nhầm lẫn giữa cấu trúc trừu tượng và tính năng của ngôn ngữ

"Array", "list", "map" hoặc "tree" trong một ngôn ngữ lập trình có thể đi kèm những lựa chọn cài đặt ảnh hưởng đến bộ nhớ và tốc độ. Ý tưởng trừu tượng và vùng chứa cụ thể có liên quan với nhau, nhưng không hoàn toàn giống nhau.

Khi nào mảng, danh sách liên kết, cây và đồ thị được dùng

Mảng được dùng cho các tập hợp có thứ tự, bảng, bộ đệm và mọi trường hợp mà vị trí là quan trọng.

Danh sách liên kết xuất hiện trong các cài đặt chuyên biệt, nơi việc cập nhật con trỏ cục bộ quan trọng hơn truy cập ngẫu nhiên.

Cây được dùng cho dữ liệu phân cấp như hệ thống tệp, cấu trúc tài liệu, cây biểu thức và nhiều chỉ mục tìm kiếm.

Đồ thị được dùng cho tuyến đường, phân tích phụ thuộc, mô hình hóa mạng, liên kết gợi ý và các bài toán kết nối nói chung.

Cách chọn cấu trúc dữ liệu phù hợp

Hãy bắt đầu bằng hai câu hỏi:

1. Dữ liệu có quan hệ gì: dãy, phân cấp hay mạng lưới?
2. Thao tác nào quan trọng nhất: truy cập theo chỉ số, cập nhật cục bộ, duyệt theo phân cấp hay tìm đường đi?

Hai câu trả lời đó thường thu hẹp lựa chọn rất nhanh.

Nếu bạn vẫn chưa chắc, hãy phác thảo một phiên bản nhỏ của dữ liệu trên giấy. Hình vẽ thường làm lộ ra cấu trúc trước cả khi bạn viết mã.

Hãy thử với ví dụ của riêng bạn

Hãy chọn ba ví dụ quen thuộc như một playlist, một hệ thống thư mục và một bản đồ giao thông công cộng. Xác định xem mỗi ví dụ chủ yếu là một dãy, một hệ phân cấp hay một mạng lưới, rồi chọn cấu trúc giúp thao tác chính trở nên dễ dàng. Nếu bạn muốn thêm một trường hợp để tự kiểm tra, GPAI Solver có thể tạo ra các ví dụ phân loại tương tự.