TimTaiLieu.vn - Tài liệu, ebook, giáo trình, đồ án, luận văn

2. Sắp xếp nổi bọt (bubble sort)Sắp xếp nổi bọt • Mỗi bước duyệt qua các phần tử a0, a1, , ak • Tại mỗi phần tử ai (i < k): − So sánh a i với ai+1 − Đổi chỗ nếu chúng chưa đúng thứ tự • Sau mỗi bước, phần tử lớn nhất sẽ được đặt (“nổi bọt”) xuống cuối dãy (ak là max)Ví dụ sắp xếp nổi bọt • Ban đầu: 64, 25, 12, 22, 11 (k = n-1-0) • Sau bước...

38 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 500 | Lượt tải: 1

Giới thiệu  Phép Băm (Hashing): Là quá trình ánh xạ một giá trị khóa vào một vị trí trong bảng.  Một hàm băm ánh xạ các giá trị khóa đến các vị trí ký hiệu: h  Bảng băm (Hash Table) là mảng lưu trữ các record, ký hiệu: HT  HT có M vị trí được đánh chỉ mục từ 0 đến M- 1, M là kích thước của bảng băm.  Bảng băm thích hợp cho các ứng dụn...

61 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 628 | Lượt tải: 1

Hàng đợi ưu tiên • Chèn (insert) − Thời gian O(log N) • Xóa phần tử nhỏ nhất (deleteMin) − Thời gian O(log N)Cài đặt hàng đợi ưu tiên • Dùng danh sách liên kết: − insert mất thời gian O(1) − deleteMin mất thời gian O(N) • Dùng cây nhị phân tìm kiếm: − insert và deleteMin mất thời gian O(log N) − Tuy nhiên, cây nhị phân tìm kiếm quá phức t...

24 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 531 | Lượt tải: 1

Cài đặt hàng đợi ưu tiên • Dùng danh sách liên kết: − insert (dùng pushFront) mất thời gian O(1). − deleteMin (quét tìm rồi xóa min) mất thời gian O(N). • Dùng cây nhị phân tìm kiếm: − insert và deleteMin mất thời gian O(log N). − Tuy nhiên, cây nhị phân tìm kiếm quá phức tạp cho yêu cầu đơn giản hơn của hàng đợi ưu tiên. • Đống nhị phân (b...

25 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 539 | Lượt tải: 1

Các thao tác trên cây cân bằng  Khi thêm hay xoá 1 nút trên cây, cĩ thể làm cho cây mất tính cân bằng, khi ấy ta phải tiến hành cân bằng lại.  Cây có khả năng mất cân bằng khi thay đổi chiều cao:  Lệch nhánh trái, thêm bên trái  Lệch nhánh phải, thêm bên phải  Lệch nhánh trái, hủy bên phải  Lệch nhánh phải, hủy bên trái  Cân bằng l...

17 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 417 | Lượt tải: 1

So sánh các cấu trúc dữ liệu • So sánh thời gian tìm kiếm: − Vector và danh sách liên kết: O(n) − Cây AVL: O(log n) − Bảng băm: O(1)Hàm băm (hash function) • Ánh xạ khóa sang số nguyên (vị trí trong bảng băm). • Nếu nhiều khóa ánh xạ sang cùng một số nguyên (cùng vị trí trong bảng băm) thì sẽ dẫn đến đụng độ: − Đụng độ sẽ giảm nếu các khóa ...

17 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 502 | Lượt tải: 1

Bảng băm • Các phần tử dưới dạng cặp khóa-giá trị (key-value) • Mỗi phần tử được lưu trữ vào một ô nào đó trong mảng tùy theo khóa của nó là gì • Thực hiện các phép tìm/chèn/xóa trong thời gian O(1) • Không hiệu quả với các thao tác đòi hỏi thông tin thứ tự: − VD: tìm phần tử lớn nhất và nhỏ nhất Ví dụ bảng băm Mỗi phần tử là một cặp khóa...

16 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 573 | Lượt tải: 1

Định nghĩa B-tree Định nghĩa Một B-tree bậc m là cây nhiều nhánh tìm kiếm thỏa các điều kiện sau: (i) Tất cả các node lá cùng mức. (ii) Tất cả các node trung gian (trừ node gốc) có nhiều nhất m cây con và có ít nhất m/2 cây con (khác rỗng). (iii) Mỗi node hoặc là node lá hoặc có k+1 cây con (k là số khoá của node này). (iv) Node gốc có nhi...

29 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 695 | Lượt tải: 1

Ðịnh nghĩa cây nhị phân tìm kiếm • Cây nhị phân • Bảo đảm nguyên tắc bố trí khoá tại mỗi nút: – Các nút trong cây trái nhỏ hơn nút hiện hành – Các nút trong cây phải lớn hơn nút hiện hành Ưu điểm của cây nhị phân tìm kiếm • Nhờ trật tự bố trí khóa trên cây : – Định hướng được khi tìm kiếm • Cây gồm N phần tử : – Trường hợp tốt nhất h = log...

19 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 469 | Lượt tải: 1

Mở đầu • Khi xây dựng cây nhị phân tìm kiếm, ta muốn có kiểu cây nào hơn? • Ví dụ: dựng cây từ dãy {3, 5, 8, 20, 18, 13, 22} Mở đầu (tiếp) • Ta muốn một cây nhị phân tìm kiếm cân đối: − có độ sâu của cây = log n, và do đó − cho phép chèn và xóa với thời gian chạy O(log n) trong mọi trường hợp. • Cây AVL là một kiểu cây như vậy! Cây AVL (A...

27 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 748 | Lượt tải: 1