Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 6: Cây nhị phân tìm kiếm (Binary Search Trees) - Nguyễn Mạnh Hiển

Cây nhị phân tìm kiếm (Binary Search Trees) Nguyễn Mạnh Hiển [email protected] Đị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 sau Cài đặt template // 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út struct 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ỗng BinarySearchTree() { 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ây void 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 public T 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 public T 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 public bool contains(T x) { return contains(x, root); // gọi hàm private } // Hàm private trợ giúp bool contains(T x, BinaryNode * t) { if (t == NULL) return false; else if (x 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 5 Cà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 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óa Xóa nút có hai con Trước khi xóa 2 Sau khi xóa 2 Cách xóa: Thay nút bị xóa bằng nút nhỏ nhất của cây con phải 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) { ... // 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 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 3 1 2 5 3 1 6 9 7 8 0 6 4 2 Chứng minh d = O(log N) (2) • Nếu cây con trái của nút gốc có i nút: D(N) = D(i) + D(N-i-1) + N-1 D(i) là độ dài đường đi bên trong của cây con trái D(N-i-1) là độ dài đường đi bên trong của cây con phải Độ dài đường đi của mỗi nút trong cả hai cây con được cộng thêm 1 khi tính từ nút gốc của toàn cây 2 5 1 7 9 8 3 2 2 5 1 7 9 8 11 6 Chứng minh d = O(log N) (3) Gốc Cây con có N-1 nút Tính giá trị trung bình của D(N) theo kiểu đệ quy: D(1) = 0 D(N) = 1/N i=0 N-1 [ D(i) + D(N-i-1) ] + N - 1 = 2/N i=0 N-1 D(i) + N - 1 Gốc Cây con có N-2 nút Cây con có 1 nút Gốc Cây con có N-3 nút Cây con có 2 nút Chứng minh d = O(log N) (4) D(N) = 2/N i=0 N-1 D(i) + N - 1 ND(N) = 2 i=0 N-1 D(i) + N(N-1) (1) (N-1)D(N-1) = 2 i=0 N-2 D(i) + (N-1)(N-2) (2) Lấy (1) trừ (2) theo từng vế, ta có: ND(N) - (N-1)D(N-1) = 2D(N-1) + 2(N-1) ND(N) = (N+1)D(N-1) + 2(N-1) D(N)/(N+1) = D(N-1)/N + 2(N-1)/[N(N+1)] < D(N-1)/N + 2/N D(N)/(N+1) < D(N-1)/N + 2/N D(N-1)/(N) < D(N-2)/(N-1) + 2/(N-1) D(N-2)/(N-1) < D(N-3)/(N-2) + 2/(N-2) ... D(2)/3 < D(1)/2 + 2/2 Chứng minh d = O(log N) (5) D(N)/(N+1) < D(N-1)/N + 2/N < D(N-2)/(N-1) + 2/(N-1) + 2/N < D(N-3)/(N-2) + 2/(N-2) + 2/(N-1) + 2/N ... < D(1)/(2) + 2/2 + ... + 2/(N-2) + 2/(N-1) + 2/N = 2 i=2 N 1/i Nếu ta chứng minh được i=2 N 1/i = O(logN) thì sẽ suy ra độ sâu trung bình của một nút là d = D(N)/N  D(N)/(N+1) = O(log N) D(N)/(N+1) < D(N-1)/N + 2/N D(N-1)/(N) < D(N-2)/(N-1) + 2/(N-1) D(N-2)/(N-1) < D(N-3)/(N-2) + 2/(N-2) ... D(2)/3 < D(1)/2 + 2/2 Chứng minh d = O(log N) (6) 1 2 3 4 1/ 2 f(x) = 1/x 1/ 3 1/ 4 Diện tích của các hình chữ nhật < diện tích dưới 1/x i=2 4 1/i < ∫1 4 1/x dx i=2 N 1/i < ∫1 N 1/x dx = ln N - ln 1 = O(logN)