intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Cấu trúc dữ liệu và giải thuật: Cây tìm kiếm nhị phân cân bằng

Chia sẻ: You Can | Ngày: | Loại File: PDF | Số trang:22

Thêm vào BST
Báo xấu
183
lượt xem 10
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chương này trang bị cho người học những hiểu biết về cây tìm kiếm nhị phân cân bằng. Thông qua chương này người học có thể biết được đặc điểm của cấu trúc cây tìm kiếm nhị phân, biết được cây tìm kiếm nhị phân cân bằng – AVL tree là gì, biết cách khai báo cấu trúc 1 nút cây AVL,... Mời các bạn ù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 Cấu trúc dữ liệu và giải thuật: Cây tìm kiếm nhị phân cân bằng

  1. 3/24/2011 Chương 4. Cây tìm kiếm nhị phân cân bằng Tìm kiếm (tiếp) AVL Tree  nguyenduyhiep@gmail.com G. M. ADELSON‐VELSKII và E. M. LANDIS hiepnd@soict.hut.edu.vn Tìm kiếm AVL tree  Cây tìm kiếm nhị phân cân bằng – AVL tree:   Đặc điểm của cấu trúc cây tìm kiếm nhị phân  Là cây tìm kiếm nhị phân   Kiểu cấu trúc liên kết  Chiều cao của cây con trái và cây con phải của gốc chênh nhau  không quá 1  Thao tác tìm kiếm, thêm, xóa thực hiện dễ dàng  Cây con trái và cây con phải cũng là các cây AVL  Thời gian thực hiện các thao tác trong trường hợp tốt nhất  log , tồi nhất   Trường hợp tồi khi cây bị suy biến  12 12 12  Cây cân bằng cho thời gian thực hiện tốt nhất 21 9 21 9 21  Cải tiến cấu trúc cây tìm kiếm nhị phân để  luôn thu được thời gian thực hiện tối ưu  5 10 15 30 1
  2. 3/24/2011 AVL tree AVL tree  Quản lý trạng thái cân bằng của cây  Thêm các nút 3, 2, 1, 4, 5, 6, 7 vào cây AVL ban đầu rỗng  Mỗi nút đưa thêm 1 thông tin là hệ số cân bằng (balance  Xoay phải factor) có thể nhận 3 giá trị 3 3 ‐2 3 2  Left_higher (hoặc ‐1)   Equal_height (hoặc 0)  2 ‐1 2 1 3  Right_higher (hoặc +1)  12 1 Thêm 3 Thêm 2 Vi phạm tính  chất của cây   Hai thao tác làm thay đổi  0 1 AVL 0 9 21 ‐1 hệ số cân bằng của nút: Thêm 1  Thêm nút  Xóa nút  15 0 Xử lý bằng phép xoay nút AVL tree AVL tree  Khai báo cấu trúc 1 nút cây AVL 2 2 2 2 Xoay trái 2 enum Balance_factor { left_higher, equal_height, right_higher }; 1 3 1 0 3 1 4 typedef struct AVLNode { 1 int data; 4 4 3 5 Vi phạm Balance_factor balance; Thêm 4 struct TreeNode *leftChild; 0 struct TreeNode *rightChild; Thêm 5 5 } AVLNODE; Xoay giữa nút vi phạm và nút con của nó 2
  3. 3/24/2011 AVL tree AVL tree Xoay trái Xoay phải K1 K2 2 Vi phạm 2 4 K1 K2 X Z Y X 1 4 1 2 5 Z Y 3 5 1 1 3 6 Xoay trái K1 K2 6 K2 K1 0 Thêm 6 X X Z Y Z Y AVL tree AVL tree 4 Phép xoay đơn – single rotation:  Vi phạm 4  Dùng để điều chỉnh khi mà nút mới thêm vào trong  trường hợp: 2 5 2 6  (i) Cây con trái của nút con trái, hoặc   (ii)Cây con phải của nút con phải của nút 1 3 6  Thực hiện tại nút vi phạm đầu tiên trên đường từ vị trí  1 3 5 7 mới thêm trở về gốc 7  Xoay giữa nút vi phạm và nút con trái (xoay phải) – TH i)  Thêm 7 (hoặc con phải (xoay trái)– TH ii)  Sau khi xoay các nút trở nên cân bằng 3
  4. 3/24/2011 AVL tree AVL tree  Thực hiện thêm tiếp các khóa 16, 15, 14, 13, 12, 11, 10, 8, 9  4 2 vào cây Vi phạm 4 4 2 Nút vi phạm  2 6 2 2 7 đầu tiên 6 2 2 1 3 5 15 ‐1 1 3 6 15 1 3 5 7 2 ‐2 16 1 7 16 5 14 16 Thêm 16 1 Vẫn vi phạm 16 ‐1 7 14 Thêm 14 15 15 0 Thêm 15 0 AVL tree AVL tree K1 K1 4 4 K2 K2 X X 2 6 2 6 K3 Y Z Y 3 5 3 5 Z1’ Z2’ 1 7 1 15 K1 K1 2. Xoay trái Hai trường hợp áp  16 7 16 dụng xoay kép K2 K2 1. Xoay phải X 15 X K3 Thêm 15 Y Z Y Z1’ Z2’ 4
  5. 3/24/2011 AVL tree AVL tree K1 2 K3 2 4 7 K2 K1 K2 2 7 1 X 4 15 K3 1 Y Z1’ Z2’ X Y 1 3 6 ‐1 Z1’ Z2’ 15 2 6 14 16 K1 K3 2 5 14 16 1 3 5 13 K2 1 K2 K1 13 K3 X Thêm 13 Y Y Z1’ Z2’ X Z1’ Z2’ AVL tree AVL tree Phép xoay kép – double rotation:  7  Dùng để điều chỉnh khi mà nút mới thêm vào trong  trường hợp:  (i) Cây con phải của nút con trái, hoặc  4 15  (ii)Cây con trái của nút con phải của nút  Thực hiện tại nút vi phạm đầu tiên trên đường từ vị trí  2 6 14 16 mới thêm trở về gốc  Xoay giữa nút vi phạm, nút con, và nút cháu (con của nút  1 3 5 13 con)  Xoay kép gồm 2 phép xoay trái và xoay phải  Số nút trong quá trình thực hiện xoay là 3 Thêm 12 5
  6. 3/24/2011 AVL tree AVL tree Thêm 11 Thêm 8 AVL tree AVL tree Thêm 10 Thêm 9 6
  7. 3/24/2011 AVL tree AVL tree  Mỗi phép xoay có 2 trường hợp, khi cài đặt sẽ phải có 4  void rotate_right(AVLNODE *&root) trường hợp { if(root==NULL || root‐>leftChild==NULL)   Trái – trái (xoay đơn) //error, because it's impossible   Phải – phải (xoay đơn) { printf("It's must be a mistake when using this function!\n");  Trái – phải (xoay kép) }  Phải – trái (xoay kép) else { AVLNODE *pLeft = root‐>leftChild; root‐>leftChild = pLeft‐>rightChild;  Sau mỗi lần xoay, trạng thái cân bằng lại được xác lập lại  pLeft‐>rightChild = root; tại nút vi phạm root = pLeft; } } AVL tree AVL tree void left_balance(AVLNODE *&root) //2 single rotations //balance function for insert in left subtree void rotate_left(AVLNODE *&root) { { AVLNODE *pLeft = root‐>leftChild; if(root==NULL || root‐>rightChild==NULL)  if(pLeft‐>balance == equal_height) //error, because it's impossible  { { printf("It's must be a mistake when using this function!\n"); printf("It's must be a mistake when using this function!\n"); } } else if(pLeft‐>balance == left_higher)  else //left‐left case (single rotation) { { AVLNODE *pRight = root‐>rightChild; root‐>balance = equal_height; root‐>rightChild = pRight‐>leftChild; pLeft‐>balance = equal_height; pRight‐>leftChild = root; rotate_right(root); root = pRight; } } else } //left‐right case (double rotation:(1)rotate left,(2)rotate right) 7
  8. 3/24/2011 { AVLNODE *pLeftRight = root‐>leftChild‐>rightChild; if(pLeftRight‐>balance == left_higher) { AVL tree pLeft‐>balance = equal_height; root‐>balance = right_higher;  Xóa nút khỏi cây:  }  Chuyển bài toán xóa nút đầy đủ thành xóa nút có nhiều nhất  else if(pLeftRight‐>balance == equal_height) { một con. pLeft‐>balance = equal_height;  Xóa nút có nhiều nhất một con bị xóa làm chiều cao của  root‐>balance = equal_height; } nhánh bị giảm else  Căn cứ vào trạng thái cân bằng tại các nút từ nút bị xóa trên  { pLeft‐>balance = left_higher; đường trở về gốc để cân bằng lại cây nếu cần (giống với khi  root‐>balance = equal_height; thêm một nút mới vào cây) } pLeftRight‐>balance = equal_height; rotate_left(pLeft); root‐>leftChild = pLeft; rotate_right(root); } } AVL tree AVL tree  Xóa nút khỏi cây:   Nếu nút cần xóa là nút đầy đủ: chuyển về xóa nút có nhiều  nhất 1 nút con  Thay thế nút cần xóa bằng nút phải nhất trên cây con trái  hoặc , nút trái nhất trên cây con phải  Copy các thông số của nút thay thế giống với thông số của  nút bị xóa thực sự  Nếu nút bị xóa là nút có 1 con: thay thế nút đó bằng nút gốc  của cây con  Chiều cao cây không đổi  Nếu nút bị xóa là nút lá: gỡ bỏ nút, gán con trỏ của nút cha  Trường hợp 1: nút p đang ở trạng thái cân bằng (equal) nó bằng NULL Xóa một nút của cây con trái (hoặc phải) làm cây bị lệch nhưng  chiều cao không đổi  8
  9. 3/24/2011 AVL tree AVL tree Trường hợp 3.1 Chiều cao cây thay đổi Trường hợp 2: nút p đang ở trạng thái lệch trái hoặc phải  Nút bị xóa là nút của nhánh cao hơn, sau khi xóa cây trở về trạng  thái cân bằng và chiều cao của cây giảm  Chiều cao cây không đổi AVL tree AVL tree  Trường hợp 3: cây đang bị lệch và nút bị xóa nằm trên nhánh  thấp hơn.   Để cân bằng lại cây ta phải thực hiện các phép xoay.   Trường hợp 3.2: nút q bị lệch trái (nếu q là con phải của  Căn cứ vào tình trạng cân bằng của nút con còn lại  q của p mà  p) hoặc lệch phải (nếu q là con trái của p) ta chia thành các trường hợp nhỏ sau:  Cân bằng p bằng cách thực hiện phép xoay đơn giữa q và p  Sau khi xoay p trở về trạng thái cân bằng và chiều cao của p  Trường hợp 3.1: Nút q đang ở trạng thái cân bằng  bị giảm đi    Thực hiện phép xoay đơn (xoay trái hoặc xoay phải)  Sau khi xoay, p trở về trạng thái cân bằng  9
  10. 3/24/2011 AVL tree AVL tree Chiều cao cây thay đổi Chiều cao cây thay đổi AVL tree AVL tree  Trường hợp 3.3: nút q bị lệch cùng phía với nhánh bị xóa.  7 Nếu nhánh bị xóa là nhánh trái của p thì q bị lệch trái và  ngược lại  Để tái cân bằng cho p ta phải thực hiện 2 phép xoay giữa nút  4 15 con của q, nút q, và nút p  Sau khi xoay, chiều cao của cây giảm đi, p trở về trạng thái cân  2 6 bằng 14 16 1 3 13 Xóa một trong các nút 4, 7, 15 trên cây AVL 10
  11. 3/24/2011 Cấy trúc tự điều chỉnh  Trong nhiều bài toán chúng ta cần một cấu trúc xử lý hiệu  quả với những truy cập có số lượng lớn trên các bản ghi  Question  mới đưa vào. Ví dụ: bài toán quản lý thông tin bệnh nhân tại bệnh viện  Bệnh nhân ra khỏi bệnh viện thì có số lần truy cập thông tin ít  hơn  Bệnh nhân mới vào viện thì sẽ có số lượng truy cập thông tin  thường xuyên  Ta cần cấu trúc mà có thể tự điều chỉnh để đưa những bản ghi  mới thêm vào ở gần gốc để cho việc truy cập thường xuyên dễ  dàng. Cây splay  Splay tree  Là cây tìm kiếm nhị phân  Mỗi khi truy cập vào một nút trên cây (thêm, hoặc xóa) thì nút  mới truy nhập sẽ được tự động chuyển thành gốc của cây mới  Các nút được truy cập thường xuyên sẽ ở gần gốc  Các nút ít được truy cập sẽ bị đẩy xa dần gốc Splay tree  Để dịch chuyển các nút ta dùng các phép xoay giống với trong  Cấu trúc tự điều chỉnh AVL tree  Các nút nằm trên đường đi từ gốc đến nút mới truy cập sẽ chịu  ảnh hưởng của các phép xoay 11
  12. 3/24/2011 Cây splay Cây splay  Nhắc lại về các phép xoay   Trường hợp chỉ dùng phép xoay đơn để điều chỉnh nút  Xoay đơn – single rotation:  25  Nút cha xuống thấp 1 mức và nút con lên 1 mức 9 21 6 25 ‐2 3 2 15 4 21 ‐1 2 1 3 6 18 15 0 1 4 9 18 Cây splay Cây splay  Xoay kép – double rotation:   Nhận xét:  gồm 2 phép xoay đơn liên tiếp.   Nút mới truy cập (nút 9) được chuyển thành nút gốc của cây   Nút  tăng lên 1 mức, còn các nút còn lại lên hoặc giảm xuống  mới nhiều nhất 1 mức   Tuy nhiên nút 18 lại bị đẩu xuống vị trí của nút 9 trước  Như vậy:  7  Truy cập tới 1 nút sẽ đẩy các nút khác xuống sâu hơn.   Tốc độ của nút bị truy cập được cải thiện nhưng không cải  15 thiện tốc độ truy cập của các nút khác trên đường truy cập 16  Thời gian truy cập với  nút liên tiếp vẫn là  ∗ 7 16  Ý tưởng dùng chỉ phép xoay đơn để biến đổi cây là không đủ  15 tốt 12
  13. 3/24/2011 Cây splay Cây splay  Ý tưởng mới:  Tại mỗi bước ta di chuyển nút liền 2 mức  Xét các nút trên đường đi từ gốc đến nút mới truy nhập  Nếu ta di chuyển trái (từ gốc xuống), ta gọi là Zig  Ngược lại, di chuyển phải ta gọi là Zag  T4 T1 21 21 21 21 21 21 T3 T2 15 15 15 27 27 27 T1 T2 T3 T4 Trường hợp Zig‐Zig Zig Zag 6 Zig‐Zig 17 23 34 Zig‐Zag Zag‐Zig Zag‐Zag Cây splay Cây splay  Dịch chuyển:  Nếu nút đang xét nằm ở mức sâu hơn hoặc bằng 2 ta dịch chuyển  2 mức mỗi lần  Nếu nút ở mức 1: ta chỉ dịch chuyển 1 mức (trường hợp Zig hoặc  Zag) T4 T3 T4 T1 T2 T3 T3 T1 T1 T2 Trường hợp Zag‐Zig T1 T2 T2 T3 Trường hợp Zig 13
  14. 3/24/2011 Cây splay Cây splay  Chú ý: trường hợp Zig‐Zig (hoặc Zag‐Zag) khác hoàn toàn với   Nhận xét về cây splay: trường hợp dùng hai phép xoay đơn liên tiếp   Cây không cân bằng (thường bị lệch)  Các thao tác có thời gian thực hiện khác nhau từ O(1) tới O(n)  Thời gian thực hiện trung bình của một thao tác trong một  chuỗi thao tác là  log  Thực hiện giống như cây AVL nhưng không cần quản lý thông  T1 T4 tin về trạng thái cân bằng của các nút  T4 T3 Nếu dùng 2 phép xoay đơn T1 T2 T2 T3 Cây splay  Thực hiện splay tại nút 23 45 21 73 15 37 6 35 40 Cây 2‐3 25 23 27 14
  15. 3/24/2011 Cây 2‐3 Cây 2‐3  Đảm bảo cây luôn luôn cân bằng  Nút trong có 3 con – nút 3  Chi phí thực hiện các thao tác luôn là  log  Nút chứa 2 phần tử  Có 3 nút con  Cây 2‐3:  Mỗi nút trong có 2 tới 3 nút con p          q  Nút lá có 1 tới 2 giá trị x q  Dữ liệu được lưu trên nút lá hoặc nút trong p
  16. 3/24/2011 Cây 2‐3 Cây 2‐3  Định nghĩa cấu trúc 1 nút  34    57 struct TreeNode { 24 37    45 59    67 DATA_TYPE smallItem, largeItem; struct TreeNode *left, *middle, *right; struct TreeNode *parent; //to make your life easier } 12 27    32 35 42 47    52  Duyệt cây theo thứ tự giữa: 12, 24, 27, 32, 34, 35, 37, 42, 45, 47, 52, 57, 59, 67 Cây 2‐3 Cây 2‐3  Duyệt cây theo thứ tự giữa – in‐order traversal   (1) Duyệt cây con trái   Tìm kiếm   (2) Xử lý nội dung khóa nhỏ hơn tại nút  Nếu nút hiện tại rỗng  không tìm thấy  (3) Duyệt cây con giữa  Nếu giá trị tìm kiếm k xuất hiện trên nút hiện tại  tìm thấy  (4) Xử lý nội dung khóa lớn hơn tại nút  Nếu k
  17. 3/24/2011 Cây 2‐3 Cây 2‐3 Thêm 29  Thêm nút 24 24  Phần tử mới được thêm vào tại nút lá của cây  Nếu nút lá sau khi thêm có 3 phần tử ta phải thực hiện thao  tác tách nút 12 27    32 12 27    29    32  Khi tách nút, khóa giữa bị đẩy lên nút cha  Tách nút tại nút lá có thể dẫn đến tách nút tại nút trong Tách nút 24    29 Tách nút: • Khóa ở giữa bị đẩy lên nút  cha 12 27 32 • Nút hiện tại bị tách thành 2  nút con Cây 2‐3 Cây 2‐3 34    57 24 Thêm 19 24 24 37    45 59    67 12 27    32 12    19 27    32 12 27    32 35 42 47    52 Không phải tách nút Thêm nút 50 ? 17
  18. 3/24/2011 Cây 2‐3 Cây 2‐3 Thêm nút 50 Thêm nút 50 Vi phạm 34    57 34     45    57 24 37    45 59    67 24 37 50 59    67 12 27    32 35 42 47  50  52 12 27    32 35 42 47 52 Vi phạm Cây 2‐3 Cây 2‐3 Thêm nút 50 Thêm nút 50 45 34 57 34    57 Vi phạm 24 37 50 59    67 24 37    45   50 59    67 12 27    32 35 42 47 52 12 27    32 35 42 47 52 Tách tại nút gốc 18
  19. 3/24/2011 Cây 2‐3 Cây 2‐3 45  Xóa nút lá  Nếu nút lá sau khi xóa vẫn còn phần tử kết thúc  Ngược lại ta phải dịch chuyển phần tử từ nút anh em  34 57 của nó, hoặc từ nút cha của nó  (i) Nếu nút anh em của nó có 2 phần tử thì dịch một phần  tử sang nút hiện tại 24 37 50 59    67  (ii) Nếu không thực hiện dịch được thì ta sẽ thực hiện kết  hợp (điều này có thể dẫn đến giảm chiều cao của cây) 12 27    32 35 42 47 52 Vẽ cây thu được sau khi thêm lần lượt các khóa  5, 7, 29, 31, 70, 75 vào cây trên Cây 2‐3 Cây 2‐3  Xóa nút:  Xóa 27 (trường hợp nút lá sau khi xóa vẫn còn phần tử)  Nếu phần tử bị xóa ở trên nút trong:   Phải chuyển phần tử đó về nút lá để xóa  Thay thế bằng nút kế tiếp trong duyệt theo thứ tự giữa 24 24 37 45 42 45 12 27  32 12 32 35 42 47    52 35 37 47    52 Xóa 37, ta thay bằng 42 19
  20. 3/24/2011 Cây 2‐3 Cây 2‐3  Xóa 35 : trường hợp (i)  Xóa 37: trường hợp (ii) 42    47 47 37    45 42    47 37 45 52 35 42 47    52 37 45 52 42    45 52 Cây 2‐3 Cây 2‐3  Xóa 52: trường hợp (ii)  Xóa 12: trường hợp (ii) 42 34 42    47 37 45 52 37 45    47 24 42    47 12 32 37 45 52 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2