Bài giảng Phân tích và Thiết kế giải thuật nâng cao: Chương 3 - PGS.TS. Trần Cao Đệ

Chia sẻ: Lê Kim Luông | Ngày: | Loại File: PPT | Số trang:54

Thêm vào BST

Báo xấu

106
lượt xem 16
download

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

Bài giảng Phân tích và thiết kế thuật toán gồm 5 chương: Kỹ thuật phân tích giải thuật, kỹ thuật thiết kế giải thuật, cây cân bằng, giải thuật so khớp chuỗi, các giải thuật hình học, mật mã. Bài giảng sau đây sẽ giới thiệu môn học &kế hoạch hoàn thành môn học. Mời các bạn cùng tham khảo.

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 Phân tích và Thiết kế giải thuật nâng cao: Chương 3 - PGS.TS. Trần Cao Đệ

Phần 2: Các giải thuật nâng cao Chương 3: Cây cân bằng Balanced trees PGS. TS. TRẦN CAO ĐỆ Đại Học Cần Thơ 1 2013
Cây tìm kiếm nhị phân binary search tree  Cây tìm kiếm nhị phân 20 (TKNP) là cây nhị phân mà khoá tại mỗi nút lớn hơn khoá của tất cả các nút 10 35 thuộc cây con bên trái và nhỏ hơn khoá của tất cả các nút thuộc cây con bên phải. 5 17 22 42 typedef KeyType; typedef struct Node{ KeyType Key; 15 37 Node* Left; Node* Right; }; typedef Node* Tree; 2
thêm một khoá vào cây TKNP void InsertNode(KeyType x,Tree& Root ){ 20 /* thêm nút mới chứa khoá x */ if (Root == NULL){ Root=(Node*)malloc(sizeof(Node)); 10 35 Root->Key = x; Root->Left = NULL; Root->Right = NULL; } 5 17 22 42 else if (x < Root->Key) InsertNode(x,Root->Left); else if (x>Root->Key)InsertNode(x,Root->Right); 15 19 37 } 3
20 Xóa một nút trên cây TKNP 10 10 NULL 35 5 17 Xóa nút 17 Xóa nút 35 Xóa nút 20 20 15 10 35 5 17 25 42 22 24
Xóa một nút trên cây TKNP KeyType DeleteMin (Tree& Root ){ KeyType k; if (Root->Left == NULL){ k=Root->Key; Root = Root->Right; return k; } else return DeleteMin(Root->Left); } void DeleteNode(KeyType x,Tree& Root){ if (Root!=NULL) if (x < Root->Key) DeleteNode(x,Root->Left); else if (x > Root->Key) DeleteNode(x,Root->Right); else if ((Root->Left==NULL) && (Root->Right==NULL)) Root=NULL; else if (Root->Left == NULL) Root = Root->Right; else if (Root->Right==NULL) Root = Root->Left; else Root->Key = DeleteMin(Root->Right); } 5
Phân tích BST  Tìm kiếm một nút trên cây TKNP – Mất O(1) duyệt trên mỗi nút – Mỗi lần duyệt đi sâu xuống một mức – Vậy thời gian tìm kiếm là O(h) với h là chiều cao của cây  Thời gian tìm kiếm 1 nút, thêm một nút, xóa một nút trên cây TKNP là O(h), với h là chiều cao của cây TKNP  Chiều cao của cây TKNP có n nút: Logn ≤ h ≤ n 6
Cây AVL  Trong trường hợp xấu nhất  Chứng minh Gọi Nh số nút cây AVL có chiều cao h. thời gian thực hiện các phép Nh ≥ Nh-1 + Nh-2 + 1 toán trên BST là O(n) ≥ 2Nh-2 + 1  Cân bằng AVL ≥ 1 + 2(1 + 2Nh-4) – Do Adelson Velski và = 1 + 2 + 22Nh-4 Landis ≥ 1 + 2 + 22 + 23Nh-6 – AVL: Cây TKNP mà chiều … cao của hai cây con của ≥ 1 + 2 + 22 + 23 + ... + 2h/2 mọi nút chênh lệch nhiều = 2h/2+1 – 1 nhất là 1. Vậy 2h/2+1 – 1 < n  Trên cây AVL các phép tìm h/2 +1 < log2(n + 1) kiếm, thêm, xoa một nút là h < 2 log2(n + 1) O(log n), n là số nút  Phân tích sâu sắc theo số Fibonacci, giới hạn trên là 1.44 log(n + 2). 7
Thêm một nút vào cây AVL  Đầu tiên thêm một nút vào cây TKNP. Cây có thể mất cân bằng.  Cân bằng lại – Xét cây AVL: tree T=(r,Tl,Tr) trong đó Tl có chiều cao hl và Tr có chiều cao hr – Giả sử nút thêm vào trên Tr.  Nếu hl=hr+1: sau khi thêm vẫn cân bằng  Nếu hl=hr : sau khi thêm vẫn cân bằng  Nếu hl=hr-1 thì sau khi thêm sẽ mất cân bằngcân bằng lại. – Tương tự nếu thêm nút vào Tl 8
Single Rotation-RR RR rotation 9
Single rotation LL LL 10
Double rotation-LR LR 11
Double rotation-RL RL 12
Các định lý 4 phép quay LL, RR, LR, và RL phủ toàn bộ các trường hợp cần phải cân bằng lại  Trường hợp cây AVL trở nên mất cân bằng khi thêm một nút chỉ cần một phép quay để làm cho cây cân bằng lại.  Trường hợp cây AVL trở nên mất cân bằng khi Xóa một nút có thể cần tới O(log n) phép quay để làm cho cây cân bằng lại (từ nút mất cân bằng đến gốc). 13
Ví dụ thêm 1 khóa LL Thêm khóa 1 Thêm khóa 32 14
Xóa nút 4 4 RR rotation LL rotation
AVL Trees Implementation in java  See 3.6.1 chapter 3, Algorithm design, Goodrich 16
d-cây  Cây đa phân: là cây mỗi nút có  Mỗi d-nút (có các nút con từ hai con trở lên. v1,..,vd) sẽ lưu d-1 phần tử  Cây có thứ tự: các nút có tt dạng (k1,x1), …, (kd-1,xd-1) và  Nút v là d-nút: V có d≥2 nút con mỗi phần tử (k,x) lưu trong  Cây tìm kiếm đa phân (multi- cây con gốc vi phải thỏa way search tree) là cây có thứ tự với các tính chất sau: mãn: ki-1 ≤ k < ki – Mỗi nút trong là một d-nút có ít nhất 2 nút con. ( k0= -∞ còn kd = +∞) – Mỗi nút lưu trữ một tập hợp  Định lý: cây tìm kiếm đa các phần tử dạng (k,x),  k là khóa phân chứa n phần tử  x là giá trị kết hợp với khóa có (n+1) nút ngoài 17
Ví dụ: 3-cây 22 5 10 25 3 4 6 8 14 23 24 27 11 13 17 Xem thêm các giải thuật B-Cây trong giáo trình GT của Nguyễn Văn Linh 18
Cây 2-3-4 hoặc cây (2,4)  Cây (2,4) là 4-cây cân 25 bằng: – Mỗi nút có tối đa 4 nút con 50 5 15 – Các nút lá cùng một độ sâu  Định lý: 0 3 6 79 17 19 20 40 70 Cây (2,4) chứa n phần tử có chiều cao (logn) 19
Thêm 1 phần tử vào cây (2,4) thêm 4,6,12,15,3,5,10,8 4 12 5, 12 4, 6 15 3, 4, 6 3, 4 6,10 15 4, 6, 12 12 5, 12 4, 6, 12, 15 15 3, 4, 5, 6 3, 4 6, 8, 10 15 split split 5, 12 12 3, 4 6 15 SỐ lần split khi thêm 15 1 phần tử là O(logn) 20 4, 6