Giải thích cấu trúc dữ liệu
Mọi chương trình đều cất dữ liệu ở đâu đó, và cách cất quyết định cái gì nhanh, cái gì chậm. Một danh sách một triệu cái tên có thể dò từng tên một, hoặc được sắp xếp sao cho hai mươi lần so sánh là tìm ra bất kỳ tên nào. Cấu trúc dữ liệu chính là những cách sắp xếp ấy: một nhúm ý tưởng, phần lớn còn lâu đời hơn máy tính cá nhân, nằm bên trong mọi cơ sở dữ liệu, hệ điều hành, trình duyệt và trò chơi.
Cấu trúc dữ liệu để làm gì
Người ta chọn cấu trúc dữ liệu theo những câu hỏi nó phải trả lời. Nhật ký cuộc gọi trên điện thoại cần cuộc gọi mới nhất trước, hàng in của máy in cần lệnh cũ nhất trước, từ điển cần nghĩa của một từ trong một trăm nghìn từ, công cụ chỉ đường cần giao lộ gần nhất chưa đi qua. Mỗi cấu trúc làm một số thao tác nhanh lên bằng cách hy sinh những thao tác khác, và ký hiệu O lớn mô tả sự đánh đổi đó: O(1) nghĩa là thời gian không tăng theo số phần tử n, O(log n) nghĩa là gấp đôi n chỉ thêm một bước, còn O(n) nghĩa là thời gian tăng tỉ lệ với n.
Ngăn xếp, hàng đợi và deque
Ngăn xếp thêm và lấy ra ở cùng một đầu: vào sau, ra trước. Lịch sử hoàn tác, nút quay lại và các lời gọi hàm của một chương trình đang chạy đều là ngăn xếp. Hàng đợi thêm vào cuối và lấy ra ở đầu: vào trước, ra trước, như các phím được gõ hay một hàng in. Deque cho phép cả hai việc ở cả hai đầu. Cả ba đều mất thời gian hằng số cho mỗi thao tác. Hàng đợi thường được cất trong bộ đệm vòng, một mảng cố định mà đầu và cuối quay vòng lại sau ô cuối cùng; khi đầy, các phần tử được sao chép sang một mảng lớn gấp đôi. Việc sao chép tốn O(n), nhưng hiếm đến mức trung bình mỗi thao tác vẫn chỉ tốn O(1), gọi là cận khấu hao.
Danh sách liên kết
Danh sách liên kết lưu mỗi giá trị trong một nút có con trỏ tới nút kế tiếp. Chèn hay xóa chỉ cần bẻ lại một hai con trỏ, không phải dời gì cả, nhưng không thể nhảy thẳng tới nút thứ mười: phải đi theo liên kết từ nút đầu. Một danh sách chỉ giữ nút đầu cần O(n) bước để tới đuôi; danh sách thực tế thường giữ thêm con trỏ đuôi, còn danh sách liên kết đôi có cả con trỏ lùi, và lịch sử trình duyệt hay bộ nhớ đệm LRU được xây dựng theo cách đó.
Cây tìm kiếm nhị phân
Cây tìm kiếm nhị phân giữ, tại mỗi nút, các giá trị nhỏ hơn ở cây con trái và lớn hơn ở cây con phải. Tìm kiếm so sánh rồi đi sang trái hoặc phải, còn duyệt trung thứ tự đọc ra các giá trị theo thứ tự. Xóa một lá chỉ là gỡ nó đi, nút có một con được thay bằng con đó, còn nút có hai con được thay bằng phần tử kế tiếp trung thứ tự của nó, tức giá trị nhỏ nhất ở cây con phải. Tất cả những việc này tốn thời gian tỉ lệ với chiều cao của cây: khoảng log n khi cây sum suê, nhưng là n khi các giá trị đến theo thứ tự và cây suy biến thành một danh sách.
Cây AVL và cây đỏ-đen
Cây tự cân bằng sửa lại hình dạng sau mỗi lần thay đổi. Cây AVL, do Adelson-Velsky và Landis phát minh năm 1962, giữ chiều cao hai cây con của mỗi nút chênh nhau không quá một; khi hệ số cân bằng của một nút đạt ±2, một phép quay (trường hợp LL và RR) hoặc hai phép quay (LR và RL) khôi phục cân bằng. Cây đỏ-đen tô màu các nút sao cho gốc màu đen, không nút đỏ nào có con đỏ và mọi đường đi xuống đều qua cùng số nút đen, nhờ vậy đường dài nhất không quá gấp đôi đường ngắn nhất. Nó tự sửa bằng cách tô lại màu và nhiều nhất vài phép quay, và đó là cây nằm bên trong TreeMap của Java, std::map của C++ và bộ lập lịch của Linux.
Đống và hàng đợi ưu tiên
Đống nhị phân là một cây nhị phân hoàn chỉnh được lưu trong mảng mà không cần con trỏ nào: các con của vị trí i nằm ở 2i + 1 và 2i + 2. Trong min-heap, mỗi nút cha không lớn hơn các con của nó, nên giá trị nhỏ nhất luôn ở gốc. Một giá trị mới được đặt ở cuối rồi nổi lên qua các nút cha lớn hơn; khi lấy gốc ra, giá trị cuối được đưa lên đỉnh rồi chìm xuống. Cả hai đều tốn O(log n), và cả một mảng có thể được biến thành đống trong O(n). Đống vận hành các hàng đợi ưu tiên trong thuật toán đường đi ngắn nhất của Dijkstra, trong mô phỏng sự kiện và bộ lập lịch của hệ điều hành, và tạo ra thuật toán sắp xếp vun đống.
Bảng băm
Bảng băm biến một khóa thành chỉ số mảng bằng hàm băm rồi đi thẳng tới đó. Các khóa khác nhau có thể rơi vào cùng một chỉ số: đó là va chạm. Xâu chuỗi giữ một danh sách nhỏ trong mỗi thùng; địa chỉ mở, như dò tuyến tính, thử các ô kế tiếp cho tới khi gặp ô trống, và khi xóa một khóa phải để lại bia mộ để các lần tìm sau tiếp tục dò. Với một hàm băm tốt và hệ số tải (số khóa mỗi thùng) được giữ thấp nhờ nới rộng bảng, chèn, tìm và xóa trung bình tốn O(1). Một hàm kém, như cộng mã ký tự của một từ, đẩy các từ đảo chữ vào cùng một thùng. Bảng băm nằm sau dict của Python, các đối tượng JavaScript và chỉ mục cơ sở dữ liệu.
Trie và union-find
Trie, hay cây tiền tố, lưu chuỗi với mỗi tầng một ký tự, nên các từ có phần đầu giống nhau dùng chung một đường đi và một nút đánh dấu nơi từ kết thúc. Tìm một từ dài L mất L bước, bất kể có bao nhiêu từ được lưu, và mọi từ có cùng một tiền tố đều nằm trong một cây con; tự động gợi ý và kiểm tra chính tả hoạt động như thế. Union-find giữ các phần tử trong những tập rời nhau, mỗi tập là một cây có gốc đại diện cho tập. Find đi theo liên kết cha tới gốc; union treo một gốc bên dưới gốc kia. Với hợp theo hạng và nén đường đi, một chuỗi dài thao tác tốn thời gian gần như hằng số cho mỗi thao tác, tức hàm Ackermann ngược α(n), không vượt quá 4 với mọi n thực tế. Thuật toán Kruskal tìm cây khung nhỏ nhất dựa vào nó.
Câu hỏi thường gặp
Mảng và danh sách liên kết khác nhau thế nào?
Mảng giữ các phần tử nằm sát nhau trong bộ nhớ, nên vị trí nào cũng tới được ngay, nhưng chèn vào giữa nghĩa là phải dời mọi thứ phía sau. Danh sách liên kết có thể chèn ở bất kỳ đâu bằng cách đổi con trỏ, nhưng muốn tới một vị trí thì phải đi từ nút đầu. Mảng cũng tận dụng bộ nhớ đệm của bộ xử lý tốt hơn nhiều, vì thế trong thực tế thường nhanh hơn.
Thời gian khấu hao nghĩa là gì?
Chi phí trung bình cho mỗi thao tác trên một chuỗi dài, ngay cả khi có lúc một thao tác đơn lẻ tốn kém. Một bộ đệm vòng tăng gấp đôi khi đầy thỉnh thoảng phải sao chép toàn bộ n phần tử, nhưng vì bộ đệm càng lớn thì việc sao chép càng hiếm, n lần thêm tốn tổng cộng O(n), tức trung bình O(1) mỗi lần.
Đống có giống cây tìm kiếm nhị phân không?
Không. Cây tìm kiếm nhị phân đặt mọi cây con trái trước nút của nó và mọi cây con phải sau nút, nên nó có thể liệt kê mọi giá trị theo thứ tự và tìm nhanh bất kỳ giá trị nào. Đống chỉ hứa rằng mỗi nút cha đứng trước các con, như vậy đủ để tìm ngay giá trị nhỏ nhất hoặc lớn nhất, nhưng không đủ để tìm một giá trị tùy ý.
Union-find biết hai phần tử có liên thông bằng cách nào?
Nó đi theo liên kết cha từ mỗi phần tử tới gốc của cây. Nếu cả hai tới cùng một gốc thì chúng ở cùng một tập. Sau đó, nén đường đi khiến mọi nút trên đường trỏ thẳng tới gốc, nên câu hỏi tiếp theo về chúng chỉ mất một bước.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Mở công cụ trực quan hóa cấu trúc dữ liệu