Phần tiếp theo bài giảng "Cấu trúc dữ liệu và giải thuật: Cây nhị phân" cung cấp cho các bạn các kiến thức: Cây nhị phân tìm kiếm – Binary search tree, hàng đợi ưu tiên – Priority queue. nội dung chi tiết. | Bài giảng Cấu trúc dữ liệu và giải thuật: Cây nhị phân - Nguyễn Tri Tuấn (tt) Cây nhị phân Các khái niệm và thuật ngữ cơ bản Cài đặt cấu trúc dữ liệu Duyệt cây Cây nhị phân tìm kiếm – Binary Search Tree Hàng đợi ưu tiên – Priority Queue Winter 2017 85 (C) Nguyen Tri Tuan - Truong DHQG-HCM Cây nhị phân tìm kiếm (BST) Ý nghĩa của cây BST Binary Search Tree ADT Cài đặt cấu trúc dữ liệu BST Đánh giá/So sánh Bài tập Winter 2017 86 (C) Nguyen Tri Tuan - Truong DHQG-HCM Ý nghĩa của cây BST (1) Tìm 1 phần tử trong cây nhị phân ? Thuật toán ? Chi phí ? Winter 2017 87 (C) Nguyen Tri Tuan - Truong DHQG-HCM Ý nghĩa của cây BST (2) Điểm yếu và điểm mạnh của mảng ? Điểm yếu và điểm mạnh của danh sách liên kết ? Một cấu trúc dữ liệu có được cả điểm mạnh của mảng và danh sách liên kết ? Winter 2017 88 (C) Nguyen Tri Tuan - Truong DHQG-HCM Binary Search Tree ADT (1) Cây nhị phân tìm kiếm là: Một cây nhị phân Mỗi node có một khóa (key) Mỗi node p của cây đều thỏa: • Tất cả các node thuộc cây con trái đều có khóa nhỏ hơn khóa của p q p->left: q->key < p->key • Tất cả các node thuộc cây con phải đều có khóa lớn hơn khóa của p q p->right: q->key > p->key Winter 2017 89 (C) Nguyen Tri Tuan - Truong DHQG-HCM Binary Search Tree ADT (2) Winter 2017 90 (C) Nguyen Tri Tuan - Truong DHQG-HCM Binary Search Tree ADT (3) Winter 2017 91 (C) Nguyen Tri Tuan - Truong DHQG-HCM Binary .
