Danh mục

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    
Jamona

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ì ...

Tài liệu được xem nhiều: