Cây và thuật toán cây
Last updated
Was this helpful?
Last updated
Was this helpful?
Cây (tiếng Anh: tree) là một kiểu dữ liệu trừu tượng (ADT) hoặc một cấu trúc dữ liệu thực thi kiểu dữ liệu trừu tượng này, và được sử dụng để mô phỏng một tập hợp dữ liệu với bản chất của cấu trúc cây. Nó bao gồm n (n> = 1) nút hữu hạn để tạo thành một tập hợp phân cấp. Nó được gọi là "cây" bởi vì nó trông giống như một cái cây lộn ngược, có nghĩa là nó có rễ hướng lên trên và lá của nó hướng xuống. Nó có các đặc điểm sau:
Mỗi nút không có hoặc nhiều nút con;
Nút không có nút cha được gọi là nút gốc;
Mọi nút không gốc đều có một và chỉ một nút cha;
Ngoại trừ nút gốc, mỗi nút con có thể được chia thành nhiều cây con rời rạc;
Ví dụ:
Bậc nút : số lượng cây con chứa trong một nút được gọi là bậc của nút;
Độ cây : độ của nút lớn nhất trong cây được gọi là độ cây;
Nút lá hay nút cuối : nút có bậc bằng 0;
Nút cha hoặc nút cha : Nếu một nút chứa các nút con, nút này được gọi là nút cha của nút con của nó;
Nút con hay nút con : Nút gốc của cây con chứa trong một nút được gọi là nút con của nút;
Các nút anh chị em : các nút có cùng nút cha được gọi là các nút anh chị em;
Mức nút : bắt đầu từ định nghĩa của gốc, gốc là mức đầu tiên, các nút con của gốc là mức thứ hai, v.v.
Các chiều cao hoặc độ sâu của cây: mức tối đa của các nút trong cây;
Nút anh em họ : Các nút có nút cha trên cùng một lớp là anh em họ;
Tổ tiên của một nút : tất cả các nút trên nhánh từ gốc đến nút;
Con cháu : Bất kỳ nút nào trong cây con bắt nguồn từ một nút được gọi là con của nút.
Rừng : Tập hợp m (m> = 0) cây rời rạc được gọi là rừng;
Cây không có thứ tự : Không có quan hệ thứ tự giữa các nút con của bất kỳ nút nào trong cây, loại cây này được gọi là cây không có thứ tự, còn gọi là cây tự do;
Cây có thứ tự: Có mối quan hệ thứ tự giữa các nút con của bất kỳ nút nào trong cây, loại cây này được gọi là cây có thứ tự;
Cây nhị phân : Cây có nhiều nhất hai cây con trên mỗi nút được gọi là cây nhị phân;
Cây nhị phân hoàn chỉnh : Đối với cây nhị phân, giả sử độ sâu của nó là d (d> 1). Ngoại trừ lớp thứ d, số lượng nút ở các lớp khác đã đạt đến mức tối đa và tất cả các nút của lớp thứ d được sắp xếp chặt chẽ từ trái sang phải. Cây nhị phân như vậy được gọi là cây nhị phân hoàn chỉnh. Định nghĩa về cây nhị phân đầy đủ là tất cả các lá Một cây nhị phân hoàn chỉnh với các nút ở dưới cùng;
Cây nhị phân cân bằng ( cây AVL): Cây nhị phân có độ cao chênh lệch giữa hai cây con của bất kỳ nút nào không lớn hơn 1;
Sắp xếp cây nhị phân ( cây tìm kiếm nhị phân (tiếng Anh: Binary Search Tree) hay còn gọi là cây tìm kiếm nhị phân, cây nhị phân có thứ tự);
Cây Huffman (dùng để mã hóa thông tin): cây nhị phân với đường đi có trọng số ngắn nhất được gọi là cây Huffman hay cây nhị phân tối ưu;
B-tree : Cây tìm kiếm nhị phân tự cân bằng được tối ưu hóa cho các thao tác đọc và ghi, có thể giữ cho dữ liệu theo thứ tự và có nhiều hơn hai cây con.
Lưu trữ tuần tự: lưu trữ cấu trúc dữ liệu trong một mảng cố định có lợi thế nhất định về tốc độ truyền, nhưng nó là một cây nhị phân không chính thống vì nó chiếm một không gian tương đối lớn. Cây nhị phân thường được lưu trữ trong chuỗi.
Lưu trữ chuỗi:
Vì không thể nắm bắt được số lượng nút, các biểu diễn lưu trữ của cây chung được chuyển đổi thành cây nhị phân để xử lý và số lượng nút con nhiều nhất là 2
1. xml, html, v.v., khi biên dịch phân tích cú pháp những thứ này, không thể tránh khỏi việc sử dụng cây 2. Giao thức định tuyến sử dụng thuật toán cây 3. Chỉ mục cơ sở dữ liệu mysql 4. Cấu trúc thư mục của hệ thống tệp 5. Nhiều kinh điển Các thuật toán AI thực sự là tìm kiếm cây và cây quyết định trong học máy cũng là một cấu trúc cây
