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 - Nguyễn Mạnh Hiển (HKI năm 2020-2021)
Số trang: 26
Loại file: pdf
Dung lượng: 921.80 KB
Lượt xem: 7
Lượt tải: 0
Xem trước 3 trang đầu tiên của tài liệu này:
Thông tin tài liệu:
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 bạn đọc những kiến thức về khái niệm cây nhị phân tìm kiếm, các thao tác trên cây nhị phân tìm kiếm, một vài ví dụ sử dụng cây nhị phân tìm kiếm.
Nội dung trích xuất từ tài liệu:
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 - Nguyễn Mạnh Hiển (HKI năm 2020-2021)Cây nhị phân tìm kiếm(Binary Search Trees)Nguyễn Mạnh Hiểnhiennm@tlu.edu.vnĐịnh nghĩa• Giả thiết các giá trị trên cây 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 đặttemplate // 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útstruct BinaryNode { T elem; // Phần tử BinaryNode * left; // Con trỏ tới con trái BinaryNode * right; // Con trỏ tới con phải // Hàm tạo của cấu trúc BinaryNode. BinaryNode(T x, BinaryNode * l, BinaryNode * r) { elem = x; // Khởi tạo trường phần tử left = l; // Khởi tạo trường con trỏ trái right = r; // Khởi tạo trường con trỏ phải }};Hàm tạo, hàm hủy, xóa rỗngBinarySearchTree() { root = NULL; // Ban đầu cây rỗng}~BinarySearchTree() { makeEmpty(); // Xóa hết các nút trên cây}void makeEmpty() { // Hàm xóa rỗng cây makeEmpty(root); // Gọi hàm private trợ giúp (slide sau)}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 việc xóa rỗng cây, viết theo// kiểu đệ quy.void makeEmpty(BinaryNode * & t) { Có dấu & trước t vì sẽ gán giá trị mới cho t trong thân hàm. if (t == NULL) return; // Thoát ra nếu cây rỗng makeEmpty(t->left); // Xóa rỗng cây con trái makeEmpty(t->right); // Xóa rỗng cây con phải delete t; // Xóa nút gốc t = NULL; // Cây đã rỗng tức là không tồn tại gốc}Tìm phần tử nhỏ nhất// Hàm public.T findMin() { BinaryNode * v = findMin(root); // Gọi hàm private return v->elem; // Lấy ra phần tử nhỏ nhất và trả về}// Hàm private trợ giúp (dùng đệ quy).// Phần tử nhỏ nhất nằm ở nút ngoài cùng bên trái của cây.BinaryNode * findMin(BinaryNode * t) { if (t == NULL) // Cây rỗng? return NULL; if(t->left == NULL) // Nút ngoài cùng bên trái? return t; return findMin(t->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->elem; // Lấy ra phần tử lớn nhất và trả về}// Hàm private trợ giúp (dùng vòng lặp thay cho đệ quy).// Phần tử lớn nhất nằm ở nút ngoài cùng bên phải của cây.BinaryNode * findMax(BinaryNode * t) { if (t != NULL) while (t->right != NULL) // Chưa đến tận cùng? t = t->right; // Đi tiếp sang bên phải return t;}Tìm phần tử x// Hàm public.bool contains(T x) { return contains(x, root); // Gọi hàm private}// Hàm private trợ giúp, tìm x trên cây có gốc t.bool contains(T x, BinaryNode * t) { if (t == NULL) // Cây rỗng tức là không tìm được return false; else if (x < t->elem) // Nếu x nhỏ hơn giá trị đang xét thì return contains(x, t->left); // tìm x ở bên trái. else if (x > t->elem) // Nếu x lớn hơn giá trị đang xét thì return contains(x, t->right); // tìm x ở bên phải. else // Gặp x return true;}Chèn phần tử Trước khi chèn 5 Sau khi chèn 5Cài đặt thao tác chèn// Hàm public (chèn x vào cây).void insert(T x) { insert(x, root); // Gọi hàm private Có dấu &} trước t vì sẽ gán giá trị mới// Hàm private trợ giúp (chèn x vào cây có gốc t). cho t trongvoid insert(T x, BinaryNode * & t) { thân hàm. if (t == NULL) // Cây rỗng thì tạo nút mới chứa x t = new BinaryNode(x, NULL, NULL); else if (x < t->elem) // Nếu x nhỏ hơn giá trị đang xét insert(x, t->left); // thì chèn x vào cây con trái else if (x > t->elem) // Nếu x lớn hơn giá trị đang xét insert(x, t->right); // thì chèn x vào cây con phải else // Gặp x thì không làm gì cả ; // Câu lệnh rỗng}Xóa nút lá Trước khi xóa 3 Sau khi xóa 3 Cách xóa: Chỉ đơn giản xóa nút đó.Xóa nút chỉ có một con Trước khi xóa 4 Sau khi xóa 4Cách xóa: Trước khi xóa, cho nút cha trỏ tới nút con của nút bị xóa.Xóa nút có hai con Trước khi xóa 2 Sau khi xóa 2Cách xóa: Thay nút bị xóa (2) bằng nút nhỏ nhất trên cây con phải (3).Sau đó, xóa nút nhỏ nhất trên cây con phải (là nút lá hoặc nút một con).Cài đặt thao tác xóa// Hàm public (xóa x khỏi cây).void remove(T x) { remove(x, root); // Gọi hàm private}// Hàm private trợ giúp (xóa x khỏi cây có gốc t).void remove(T x, BinaryNode * & t) { Có dấu & trước t vì sẽ ... // Xem code ở slide sau gán giá trị mới cho t} trong thân hàm. Cài đặt thao tác xóa (tiếp)void remove(T x, BinaryNode * & t) { if (t == NULL) return; // Thoát ra nếu cây rỗng. if (x < t->elem) // Nếu x nhỏ hơn giá trị đang xét thì remove(x, t->left); // xóa x ở cây con trái. else if (x > t->elem) // Nếu x lớn hơn giá trị đang xét thì ...
Nội dung trích xuất từ tài liệu:
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 - Nguyễn Mạnh Hiển (HKI năm 2020-2021)Cây nhị phân tìm kiếm(Binary Search Trees)Nguyễn Mạnh Hiểnhiennm@tlu.edu.vnĐịnh nghĩa• Giả thiết các giá trị trên cây 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 đặttemplate // 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útstruct BinaryNode { T elem; // Phần tử BinaryNode * left; // Con trỏ tới con trái BinaryNode * right; // Con trỏ tới con phải // Hàm tạo của cấu trúc BinaryNode. BinaryNode(T x, BinaryNode * l, BinaryNode * r) { elem = x; // Khởi tạo trường phần tử left = l; // Khởi tạo trường con trỏ trái right = r; // Khởi tạo trường con trỏ phải }};Hàm tạo, hàm hủy, xóa rỗngBinarySearchTree() { root = NULL; // Ban đầu cây rỗng}~BinarySearchTree() { makeEmpty(); // Xóa hết các nút trên cây}void makeEmpty() { // Hàm xóa rỗng cây makeEmpty(root); // Gọi hàm private trợ giúp (slide sau)}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 việc xóa rỗng cây, viết theo// kiểu đệ quy.void makeEmpty(BinaryNode * & t) { Có dấu & trước t vì sẽ gán giá trị mới cho t trong thân hàm. if (t == NULL) return; // Thoát ra nếu cây rỗng makeEmpty(t->left); // Xóa rỗng cây con trái makeEmpty(t->right); // Xóa rỗng cây con phải delete t; // Xóa nút gốc t = NULL; // Cây đã rỗng tức là không tồn tại gốc}Tìm phần tử nhỏ nhất// Hàm public.T findMin() { BinaryNode * v = findMin(root); // Gọi hàm private return v->elem; // Lấy ra phần tử nhỏ nhất và trả về}// Hàm private trợ giúp (dùng đệ quy).// Phần tử nhỏ nhất nằm ở nút ngoài cùng bên trái của cây.BinaryNode * findMin(BinaryNode * t) { if (t == NULL) // Cây rỗng? return NULL; if(t->left == NULL) // Nút ngoài cùng bên trái? return t; return findMin(t->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->elem; // Lấy ra phần tử lớn nhất và trả về}// Hàm private trợ giúp (dùng vòng lặp thay cho đệ quy).// Phần tử lớn nhất nằm ở nút ngoài cùng bên phải của cây.BinaryNode * findMax(BinaryNode * t) { if (t != NULL) while (t->right != NULL) // Chưa đến tận cùng? t = t->right; // Đi tiếp sang bên phải return t;}Tìm phần tử x// Hàm public.bool contains(T x) { return contains(x, root); // Gọi hàm private}// Hàm private trợ giúp, tìm x trên cây có gốc t.bool contains(T x, BinaryNode * t) { if (t == NULL) // Cây rỗng tức là không tìm được return false; else if (x < t->elem) // Nếu x nhỏ hơn giá trị đang xét thì return contains(x, t->left); // tìm x ở bên trái. else if (x > t->elem) // Nếu x lớn hơn giá trị đang xét thì return contains(x, t->right); // tìm x ở bên phải. else // Gặp x return true;}Chèn phần tử Trước khi chèn 5 Sau khi chèn 5Cài đặt thao tác chèn// Hàm public (chèn x vào cây).void insert(T x) { insert(x, root); // Gọi hàm private Có dấu &} trước t vì sẽ gán giá trị mới// Hàm private trợ giúp (chèn x vào cây có gốc t). cho t trongvoid insert(T x, BinaryNode * & t) { thân hàm. if (t == NULL) // Cây rỗng thì tạo nút mới chứa x t = new BinaryNode(x, NULL, NULL); else if (x < t->elem) // Nếu x nhỏ hơn giá trị đang xét insert(x, t->left); // thì chèn x vào cây con trái else if (x > t->elem) // Nếu x lớn hơn giá trị đang xét insert(x, t->right); // thì chèn x vào cây con phải else // Gặp x thì không làm gì cả ; // Câu lệnh rỗng}Xóa nút lá Trước khi xóa 3 Sau khi xóa 3 Cách xóa: Chỉ đơn giản xóa nút đó.Xóa nút chỉ có một con Trước khi xóa 4 Sau khi xóa 4Cách xóa: Trước khi xóa, cho nút cha trỏ tới nút con của nút bị xóa.Xóa nút có hai con Trước khi xóa 2 Sau khi xóa 2Cách xóa: Thay nút bị xóa (2) bằng nút nhỏ nhất trên cây con phải (3).Sau đó, xóa nút nhỏ nhất trên cây con phải (là nút lá hoặc nút một con).Cài đặt thao tác xóa// Hàm public (xóa x khỏi cây).void remove(T x) { remove(x, root); // Gọi hàm private}// Hàm private trợ giúp (xóa x khỏi cây có gốc t).void remove(T x, BinaryNode * & t) { Có dấu & trước t vì sẽ ... // Xem code ở slide sau gán giá trị mới cho t} trong thân hàm. Cài đặt thao tác xóa (tiếp)void remove(T x, BinaryNode * & t) { if (t == NULL) return; // Thoát ra nếu cây rỗng. if (x < t->elem) // Nếu x nhỏ hơn giá trị đang xét thì remove(x, t->left); // xóa x ở cây con trái. else if (x > t->elem) // Nếu x lớn hơn giá trị đang xét thì ...
Tìm kiếm theo từ khóa liên quan:
Cấu trúc dữ liệu Cấu trúc dữ liệu và giải thuật Bài giảng Cấu trúc dữ liệu Cây nhị phân tìm kiếm Xóa rỗng cây có gốc TGợi ý tài liệu liên quan:
-
Đề cương chi tiết học phần Cấu trúc dữ liệu và giải thuật (Data structures and algorithms)
10 trang 301 0 0 -
3 trang 156 3 0
-
Giáo trình Cấu trúc dữ liệu và giải thuật: Phần 2 - Trần Hạnh Nhi
123 trang 154 0 0 -
Giáo trình cấu trúc dữ liệu và giải thuât part 2
16 trang 154 0 0 -
Bài giảng Phân tích thiết kế phần mềm: Chương 1 - Trường ĐH Ngoại ngữ - Tin học TP.HCM
64 trang 145 0 0 -
Giải thuật và cấu trúc dữ liệu
305 trang 139 0 0 -
Tập bài giảng Thực hành kỹ thuật lập trình
303 trang 136 0 0 -
10 trang 136 0 0
-
Giáo trình Cấu trúc dữ liệu và thuật toán (Tái bản): Phần 1
152 trang 135 0 0 -
57 trang 117 1 0