tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc cây

Bài giảng "Cấu trúc dữ liệu và giải thuật: Cấu trúc cây" được biên soạn với các nội dung chính sau đây: Khái niệm cấu trúc cây; Phép duyệt cây và Biểu diễn cây; Cây nhị phân và Cây nhị phân tìm kiếm; Cây AVL; Cây AA. Mời các bạn cùng tham khảo bài giảng! | Cấu trúc dữ liệu và giải thuật Cấu trúc cây Giảng viên Văn Chí Nam Nội dung trình bày 2 Cấu trúc dữ liệu và giải thuật HCMUS 2011 3 Khái niệm Cấu trúc dữ liệu và giải thuật HCMUS 2011 Một số thuật ngữ 4 Tree Search tree Binary search tree Balanced tree AVL tree AA tree Red-Black tree Cấu trúc dữ liệu và giải thuật HCMUS 2011 Cây tổng quát 5 Cấu trúc dữ liệu và giải thuật HCMUS 2011 Cây tổng quát 6 Sơ đồ tổ chức Cây thư mục Cấu trúc dữ liệu và giải thuật HCMUS 2011 Định nghĩa 7 Cây cây có gốc được xác định đệ quy như sau 1. Tập hợp gồm 1 đỉnh là một cây. Cây này có gốc là đỉnh duy nhất của nó. 2. Gọi T1 T2 Tk k 1 là các cây không cắt nhau có gốc tương ứng r1 r2 rk. Giả sử r là một đỉnh mới không thuộc các cây Ti. Khi đó tập hợp T gồm đỉnh r và các cây Ti tạo thành một cây mới với gốc r. Các cây T1 T2 Tk được gọi là cây con của gốc r. Cấu trúc dữ liệu và giải thuật HCMUS 2011 Định nghĩa 8 r Nút gốc r r r 1 2 k T1 T2 Tk Cây con Cấu trúc dữ liệu và giải thuật HCMUS 2011 Các khái niệm 9 node đỉnh root gốc cây leaf lá inner node internal node đỉnh trong parent đỉnh cha child đỉnh con path đường đi Cấu trúc dữ liệu và giải thuật HCMUS 2011 Các khái niệm 10 r Nút gốc rk r r r 1 2 k k k 1 2 T1 T2 Tk k k k 3 4 5 Cây con Nút lá Đường đi k Cấu trúc dữ liệu và giải thuật HCMUS 2011 6 Các khái niệm 11 degree order bậc Bậc của node Số con của node Bậc của cây bậc lớn nhất trong số các con depth level độ sâu mức Mức độ sâu của node Chiều dài của đường đi từ node gốc đến node đó cộng thêm 1. height chiều cao Chiều cao cây Cấu trúc dCây rỗng ải thu 0 ật HCMUS 2011 ữ liệu và gi Các khái niệm 12 Bậc k r Nút gốc Bậc 2 Độ cao 4 rk r r r 1 2 k k k 1 2 T1 T2 Tk k k k 3 4 5 Cây con Nút lá Đường đi k Cấu trúc dữ liệu và giải thuật HCMUS 2011 6 13 Phép duyệt cây Cấu trúc dữ liệu và giải thuật HCMUS 2011 Phép duyệt cây 14 Đảm bảo đến mỗi node trên cây chính xác một lần một cách có hệ thống. Nhiều thao tác xử lý trên cây cần phải sử dụng đến phép duyệt cây. Các phép cơ bản Duyệt trước Pre .