CSD201 - Phần 4: Cây, cây tìm kiếm nhị phân, AVL và heap

Ứng với CLO4, buổi 15-28, là phần dài nhất của môn. Tương ứng Chương 8 và Chương 11 của Goodrich ấn bản 6. Phần cây tổng quát định nghĩa cây, gốc, cha, con, lá, độ sâu, chiều cao cùng kiểu dữ liệu trừu tượng cây. Phần cây nhị phân trình bày tính chất về số nút và chiều cao, các cách cài đặt, và bốn phép duyệt trước - giữa - sau - theo mức. Phần cây tìm kiếm nhị phân là trọng tâm: tính chất thứ tự, thao tác tìm kiếm, chèn, xoá với ba trường hợp nút lá, nút một con và nút hai con, tìm phần tử nhỏ nhất và lớn nhất, đếm số nút và tính chiều cao, cùng độ phức tạp của từng thao tác và lý do cây suy biến làm hỏng hiệu năng. Phần cây cân bằng giới thiệu cây AVL với hệ số cân bằng và bốn phép quay khi chèn hoặc xoá. Khép lại bằng heap, tính chất heap và ứng dụng làm hàng đợi ưu tiên.