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)

Chia sẻ: Minh Nhân | Ngày: | Loại File: PDF | Số trang:25

Thêm vào BST

Báo xấu

41
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ển hiennm@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 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 < 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 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 < 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ó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 < 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