Cấu trúc dữ liệu phi tuyến

Cấu trúc dữ liệu phi tuyến là cấu trúc dữ liệu trong đó các phần tử dữ liệu không được tổ chức thành một chuỗi có thứ tự chỉ số như cấu trúc dữ liệu tuyến tính (xt. Cấu trúc dữ liệu, Cấu trúc dữ liệu tuyến tính).

Các cấu trúc dữ liệu phi tuyến tiêu biểu là đồ thị và cây.

Đồ thị

Đồ thị bao gồm đỉnh và cạnh, trong đó đỉnh biểu diễn các thực thể và cạnh biểu diễn mối liên hệ giữa các thực thể đó. Nếu đỉnh i có mối liên hệ với đỉnh j thì gọi là đỉnh i kề với đỉnh j. Khi ứng dụng vào các bài toán cụ thể, còn có thể đưa thêm các thông tin khác như chiều và trọng số của mối quan hệ, tương ứng với khái niệm đồ thị có hướng và đồ thị có trọng số.

Các phép toán cơ bản với đồ thị được chia thành hai nhóm chính:

1. Các phép toán với đỉnh: thêm đỉnh, dỡ bỏ đỉnh, thay đổi giá trị của đỉnh;
2. Các phép toán với cạnh: thêm cạnh, dỡ bỏ cạnh, truy cập vào giá trị trọng số, thay đổi trọng số, kiểm tra xem đỉnh i có kề với đỉnh j hay không.

Các ngôn ngữ lập trình bậc cao không cài đặt đồ thị như một kiểu dữ liệu có sẵn mà phải xây dựng dựa trên một số kiểu dữ liệu khác. Hai cách phổ biến nhất để xây dựng cấu trúc dữ liệu đồ thị là sử dụng ma trận kề và danh sách kề.

• Ma trận kề M là một ma trận vuông với kích thước mỗi chiều là số đỉnh của đồ thị. Giá trị của mỗi phần tử M[i,j] tương ứng với mối quan hệ giữa hai đỉnh i và j. M[i,j] có giá trị bằng 0 khi đỉnh i không kề với đỉnh j, khác 0 trong trường hợp ngược lại. Với đồ thị có hướng thì có thể xảy ra trường hợp M[i,j] = 0 trong khi M[j,i] khác không. Với đồ thị có trọng số thì giá trị M[i,j] là một số thực, tương ứng với giá trị của mối liên hệ giữa hai đỉnh i và j. Trong các ngôn ngữ lập trình bậc cao, ma trận kề thường được cài đặt dưới dạng mảng hai chiều, sử dụng một vùng nhớ liên tục khi chạy chương trình. Cách này rất hiệu quả khi thực hiện các phép toán với cạnh do chỉ cần một thao tác đọc hoặc thay đổi ô nhớ. Tuy nhiên, trong trường hợp số lượng đỉnh của đồ thị có thay đổi thì cách này không phù hợp. Bên cạnh đó, cách xây dựng này sẽ lãng phí bộ nhớ trong trường hợp đồ thị thưa (có rất ít cạnh).
• Danh sách kề L là một danh sách với số phần tử là số đỉnh của đồ thị. Mỗi đỉnh i lại có một danh sách L[i] chứa các đỉnh kề với đỉnh i. Với đồ thị có hướng thì có thể xảy ra trường hợp đỉnh j thuộc L[i] nhưng đỉnh i không thuộc L[j]. Với đồ thị có trọng số thì có thể đưa thêm một trường dữ liệu số thực vào mỗi phần tử thuộc L[i] để biểu diễn giá trị của mối liên hệ giữa đỉnh i và đỉnh j. Quá trình xây dựng danh sách kề biểu diễn đồ thị được tiến hành như sau:
  • Định nghĩa ĐỈNH là kiểu dữ liệu chứa nhiều trường, trong đó có một trường cho phép trỏ đến một biến khác cũng có kiểu ĐỈNH (kiểu dữ liệu đệ quy). Một số trường còn lại được dùng để chứa các dữ liệu liên quan đến đỉnh và cạnh.
  • L và L[i] là các danh sách liên kết (xt. Cấu trúc dữ liệu tuyến tính) cấp phát động với các phần tử của danh sách có kiểu ĐỈNH.

