Trong hướng dẫn này, bạn sẽ tìm hiểu về cấu trúc dữ liệu cây. Ngoài ra, bạn sẽ tìm hiểu về các loại cây khác nhau và các thuật ngữ được sử dụng trong cây.
Cây là một cấu trúc dữ liệu phân cấp phi tuyến bao gồm các nút được nối với nhau bằng các cạnh.
Một cái cây
Tại sao cấu trúc dữ liệu cây?
Các cấu trúc dữ liệu khác như mảng, danh sách liên kết, ngăn xếp và hàng đợi là cấu trúc dữ liệu tuyến tính lưu trữ dữ liệu một cách tuần tự. Để thực hiện bất kỳ hoạt động nào trong cấu trúc dữ liệu tuyến tính, độ phức tạp về thời gian tăng lên khi kích thước dữ liệu tăng lên. Nhưng, nó không thể được chấp nhận trong thế giới tính toán ngày nay.
Các cấu trúc dữ liệu cây khác nhau cho phép truy cập dữ liệu nhanh hơn và dễ dàng hơn vì nó là cấu trúc dữ liệu phi tuyến tính.
Thuật ngữ cây
Nút
Nút là một thực thể chứa khóa hoặc giá trị và con trỏ đến các nút con của nó.
Các nút cuối cùng của mỗi đường dẫn được gọi là nút lá hoặc nút bên ngoài không chứa liên kết / con trỏ đến các nút con.
Nút có ít nhất một nút con được gọi là nút bên trong .
Cạnh
Nó là liên kết giữa hai nút bất kỳ.
Các nút và các cạnh của cây
Nguồn gốc
Nó là nút trên cùng của cây.
Chiều cao của nút
Chiều cao của nút là số cạnh từ nút đến lá sâu nhất (tức là đường đi dài nhất từ nút đến nút lá).
Độ sâu của một nút
Độ sâu của một nút là số cạnh từ gốc đến nút.
Chiều cao của cây
Chiều cao của Cây là chiều cao của nút gốc hoặc chiều sâu của nút sâu nhất.
Chiều cao và chiều sâu của mỗi nút trong cây
Mức độ của một nút
Bậc của một nút là tổng số nhánh của nút đó.
rừng
Tập hợp các cây rời rạc được gọi là rừng.
Tạo rừng từ cây
Bạn có thể tạo một khu rừng bằng cách chặt rễ cây.
Các loại cây
- Cây nhị phân
- Cây tìm kiếm nhị phân
- Cây AVL
- Cây B
Traversal cây
Để thực hiện bất kỳ thao tác nào trên cây, bạn cần phải truy cập vào nút cụ thể. Thuật toán duyệt cây giúp truy cập một nút bắt buộc trong cây.
Để tìm hiểu thêm, vui lòng truy cập tree traversal.
Ứng dụng cây
- Cây tìm kiếm nhị phân (BST) được sử dụng để nhanh chóng kiểm tra xem một phần tử có trong một tập hợp hay không.
- Heap là một loại cây được sử dụng để sắp xếp đống.
- Một phiên bản sửa đổi của cây được gọi là Tries được sử dụng trong các bộ định tuyến hiện đại để lưu trữ thông tin định tuyến.
- Hầu hết các cơ sở dữ liệu phổ biến sử dụng B-Trees và T-Trees, là các biến thể của cấu trúc cây mà chúng ta đã học ở trên để lưu trữ dữ liệu của chúng
- Các trình biên dịch sử dụng một cây cú pháp để xác nhận cú pháp của mọi chương trình bạn viết.
