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 Đệ

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.
Nội dung trích xuất từ tài liệu:
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 ...