Với cách xây dựng danh sách kề như trên, các phép toán liên quan đến đỉnh sẽ dễ dàng thực hiện dưới dạng thêm hoặc gỡ phần tử khỏi danh sách liên kết. Tuy nhiên, để truy cập vào giá trị của một đỉnh hoặc một cạnh đôi khi cần phải tiến hành việc duyệt qua nhiều phần tử khác trong danh sách.

Một số bài toán cơ bản sử dụng cấu trúc dữ liệu đồ thị:

• Duyệt: lần lượt đi qua (thăm) toàn bộ các đỉnh của đồ thị. Quá trình duyệt bắt đầu từ một đỉnh gọi là đỉnh xuất phát và kết thúc khi toàn bộ các đỉnh của đồ thị được thăm hoặc có thể kết thúc sớm khi thăm một đỉnh thỏa mãn một điều kiện nào đó. Hai phương pháp duyệt đồ thị phổ biến nhất là duyệt theo chiều rộng và duyệt theo chiều sâu;
• Tìm đường: xuất phát từ một đỉnh đầu tìm cách đi qua các cạnh/cung hoặc qua các đỉnh trung gian sao cho thỏa mãn một điều kiện nào đó. Trường hợp đỉnh xuất phát và đỉnh đích trùng nhau, bài toán tìm đường trở thành bài toán tìm chu trình;
• Tìm thành phần: tìm một tập con các đỉnh và các cạnh của đồ thị ban đầu sao cho thỏa mãn một số điều kiện nào đó, ví dụ: các đỉnh đều kề với nhau, giữa hai đỉnh bất kì luôn có đường đi nối giữa chúng;
• Gán nhãn: là quá trình gán các ký hiệu cho các cạnh hoặc các đỉnh của đồ thị thỏa mãn một điều kiện nào đó, ví dụ: các đỉnh kề nhau không cùng ký hiệu, các cạnh có chung đỉnh đầu mút không cùng ký hiệu.

Cây

Cây bao gồm một nút gốc và các nút con của nút gốc đó, trong đó nút con lại có thể là nút gốc của một cây khác (gọi là cây con). Nút không có nút con được gọi là nút lá. Giữa nút gốc và nút con được là mối quan hệ cha con. Các nút con của cùng một nút gốc được gọi là các nút anh em. Số nút con tối đa của một nút được gọi là bậc của cây. Cây được dùng để mô tả mối quan hệ có phân cấp giữa các thực thể.

Về mặt tổng quát, cây cũng chính là một đồ thị với khái niệm nút tương ứng với khái niệm đỉnh, mối quan hệ cha-con được thể hiện qua các cạnh. Như vậy, cây là một đồ thị mà phải thỏa mãn các điều kiện sau: giữa hai cặp đỉnh chỉ có thể có tối đa một cạnh, luôn có đường đi nối hai đỉnh bất kỳ nhưng không được chứa chu trình.

Cây nhị phân là một trong những cấu trúc dữ liệu phi tuyến có nhiều ứng dụng nhất trong thực tế. Cây nhị phân là cây có bậc bằng 2, các nút con được chia thành nút con trái và nút con phải, tương ứng với đó là các khái niệm cây con trái và cây con phải.

Cây không phải là cấu trúc dữ liệu được xây dựng sẵn trong các ngôn ngữ bậc cao. Cách phổ biến nhất để xây dựng cây bậc A là biểu diễn các nút bằng một kiểu dữ liệu đệ qui như sau:

• Định nghĩa NÚT là kiểu dữ liệu chứa nhiều trường;
• Trong NÚT có A trường cho phép trỏ đến các biến khác cũng có kiểu NÚT, dùng để chứa địa chỉ của các nút con;
• Các trường còn lại của NÚT dùng để lưu giá trị khóa và các dữ liệu khác (nếu cần).

Ví dụ, với cây nhị phân, NÚT có 3 trường dữ liệu: khóa và hai con trỏ (chứa địa chỉ của nút con trái và nút con phải tương ứng).

Các phép toán cơ bản với cây:

• Thêm nút: thêm nút A vào cây dưới dạng nút con của nút B. Trong trường hợp B là nút lá thì A sẽ là nút lá, ngược lại, nếu B đã có nút con thì sẽ xảy ra hai trường hợp sau:
  • A là nút anh em của các nút con đã có của B,
  • A là nút cha của một số hoặc toàn bộ nút con đã có của B.
• Bỏ nút: bỏ một nút ra khỏi cây, nếu nút bị bỏ không phải là nút là thì một nút con sẽ được đưa lên chèn vào vị trí của nút bị bỏ.
• Xoay cây: là quá trình chuyển nút con thành nút cha và ngược lại. Do vậy, có thể làm giảm chiều cao của cây con bên trái hoặc cây con bên phải của nút đi một đơn vị.

