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ác cấu trúc dữ liệu nâng cao - Nguyễn Tri Tuấn

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:63

Thêm vào BST
Báo xấu
33
lượt xem 3
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ác cấu trúc dữ liệu nâng cao" cung cấp cho người đọc các kiến thức: Cây nhị phân tìm kiếm cân bằng, B-Cây, bảng băm - Hash table. 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ác cấu trúc dữ liệu nâng cao - Nguyễn Tri Tuấn

  1. Các cấu trúc dữ liệu nâng cao (Advanced Data Structures) 3.1 Cây nhị phân tìm kiếm cân bằng 3.2 B-Cây 3.3 Bảng băm – Hash Table Winter 2017 123 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  2. Cây nhị phân tìm kiếm cân bằng (1)  Cây BST có thể bị lệch  Vì sao cây BST trở nên bị lệch ?  Chi phí tìm kiếm trên cây bị lệch ? Một cây BST không cân bằng Winter 2017 124 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  3. Cây nhị phân tìm kiếm cân bằng (2) Cây cân bằng  chiều cao và chi phí tìm kiếm tối ưu O(log2N) Winter 2017 125 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  4. Cây nhị phân tìm kiếm cân bằng (3) Cần có phương pháp để duy trì tính cân bằng cho cây BST Winter 2017 126 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  5. Cây nhị phân tìm kiếm cân bằng (4)  Các loại cây BST cân bằng  Cây AVL  Cây Đỏ - Đen (Red – Black tree)  Cây AA Winter 2017 127 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  6. Cây AVL (1)  Định nghĩa  Cài đặt cấu trúc dữ liệu  Mất cân bằng khi thêm/xóa node  Các thuật toán điều chỉnh cây  Đánh giá/so sánh E. M. Landis G. M. Adelson-Velskii Winter 2017 128 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  7. Cây AVL (2)  Cấu trúc cây AVL do 2 tác giả người Liên xô: G. M. Adelson-Velskii và E. M. Landis công bố năm 1962  Đây là mô hình cây tự cân bằng đầu tiên được đề xuất (self-adjusting, height- balanced binary search tree) Winter 2017 129 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  8. Định nghĩa cây AVL (1)  Cây AVL:  Là một cây nhị phân tìm kiếm (BST)  Mỗi nút p của cây đều thỏa: chiều cao của cây con bên trái (p->left) và chiều cao của cây con bên phải (p->right) chênh lệch nhau không quá 1 pTAVL: abs(hp->left - hp->right) 1 Winter 2017 130 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  9. Định nghĩa cây AVL (2) Chiều cao 2 cây con left, right chênh lệch không quá 1 Winter 2017 131 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  10. Định nghĩa cây AVL (3) Cây AVL ? Winter 2017 132 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  11. Cài đặt cấu trúc dữ liệu (1)  Cấu trúc node, tree tương tự như BST  Thêm vào mỗi node một field balance, diễn tả trạng thái cân bằng của node đó:  balance = -1: node lệch trái (cây con trái cao hơn cây con phải)  balance = 0: node cân bằng (cây con trái cao bằng cây con phải)  balance = +1: node lệch phải (cây con phải cao hơn cây con trái) Winter 2017 133 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  12. Cài đặt cấu trúc dữ liệu (2) +1 20 +1 -1 10 30 0 0 0 15 26 40 0 0 25 27 Hệ số cân bằng của các node trong cây AVL Winter 2017 134 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  13. Cài đặt cấu trúc dữ liệu (3) template class AVLNode { public: T key; // key of node char balance; // balance status of node BSTNode *left; // pointer to left child BSTNode *right; // pointer to right child BSTNode() { } BSTNode(T newItem) { key = newItem; balance = 0; left = right = NULL; } }; // end class Winter 2017 135 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  14. Mất cân bằng khi thêm/xóa node (1)  [Insert – Thêm 1 phần tử vào cây]: có thể làm cây mất cân bằng.  Duyệt từ node vừa thêm ngược về node gốc  Nếu tìm thấy node P bị mất cân bằng thì tiến hành xoay cây tại nút P (chỉ cần điều chỉnh 1 lần duy nhất) Winter 2017 136 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  15. Mất cân bằng khi thêm/xóa node (2) 44 P 17 78 Thêm phần tử 54 32 50 88 làm cây mất cân bằng tại node P 48 62 54 Winter 2017 137 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  16. Mất cân bằng khi thêm/xóa node (3)  [Delete – Xóa 1 phần tử]: có thể làm cây mất cân bằng.  Duyệt từ node vừa xóa ngược về node gốc  Nếu tìm thấy node P bị mất cân bằng thì tiến hành xoay cây tại node P  Lưu ý: Thao tác điều chỉnh có thể làm cho những node phía trên của node P bị mất cân bằng  cần điều chỉnh cho đến khi không còn node nào bị mất cân bằng nữa (lùi dần về node gốc) Winter 2017 138 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  17. Mất cân bằng khi thêm/xóa node (4) P 44 17 78 Xóa phần tử 32 làm 32 50 88 cây mất cân bằng tại node P 48 62 Winter 2017 139 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  18. Các thuật toán điều chỉnh cây (1) P -1 P -1 -1 +1 P1 P1 h h h h+1 C h C h+1 B A A B (a1) (b1) Hai trường hợp cây bị mất cân bằng ở nhánh trái Winter 2017 140/203 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  19. Các thuật toán điều chỉnh cây (2) P +1 P +1 +1 -1 P1 P1 h h A h A h+1 h h+1 B C C B (a2) (b2) Hai trường hợp cây bị mất cân bằng ở nhánh phải Winter 2017 141 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  20. Các thuật toán điều chỉnh cây (3) P -1 P1 0 -1 P1 P 0 SLR h h C h+1 h+1 h h B A A B C Trường hợp (a1): áp dụng phép xoay đơn Trái - Phải (SLR – Single Left-to-Right) Winter 2017 142 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
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
3=>0