Chào ace, bài này chúng ta sẽ tìm hiểu về Các ứng dụng của cấu trúc dữ liệu Tree trong series tự học về cấu trúc dữ liệu(CTDL) và giải thuật, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, độ phức tạp, ứng dụng của nó, code ví dụ…) về nó thông qua các phần sau.
Nội dung chính
1. Tại sao chúng ta sử dụng cấu trúc dữ liệu Tree?
Không giống như Array (mảng) và Linked List (danh sách liên kết), là các cấu trúc dữ liệu tuyến tính, Tree (cây) là cấu trúc dữ liệu dạng phân cấp (hoặc phi tuyến tính).
1. Một lý do để sử dụng Tree có thể là vì chúng ta muốn lưu trữ thông tin dưới dạng một hệ thống phân cấp tự nhiên. Ví dụ: Hệ thống tệp tin – file system trên máy tính.
file system <– root
———–
/ \
/ \
… home
/ \
ugrad course
/ / | \
… cs101 cs112 cs113
2. Nếu chúng ta tổ chức các keys (chính là phần giá trị/data mà mỗi node trong Tree sẽ chứa) dưới dạng một Tree (cây), thì chúng ta có thể tìm kiếm một key nhất định trong thời gian vừa phải (nhanh hơn so với Linked List và chậm hơn so với Array). Các cây nhị phân tìm kiếm tự cân bằng (Self-balancing search tree) giống như cây AVL và cây Red-Black có thể đảm bảo được giới hạn cận trên về độ phức tạp thời gian dành cho thao tác tìm kiếm là O(Log n).
3. Chúng ta có thể chèn thêm/xóa đi các keys trong thời gian vừa phải (nhanh hơn so với Array và chậm hơn so với Unordered Linked Lists – danh sách liên kết không có thứ tự). Các cây nhị phân tìm kiếm tự cân bằng giống như cây AVL và cây Red-Black có thể đảm bảo giới hạn cận trên về độ phức tạp thời gian dành cho thao tác chèn thêm node/xóa node là O(Log n).
4. Giống như Linked List và Array, Pointer Implementation – dạng thức cài đặt sử dụng các con trỏ của các cấu trúc dữ liệu Trees không hề có giới hạn cận trên nào về số lượng các nodes, bởi vì các nodes đều được liên kết với nhau bằng cách sử dụng các con trỏ.
2. Các ứng dụng khác
1. Lưu trữ dữ liệu phân cấp, như là folder structure – cấu trúc thư mục trên máy tính, organization structure – cấu trúc của một tổ chức cụ thể nào đó, dữ liệu XML/HTML.
2. Binary Search Tree – Cây nhị phân tìm kiếm là một cây mà cho phép thực hiện nhanh các thao tác tìm kiếm, chèn thêm node mới, xóa node, trên một dữ liệu đã được sắp xếp. Nó cũng cho phép tìm kiếm các phần tử gần nhất.
3. Heap là một cấu trúc dữ liệu dạng Tree (cây), được cài đặt bằng cách sử dụng các arrays (mảng), và được sử dụng để cài đặt các Priority Queues – Hàng đợi ưu tiên.
4. B-Tree và B+ Tree: Chúng được sử dụng để cài đặt tính năng indexing – đánh chỉ mục trong các databases (cơ sở dữ liệu).
5. Syntax Tree: Được sử dụng trong các Compilers (trình biên dịch).
6. K-D Tree: Đây là loại cấu trúc dữ liệu cây có khả năng phân vùng không gian, được sử dụng để tổ chức các điểm trong không gian K chiều.
7. Trie: Được sử dụng để cài đặt các dictionaries – từ điển, với khả năng tra cứu dựa trên tiền tố (prefix lookup).
8. Suffix Tree: Được sử dụng để tìm kiếm mẫu nhanh (quick pattern searching) trong một văn bản cố định.
9. Các Spanning Trees – cây mở rộng và các Shortest path trees – Cây đường đi ngắn nhất được sử dụng tương ứng trong những nhu cầu về định tuyến và khả năng cầu nối trong mạng máy tính.
10. Đóng vai trò như là một workflow (quy trình làm việc) trong quá trình hợp lại/ghép lại các hình ảnh kỹ thuật số nhằm tạo ra các hiệu ứng hình ảnh.
Nguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
- Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
- Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
- Các series tự học lập trình khác
Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:
Chào thân ái và quyết thắng!
 và giải thuật){kind=link}