tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Cây nhị phân tìm kiếm - Phan Mạnh Hiển (2020)

Bài giảng "Cấu trúc dữ liệu và giải thuật: Cây nhị phân tìm kiếm" cung cấp cho người học các kiến thức: Định nghĩa, các thao tác chính, kiểu của các nút, hàm tạo, hàm hủy, xóa rỗng, xóa rỗng cây có gốc t, | Bài giảng Cấu trúc dữ liệu và giải thuật Cây nhị phân tìm kiếm - Phan Mạnh Hiển 2020 Cây nhị phân tìm kiếm Binary Search Trees Nguyễn Mạnh Hiển hiennm@ Định nghĩa Xét trường hợp các phần tử có giá trị khác nhau Cây nhị phân tìm kiếm là cây nhị phân trong đó với mọi nút X Tất cả các giá trị trên cây con trái của X nhỏ hơn X Tất cả các giá trị trên cây con phải của X lớn hơn X Đây có phải là cây nhị phân tìm kiếm Các thao tác chính Tìm phần tử nhỏ nhất Tìm phần tử lớn nhất Tìm phần tử x Chèn phần tử x Xóa phần tử x Tất cả các thao tác trên có thời gian chạy trung bình là O log N sẽ chứng minh sau Cài đặt template T là kiểu phần tử class BinarySearchTree public hàm tạo hàm hủy kiểm tra rỗng xóa rỗng cây tìm min tìm max tìm phần tử x chèn xóa phần tử x private struct BinaryNode . kiểu của các nút BinaryNode root con trỏ tới nút gốc các hàm trợ giúp Kiểu của các nút struct BinaryNode T elem BinaryNode left BinaryNode right BinaryNode T x BinaryNode l BinaryNode r elem x left l right r Hàm tạo hàm hủy xóa rỗng BinarySearchTree root NULL BinarySearchTree makeEmpty void makeEmpty hàm xóa rỗng cây makeEmpty root gọi hàm private trợ giúp bool isEmpty hàm kiểm tra rỗng return root NULL Xóa rỗng cây có gốc t Hàm private trợ giúp xóa rỗng cây void makeEmpty BinaryNode amp t if t NULL return thoát ra nếu cây rỗng makeEmpty t- gt left xóa cây con trái makeEmpty t- gt right xóa cây con phải delete t xóa nút gốc t NULL Tìm phần tử nhỏ nhất Hàm public T findMin BinaryNode v findMin root gọi hàm private return v- gt elem Hàm private trợ giúp dùng đệ quy BinaryNode findMin BinaryNode t if t NULL cây rỗng return NULL if t- gt left NULL nút ngoài cùng bên trái return t return findMin t- gt left tìm trên cây con trái Tìm phần tử lớn nhất Hàm public T findMax BinaryNode v findMax root gọi hàm private return v- gt elem Hàm private trợ giúp không dùng đệ quy BinaryNode findMax BinaryNode t if t NULL while t- gt right NULL chưa đến tận cùng t t- gt right đi tiếp sang bên phải .