Cấu trúc dữ liệu phi tuyến tính bao gồm một tập hợp các phần tử được phân phối trên mặt phẳng, điều đó có nghĩa là không có trình tự như vậy giữa các phần tử khi nó tồn tại trong cấu trúc dữ liệu tuyến tính.
Biểu đồ so sánh
| Cơ sở để so sánh | Cây | Đồ thị |
|---|---|---|
| Con đường | Chỉ có một giữa hai đỉnh. | Nhiều hơn một con đường được cho phép. |
| Nút gốc | Nó có chính xác một nút gốc. | Đồ thị không có nút gốc. |
| Vòng lặp | Không có vòng lặp được cho phép. | Đồ thị có thể có các vòng lặp. |
| Phức tạp | Ít phức tạp hơn | Tương đối phức tạp hơn |
| Kỹ thuật truyền tải | Đặt hàng trước, theo thứ tự và sau đặt hàng. | Tìm kiếm theo chiều rộng và tìm kiếm theo chiều sâu. |
| Số cạnh | n-1 (trong đó n là số nút) | Không xác định |
| Kiểu mẫu | Thứ bậc | Mạng |
Định nghĩa của cây
Cây là một tập hợp hữu hạn của các mục dữ liệu thường được gọi là các nút. Như đã đề cập ở trên, cây là một cấu trúc dữ liệu phi tuyến tính, sắp xếp các mục dữ liệu theo thứ tự được sắp xếp. Nó được sử dụng để hiển thị cấu trúc phân cấp giữa các yếu tố dữ liệu khác nhau và sắp xếp dữ liệu thành các nhánh liên quan đến thông tin. Việc bổ sung một cạnh mới trong cây dẫn đến sự hình thành của vòng lặp hoặc mạch.
Có một số loại cây như cây nhị phân, cây tìm kiếm nhị phân, cây AVL, cây nhị phân luồng, cây B, v.v. Nén dữ liệu, lưu trữ tệp, thao tác biểu thức số học và cây trò chơi là một số ứng dụng của cây cấu trúc dữ liệu.
Tính chất của cây:
- Có một nút được chỉ định ở đầu cây được gọi là gốc của cây.
- Các mục dữ liệu còn lại được chia thành các tập hợp con khác nhau được gọi là cây con.
- Cây được mở rộng về chiều cao về phía dưới.
- Một cây phải được kết nối có nghĩa là phải có một đường dẫn từ một gốc đến tất cả các nút khác.
- Nó không chứa bất kỳ vòng lặp.
- Một cây có cạnh n-1.
Có nhiều thuật ngữ khác nhau liên quan đến cây như nút thiết bị đầu cuối, cạnh, cấp độ, mức độ, độ sâu, rừng, v.v ... Trong số các thuật ngữ đó, một số thuật ngữ được mô tả dưới đây.
- Cạnh - Một đường kết nối hai nút.
- Cấp độ - Một cây được phân chia thành các cấp sao cho nút gốc ở cấp 0. Sau đó, các con ngay lập tức của nó ở cấp 1, và các con ngay lập tức của nó ở cấp 2 và cứ thế đến nút đầu cuối hoặc nút lá.
- Độ - Đó là số lượng cây con của một nút trong một cây nhất định.
- Độ sâu - Đây là mức tối đa của bất kỳ nút nào trong một cây nhất định và còn được gọi là chiều cao .
- Nút đầu cuối - Nút cấp cao nhất là nút đầu cuối trong khi các nút khác ngoại trừ nút đầu cuối và nút gốc được gọi là nút không đầu cuối.
Định nghĩa đồ thị
Biểu đồ cũng là một cấu trúc dữ liệu phi tuyến tính toán học có thể biểu diễn các loại cấu trúc vật lý khác nhau. Nó bao gồm một nhóm các đỉnh (hoặc nút) và tập hợp các cạnh kết nối hai đỉnh. Các đỉnh trên biểu đồ được biểu diễn dưới dạng điểm hoặc đường tròn và cạnh được hiển thị dưới dạng vòng cung hoặc đường thẳng. Một cạnh được biểu diễn bởi E (v, w) trong đó v và w là các cặp đỉnh. Việc loại bỏ một cạnh khỏi một mạch hoặc đồ thị được kết nối sẽ tạo ra một sơ đồ con là một cái cây.
Các biểu đồ được phân loại thành các loại khác nhau như hướng, không định hướng, kết nối, không kết nối, đơn giản và đa biểu đồ. Mạng máy tính, hệ thống giao thông, đồ thị mạng xã hội, mạch điện và lập kế hoạch dự án là một số ứng dụng của cấu trúc dữ liệu đồ thị. Nó cũng được sử dụng trong kỹ thuật quản lý có tên là PERT (kỹ thuật đánh giá và đánh giá chương trình) và CPM (phương pháp đường dẫn quan trọng) trong đó cấu trúc biểu đồ được phân tích.
Thuộc tính của đồ thị:
- Một đỉnh trong đồ thị có thể được kết nối với bất kỳ số đỉnh khác bằng các cạnh.
- Một cạnh có thể được đặt giá thầu hoặc hướng.
- Một cạnh có thể có trọng số.
Trong biểu đồ, chúng tôi cũng sử dụng các thuật ngữ khác nhau như các đỉnh liền kề, đường dẫn, chu kỳ, độ, biểu đồ được kết nối, biểu đồ hoàn chỉnh, biểu đồ có trọng số, v.v ... Hãy hiểu một số thuật ngữ này.
- Các đỉnh liền kề - Một đỉnh a liền kề với đỉnh b nếu có cạnh (a, b) hoặc (b, a).
- Đường dẫn - Đường dẫn từ một đỉnh ngẫu nhiên w là một chuỗi các đỉnh liền kề.
- Chu kỳ - Đó là một con đường nơi các đỉnh đầu tiên và cuối cùng giống nhau.
- Độ - Đó là một số sự cố cạnh trên một đỉnh.
- Biểu đồ được kết nối - Nếu tồn tại một đường dẫn từ một đỉnh ngẫu nhiên đến bất kỳ đỉnh nào khác, thì biểu đồ đó được gọi là biểu đồ được kết nối.
Sự khác biệt chính giữa cây và đồ thị
- Trong một cây chỉ tồn tại một đường giữa hai đỉnh bất kỳ trong khi đồ thị có thể có các đường đơn hướng và hai chiều giữa các nút.
- Trong cây, có chính xác một nút gốc và mỗi đứa trẻ chỉ có thể có một cha mẹ. Đối với, trong một biểu đồ, không có khái niệm về nút gốc.
- Một cây không thể có các vòng lặp và tự lặp trong khi đồ thị có thể có các vòng lặp và các vòng lặp tự.
- Đồ thị phức tạp hơn vì nó có thể có các vòng lặp và các vòng lặp tự. Ngược lại, cây đơn giản so với biểu đồ.
- Cây được duyệt qua các kỹ thuật đặt hàng trước, theo thứ tự và sau khi đặt hàng. Mặt khác, để duyệt đồ thị, chúng tôi sử dụng BFS (Breadth First Search) và DFS (Depth First Search).
- Một cây có thể có các cạnh n-1. Ngược lại, trong biểu đồ, không có số cạnh được xác định trước và nó phụ thuộc vào biểu đồ.
- Một cây có cấu trúc phân cấp trong khi đồ thị có mô hình mạng.
Phần kết luận
Đồ thị và cây là cấu trúc dữ liệu phi tuyến tính được sử dụng để giải quyết các vấn đề phức tạp khác nhau. Biểu đồ là một nhóm các đỉnh và cạnh trong đó một cạnh kết nối một cặp đỉnh trong khi đó cây được coi là biểu đồ được kết nối tối thiểu phải được kết nối và không có vòng lặp.
