TAILIEUCHUNG - 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ử .

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• giải thuật
• phương pháp sắp xếp
• tổ chức dữ liệu
• t đề án tin họ
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• giáo trình cấu trúc dữ liệu
• bài tập cấu trúc dữ liệu
• đề cương cấu trúc dữ liệu
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Tài liệu Cấu trúc dữ liệu
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp