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,.... Mời các bạn cùng tham khảo nội dung chi tiết.
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 - Phan Mạnh Hiển (2020)Cây nhị phân tìm kiếm(Binary Search Trees)Nguyễn Mạnh Hiểnhiennm@tlu.edu.vnĐị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 sauCà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; 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ỗngBinarySearchTree() { 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âyvoid makeEmpty(BinaryNode * & t) { if (t == NULL) return; // thoát ra nếu cây rỗng makeEmpty(t->left); // xóa cây con trái makeEmpty(t->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 publicT findMin() { BinaryNode * v = findMin(root); // gọi hàm private return v->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->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 publicT findMax() { BinaryNode * v = findMax(root); // gọi hàm private return v->elem;}// Hàm private trợ giúp (không dùng đệ quy)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 publicbool contains(T x) { return contains(x, root); // gọi hàm private}// Hàm private trợ giúpbool contains(T x, BinaryNode * t) { if (t == NULL) return false; else if (x < t->elem) return contains(x, t->left); else if (x > t->elem) return contains(x, t->right); else return true; // tìm được x}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}// Hàm private trợ giúp (chèn x vào cây có gốc t)void insert(T x, BinaryNode * & t) { if (t == NULL) t = new BinaryNode(x, NULL, NULL); else if (x < t->elem) insert(x, t->left); else if (x > t->elem) insert(x, t->right); else ; // gặp x; không làm gì cả}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 4 Cách xóa: Cho nút cha trỏ tới con của nút bị xóaXóa nút có hai conTrước khi xóa 2 Sau khi xóa 2Cách xóa: Thay nút bị xóa bằng nút nhỏ nhất của cây con phảiCà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) { ... // xem code ở slide sau}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) remove(x, t->left); // xóa ở cây con trái else if (x > t->elem) remove(x, t->right); // xóa ở cây con phải else if (t->left != NULL && t->right != NULL) { // 2 con t->elem = findMin(t->right)->elem; remove(t->elem, t->right); } else { // 1 con hoặc lá BinaryNode * old = t; t = (t->left != NULL) ? t->left : t->right; delete old; }}Phân tích thời gian chạy• Gọi N là tổng số nút trong cây• Gọi d là độ sâu trung bình của các nút• Thao tác xóa rỗng cây có thời gian chạy là O(N)• Các thao tác tìm/chèn/xóa có thời gian chạy trung bình là O(d) = O(log N), bao gồm: − Thời gian trung bình đi từ nút gốc tới nút v – nơi diễn ra thao tác – là O(d) − Thời gian xử lý thao tác tại nút v là O(1)• Tiếp theo, ta sẽ chứng minh d = O(log N)Chứng minh d = O(log N) (1)• Độ sâu trung bình của các nút: d = tổng-độ-sâu-của-các-nút / số-nút = D/N Tổng độ sâu của các nút được gọi là độ dài đường đi bên trong• Hãy tính độ dài đường đi bên trong của các cây sau: 2 2 2 6 0 1 3 9 1 5 2 7 3 4 8 6 ...