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

Giảng viên:<br /> <br /> Văn Chí Nam – Nguyễn Thị Hồng Nhung – Đặng Nguyễn Đức Tiến<br /> <br /> 2<br /> <br /> Khái niệm<br /> <br /> Phép duyệt cây và Biểu diễn cây<br /> Cây nhị phân và Cây nhị phân tìm kiếm<br /> Cây AVL<br /> Cây AA<br /> Cấu trúc dữ liệu và giải thuật - HCMUS 2011<br /> <br /> ©FIT-HCMUS<br /> <br /> 1<br /> <br /> 3<br /> <br /> Cấu trúc dữ liệu và giải thuật - HCMUS 2011<br /> <br /> 4<br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> Tree<br /> Search tree<br /> Binary search tree<br /> Balanced tree<br /> AVL tree<br /> AA tree<br /> Red-Black tree<br /> …<br /> Cấu trúc dữ liệu và giải thuật - HCMUS 2011<br /> <br /> ©FIT-HCMUS<br /> <br /> 2<br /> <br /> 5<br /> <br /> a<br /> b<br /> d<br /> i<br /> <br /> e<br /> <br /> j<br /> o<br /> <br /> c<br /> f<br /> k<br /> <br /> p<br /> <br /> g<br /> l<br /> <br /> h<br /> m<br /> <br /> n<br /> <br /> q<br /> <br /> Cấu trúc dữ liệu và giải thuật - HCMUS 2011<br /> <br /> 6<br /> <br /> Sơ đồ tổ chức<br /> <br /> Cấu trúc dữ liệu và giải thuật - HCMUS 2011<br /> <br /> ©FIT-HCMUS<br /> <br /> Cây thư mục<br /> <br /> 3<br /> <br /> 7<br /> <br /> Cây (cây có gốc) được xác định đệ quy như<br /> sau:<br /> Tập hợp gồm 1 đỉnh là một cây. Cây này có gốc là<br /> đỉnh duy nhất của nó.<br /> 2. Gọi T1, T2, … Tk (k ≥ 1) là các cây không cắt nhau có<br /> gốc tương ứng r1, r2, … rk.<br /> Giả sử r là một đỉnh mới không thuộc các cây Ti. Khi đó,<br /> tập hợp T gồm đỉnh r và các cây Ti tạo thành một cây<br /> mới với gốc r. Các cây T1, T2, … Tk được gọi là cây<br /> con của gốc r.<br /> 1.<br /> <br /> Cấu trúc dữ liệu và giải thuật - HCMUS 2011<br /> <br /> 8<br /> <br /> Nút gốc<br /> <br /> r1<br /> <br /> r2<br /> <br /> rk<br /> <br /> T1<br /> <br /> T2<br /> <br /> Tk<br /> <br /> Cây con<br /> <br /> Cấu trúc dữ liệu và giải thuật - HCMUS 2011<br /> <br /> ©FIT-HCMUS<br /> <br /> 4<br /> <br /> 9<br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> node: đỉnh<br /> root: gốc cây<br /> leaf: lá<br /> inner node/internal node: đỉnh trong<br /> parent: đỉnh cha<br /> child: đỉnh con<br /> path: đường đi<br /> <br /> Cấu trúc dữ liệu và giải thuật - HCMUS 2011<br /> <br /> 10<br /> <br /> Nút gốc<br /> <br /> r1<br /> <br /> r2<br /> <br /> rk<br /> k1<br /> <br /> T1<br /> <br /> T2<br /> <br /> k2<br /> <br /> Tk<br /> k3<br /> <br /> k4<br /> <br /> k5<br /> <br /> Cây con<br /> Nút lá<br /> Cấu trúc dữ liệu và giải thuật - HCMUS 2011<br /> <br /> ©FIT-HCMUS<br /> <br /> Đường đi<br /> <br /> k6<br /> <br /> 5<br /> <br />