tailieunhanh - Cấu trúc dữ liệu và giải thuật I - Bài 12

CÂY NHỊ PHÂN TÌM KIẾM Mục tiêu Tìm hiểu Cây Nhị phân Tìm kiếm Nội dung I. Cây Nhị phân tìm kiếm II. Các thao tác cơ bản trên cây nhị phân tìm kiếm cây một phần tử trên cây một phần tử vào cây một phần tử vào cây | BÀI 12 CÂY NHỊ PHÂN TÌM KIẾM Mục tiêu Tìm hiểu Cây Nhị phân Tìm kiếm Nội dung Cx Cây Nhị phân tìm kiếm da Các thao tác cơ bản trên cây nhị phân tìm kiếm cây i môt phần tử trên cây môt phần tử vào cây môt phần tử vào cây CĩnL Đánh giá cây nhị phân tìm kiếm Bài tập I. CÂY NHỊ PHÂN TÌM KIẾM Định nghĩa Cây nhị phân tìm kiếm CNPTK là cây nhị phân trong đó tại mỗi nút khóa của nút đang xét lớn hơn khóa của tất cả các nút thuộc cây con trái và nhỏ hơn khóa của tất cả các nút thuộc cây con phải. Dưới đây là một ví dụ về cây nhị phân tìm kiếm Nhờ ràng buộc về khóa trên CNPTK việc tìm kiếm trở nên có định hướng. Hơn nữa do cấu trúc cây việc tìm kiếm trở nên nhanh đáng kể. Nếu số nút trên cây là N thì chi phí tìm kiếm trung bình chỉ khoảng log2N. Trong thực tế khi xét đến cây nhị phân chủ yếu người ta xét CNPTK. II. CÁC THAO TÁC TRÊN CÂY NHỊ PHÂN TÌM KIẾM . Duyệt cây Thao tác duyệt cây trên cây nhị phân tìm kiếm hoàn toàn giống như trên cây nhị phân. Chỉ có một lưu ý nhỏ là khi duyệt theo thứ tự giữa trình tự các nút duyệt qua sẽ cho ta một dãy các nút theo thứ tự tăng dần của khóa. một phần tử x trong cây TNODE searchNode TREE T Data X if T if T- Key X return T if T- Key X return searchNode T- pLeft X else return searchNode T- pRight X return NULL Ta có thể xây dựng một hàm tìm kiếm tương đương không đệ qui như sau TNODE searchNode TREE Root Data x NODE p Root while p NULL if x p- Key return p else if x p- Key p p- pLeft else p p- pRight return NULL Dễ dàng thấy rằng số lần so sánh tối đa phải thực hiện để tìm phần tử X là h với h là chiều cao của cây. Như vậy thao tác tìm kiếm trên CNPTK có n nút tốn chi phí trung bình khoảng O log2n . Ví dụ Tìm phần tử .