Kiểu dữ liệu đệ qui NÚT trình bày phía trên được sử dụng phổ biến nhất để biểu diễn cây vì nó hỗ trợ tốt nhất việc cài đặt các phép toán cơ bản. Bên cạnh đó, còn một số cách biểu diễn khác như:

• Sử dụng các phương pháp biểu diễn đồ thị. Tuy nhiên cách này khá tổng quát và chung chung, không hỗ trợ hiệu quả việc cài đặt các phép toán cơ bản.
• Cây nhị phân còn có thể được biểu diễn bằng mảng một chiều (đánh chỉ số từ 0) theo nguyên tắc: nếu nút có chỉ số là i, thì nút con trái và nút con phải sẽ lần lượt có chỉ số là 2i và 2i+1, còn nút cha có chỉ số là [i/2]. Cách này có hiệu quả khi cấu trúc cây là tĩnh, chỉ xây dựng một lần và không có những thay đổi về sau.

Bài toán cơ bản nhất được thực hiện với cấu trúc dữ liệu kiểu cây là bài toán tìm kiếm sự xuất hiện nút chứa một từ khóa cụ thể. Quá trình tìm kiếm được thực hiện thông qua duyệt cây, tương tự như duyệt đồ thị. Trong một số trường hợp đặc biệt, với cây nhị phân có thể quan tâm đến thứ tự thăm nút và thứ tự xử lý từ khóa của nút, từ đó dẫn đến các phương pháp duyệt khác như: duyệt trước, duyệt giữa và duyệt sau.

Một số cấu trúc cây đặc biệt được phát triển để tối ưu hóa việc tìm kiếm nút chứa từ khóa cụ thể từ trong danh mục bao gồm N khóa khác nhau:

• Cây nhị phân tìm kiếm: cây nhị phân trong đó mọi nút thuộc cây con trái đều có giá trị khóa nhỏ hơn giá trị khóa của nút gốc, mọi nút thuộc cây con phải đều có giá trị khóa lớn hơn giá trị khóa của nút gốc. Quá trình thêm nút vào cây nhị phân được thực hiện bằng cách lần lượt đi theo từng nhánh dựa trên việc so sánh giá trị khóa với các nút đã có, cho đến khi tới một nút lá. Nút mới sẽ được thêm vào dưới dạng nút con trái hoặc phải của nút lá tìm được. Để bảo đảm quá trình tìm kiếm luôn có độ phức tạp tính toán là O (logN). một số biến thể sau của cây nhị phân tìm kiếm đã được nghiên cứu và phát triển như: cây đỏ-đen, cây AVL, cây 2-3-4.
• Cây B và Cây B+: các cấu trúc dữ liệu chuyên dùng cho việc lưu trữ tại bộ nhớ ngoài. Quá trình xây dựng cây hướng tới việc giảm thiểu quá trình truy cập vào các nút trong quá trình tìm kiếm.
• Cây Q, Cây R và Cây k-d: các cấu trúc cây được thiết kế cho việc biểu diễn sự phân cấp các phần tử dựa trên nhiều chiều dữ liệu khác nhau, ví dụ: các dữ liệu đa phương tiện, các dữ liệu không gian. Chức năng chủ yếu của các cấu trúc này là cho phép truy vấn dựa trên khoảng cách giữa các điểm, các vùng được thực hiện một cách nhanh nhất có thể.

Ứng dụng và phát triển

Cấu trúc dữ liệu phi tuyến dạng đồ thị được dùng để biểu diễn sự phụ thuộc của các thực thể thuộc rất nhiều lĩnh vực, vd.:

• Biểu diễn sự phụ thuộc lẫn nhau của các công đoạn trong một qui trình hay của các môn trong chương trình học;
• Biểu diễn mạng máy tính, mạng lưới cung cấp năng lượng;
• Biểu diễn bản đồ, tuyến đường;
• Biểu diễn các mối liên hệ trong mạng xã hội;
• Biểu diễn các cấu trúc sinh học, vật chất di truyền.

Cấu trúc dữ liệu phi tuyến không được cung cấp bởi các ngôn ngữ lập trình bậc cao như một kiểu dữ liệu sẵn có. Chúng được xây dựng dựa trên các kiểu dữ liệu cơ bản có sẵn và phụ thuộc vào khả năng của ngôn ngữ lập trình.

