Cây DSA
Cây
Cấu trúc dữ liệu Cây tương tự như Danh sách liên kết ở chỗ mỗi nút chứa dữ liệu và có thể được liên kết với các nút khác.
Trước đây chúng ta đã đề cập đến các cấu trúc dữ liệu như Mảng, Danh sách liên kết, Ngăn xếp và Hàng đợi. Đây đều là các cấu trúc tuyến tính, có nghĩa là mỗi phần tử nối tiếp nhau trong một chuỗi. Tuy nhiên, cây cối thì khác. Trong Cây, một phần tử có thể có nhiều phần tử 'tiếp theo', cho phép cấu trúc dữ liệu phân nhánh theo nhiều hướng khác nhau.
Cấu trúc dữ liệu được gọi là "cây" vì nó trông giống như một cái cây, chỉ lộn ngược, giống như trong hình bên dưới.
Cấu trúc dữ liệu Cây có thể hữu ích trong nhiều trường hợp:
- Dữ liệu phân cấp: Hệ thống tệp, mô hình tổ chức, v.v.
- Cơ sở dữ liệu: Được sử dụng để truy xuất dữ liệu nhanh chóng.
- Bảng định tuyến: Được sử dụng để định tuyến dữ liệu trong các thuật toán mạng.
- Sorting/Searching: Dùng để sắp xếp dữ liệu và tìm kiếm dữ liệu.
- Hàng đợi ưu tiên: Cấu trúc dữ liệu hàng đợi ưu tiên thường được triển khai bằng cách sử dụng cây, chẳng hạn như đống nhị phân.
Thuật ngữ và quy tắc cây
Tìm hiểu các từ dùng để mô tả cấu trúc dữ liệu cây bằng cách sử dụng trực quan hóa cây tương tác bên dưới.
Nút đầu tiên trong cây được gọi là nút gốc .
Một liên kết kết nối nút này với nút khác được gọi là cạnh .
Nút cha có liên kết đến các nút con của nó. Một từ khác cho nút cha là nút nội bộ .
Một nút có thể có 0, một hoặc nhiều nút con.
Một nút chỉ có thể có một nút cha.
Các nút không có liên kết đến các nút con khác được gọi là nút lá hoặc nút lá .
Chiều cao của cây là số cạnh tối đa tính từ nút gốc đến nút lá. Chiều cao của cây trên là 2.
Chiều cao của một nút là số cạnh tối đa giữa nút đó và nút lá.
Kích thước cây là số nút trong cây.
Các loại cây
Cây là cấu trúc dữ liệu cơ bản trong khoa học máy tính, được sử dụng để thể hiện các mối quan hệ phân cấp. Hướng dẫn này bao gồm một số loại cây chính.
Cây nhị phân: Mỗi nút có tối đa hai nút con, nút con bên trái và nút con bên phải. Cấu trúc này là nền tảng cho các loại cây phức tạp hơn như Cây tìm kiếm Binay và Cây AVL.
Cây tìm kiếm nhị phân (BST): Một loại Cây nhị phân trong đó đối với mỗi nút, nút con bên trái có giá trị thấp hơn và nút con bên phải có giá trị cao hơn.
Cây AVL: Là một loại Cây tìm kiếm nhị phân tự cân bằng sao cho đối với mỗi nút, chênh lệch chiều cao giữa cây con trái và cây con phải nhiều nhất là một. Sự cân bằng này được duy trì thông qua các vòng quay khi các nút được chèn vào hoặc xóa đi.
Mỗi cấu trúc dữ liệu này được mô tả chi tiết trên các trang tiếp theo, bao gồm cả hoạt ảnh và cách triển khai chúng.
