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

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 bởi các giảng viên Văn Chí Nam, Nguyễn Thị Hồng Nhung và Đặng Nguyễn Đức Tiến trình bày về các nội dung: 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. Để biết rõ hơn về nội dung chi tiết, mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc cây - ĐHKHTNGiảng viên:Văn Chí Nam – Nguyễn Thị Hồng Nhung – Đặng Nguyễn Đức Tiến2Khái niệmPhép duyệt cây và Biểu diễn câyCây nhị phân và Cây nhị phân tìm kiếmCây AVLCây AACấu trúc dữ liệu và giải thuật - HCMUS 2011©FIT-HCMUS13Cấu trúc dữ liệu và giải thuật - HCMUS 20114TreeSearch treeBinary search treeBalanced treeAVL treeAA treeRed-Black tree…Cấu trúc dữ liệu và giải thuật - HCMUS 2011©FIT-HCMUS25abdiejocfkpglhmnqCấu trúc dữ liệu và giải thuật - HCMUS 20116Sơ đồ tổ chứcCấu trúc dữ liệu và giải thuật - HCMUS 2011©FIT-HCMUSCây thư mục37Cây (cây có gốc) được xác định đệ quy nhưsau: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âymới với gốc r. Các cây T1, T2, … Tk được gọi là câycon của gốc r.1.Cấu trúc dữ liệu và giải thuật - HCMUS 20118Nút gốcr1r2rkT1T2TkCây conCấu trúc dữ liệu và giải thuật - HCMUS 2011©FIT-HCMUS49node: đỉnhroot: gốc câyleaf: láinner node/internal node: đỉnh trongparent: đỉnh chachild: đỉnh conpath: đường điCấu trúc dữ liệu và giải thuật - HCMUS 201110Nút gốcr1r2rkk1T1T2k2Tkk3k4k5Cây conNút láCấu trúc dữ liệu và giải thuật - HCMUS 2011©FIT-HCMUSĐường đik65