Cách xây dựng đồ thị dựa trên mảng hai chiều được sử dụng xuyên suốt quá trình phát triển của các ngôn ngữ lập trình bậc cao và gần như không có gì thay đổi.

Cách xây dựng đồ thị dựa trên danh sách kề và xây dựng cây sử dụng kiểu dữ liệu đệ qui chủ yếu dựa trên việc biểu diễn danh sách liên kết của các ngôn ngữ. Với C hoặc Pascal, quá trình xây dựng này dựa trên việc sử dụng con trỏ và cấp phát động. Người lập trình phải tự cài đặt các thao tác cơ bản như thêm nút, gỡ nút,... và tiến hành việc quản lý bộ nhớ tương ứng. Một số ngôn ngữ ra đời muộn hơn gián tiếp trợ giúp việc xây dựng các lớp biểu diễn đồ thị hoặc cây bằng một số cách sau:

• Cung cấp những lớp biểu diễn danh sách liên kết trong thư viện lập trình như STL của C++, Java Collections Framework;
• Cung cấp các lớp dữ liệu xây dựng sẵn cho phép tiến hành linh hoạt việc thêm bớt dữ liệu vào các tập hợp có sẵn như dictionary, set của Python.

Với dữ liệu đầu vào như trên, các giải thuật xử lý các bài toán duyệt, tìm đường, tìm thành phần, gán nhãn được dùng trong việc phát triển các ứng dụng giải quyết hầu hết các vấn đề phục vụ cho mục đích quản lý, điều hành, nghiên cứu khoa học, ví dụ:

• Dẫn đường, định hướng;
• Lập kế hoạch điều khiển các đài quan sát không gian, quá trình in mạch điện tử;
• Lên lịch thi, lịch làm việc.

Cấu trúc dữ liệu phi tuyến dạng cây được dùng để biểu diễn các dữ liệu có phân cấp, phân nhánh, phân loại, thừa kế như sơ đồ chức năng của một tổ chức, cây phả hệ,… Ứng dụng tiêu biểu nhất của cây là sử dụng để đánh chỉ mục, trợ giúp các thao tác tìm kiếm, liệt kê. Đặc biệt, một số cấu trúc được thiết kế để tối ưu cho việc lưu trữ bộ nhớ ngoài (cây B và B+) hoặc dữ liệu nhiều chiều, ứng dụng trong các ứng dụng đa phương tiện, định vị không gian (cây Q, cây R và cây k-d).

Bên cạnh đó, cây được sử dụng để phân tích cú pháp, xây dựng các cấu trúc trung gian cho các giải thuật nén hoặc giải nén dữ liệu (Huffman, Lempel-Zip) hoặc trợ giúp ra quyết định.

Cấu trúc dữ liệu phi tuyến tiếp tục được nghiên cứu và phát triển mạnh mẽ trong hiện tại và tương lai, đặc biệt tập trung vào việc biểu diễn dữ liệu của các lĩnh vực đang là xu thế của giai đoạn đầu thế kỉ XXI như mạng xã hội, dữ liệu di truyền, bản đồ tiến hóa, … Bên cạnh đó, các nghiên cứu cũng tập trung vào việc phân tán và song song hóa quá trình lưu trữ, xử lý để có thể bắt kịp sự gia tăng liên tục của dữ liệu và xu thế ứng dụng của điện toán đám mây, của các bộ vi xử lý nhiều lõi trong các hệ thống tính toán hiện đại.

Về mặt học thuật, cấu trúc dữ liệu phi tuyến là nội dung cơ bản trong chương trình đào tạo kỹ sư, cử nhân công nghệ thông tin và khoa học máy tính, ở cả mức độ cơ bản và nâng cao. Về mặt ứng dụng, các cấu trúc dữ liệu phi tuyến được ứng dụng rộng rãi để xây dựng lên rất nhiều ứng dụng, tiêu biểu như: lập lịch, tìm đường, lưu trữ cơ sở dữ liệu đa chiều, xử lý dữ liệu đa phương tiện, xử lý dữ liệu không gian.

Tài liệu tham khảo

1. Donald E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd Edition, Addison-Wesley (1997). ISBN 978-0201896831
2. Niclaus Wirth, Algorithms + Data structures = Programs, Prentice-Hall, Inc (1976). ISBN 0-13-022418-9
3. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, MIT Press, Second Edition (2001). ISBN 978-0262032933