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

Bài 3. a) Cho cây nhị phân tìm kiếm ban đầu như hình thêm lần lượt dãy khóa 43, 12, 36, 78, 29, 16, 9, 65, 27, 32. Hãy vẽ cây nhị phân kết quả thu được cuối cùng (không cần trình bày các bước trung gian). b) Với cây nhị phân tìm kiếm thu được ở phần a, thực hiện xóa lần lượt khóa 18 và 36. Hãy vẽ cây kết quả thu được sau mỗi lần xóa Chú ý: ch...

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

Bài 2. Cho cây biểu thức sau a.Duyệt cây biểu thức để đưa ra biểu thức dạng tiền tố, hậu tố b.Với a=36 và b=5, hãy minh họa thuật toán định giá biểu thức hậu tố trên biểu thức hậu tố thu được từ phần a Chú ý: √ là ký hiệu của toán tử căn bậc hai Bài 3. Cây nhị phân tìm kiếm a) Thêm lần lượt các nút 25, 32, 14, 21, 19, 17, 23, 5, 9 vào cây nhị...

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

Thuật toán nén RLE (cont.) Ví dụ 1 Hãy nén chuỗi sau bằng RLE AAABBCCAAADE Sẽ được mã hóa thành 3A2B2C3A1D1E Đánh giá thuật toán RLE Đơn giản, dễ cài đặt Dùng để nén các dữ liệu có nhiều đoạn lặp lại Thích hợp cho dữ liệu ảnh Hiệu suất nén không cao Thuật toán nén LZW Giới thiệu Được đề xuất bởi Ziv and Lempel và cải tiến bởi Welch [L...

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

Các khái niệm Định nghĩa 1 Cho số nguyên dương n 2 N, hai số nguyên a; b 2 Z được gọi là đồng dư theo mô-đun n nếu cả hai có cùng số dư khi chia cho n. Được ký hiệu a ≡ b (modn) Ví dụ 1 Ta có 11 ≡ 8 (mod3) (vì 11 và 8 chia cho 3 đều có số dư là 2) −2 ≡ 5 (mod7) (vì -2 và 5 chia cho 7 đều có số dư là 5) Một số tính chất Tính chất Quan hệ...

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

Ứng dụng của kiểu dữ liệu cây Kiểu dữ liệu cây thể hiện tính “phân cấp”, “kế thừa”. Do đó có thể biểu diễn được những cấu trúc như Cây gia phả (trong các dòng họ) Cây phân cấp các loài (trong sinh học) Cây thư mục (trong máy tính) Ứng dụng của kiểu dữ liệu cây (cont.) Biểu thức toán học có thể được biểu diễn bằng cây. Ví dụ cây dưới đây dùn...

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

Ngăn xếp Định nghĩa 1 Ngăn xếp (stack) là một cấu trúc dữ liệu dùng để lưu trữ một tập hợp các phần tử Hoạt động theo cơ chế “vào sau - ra trước” (last in, first out - LIFO); nghĩa là, ta chỉ thấy và truy cập của đỉnh của ngăn xếp Cấu trúc dữ liệu này được đề xuất bởi hai nhà khoa học người Đức [Bauer and Samelson, 2001] Ngăn xếp (cont.) M...

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

Cây đỏ đen Định nghĩa 1 Cây đỏ đen (red black tree) được Rudolf Bayer phát minh và là một cây nhị phân tìm kiếm có các đặc điểm sau 1. Mọi nút phải là nút đỏ hoặc nút đen 2. Nút gốc là nút đen 3. Nếu một nút là nút đỏ, thì con của nó phải nút đen 4. Tất cả các đường đi từ nút gốc đến nút-0 (không có con) hoặc nút-1 (có 1 con) phải có cùng s...

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

Dẫn nhập Một số ứng dụng kiểu hàng đợi thông thường không thể giải quyết được như Sắp hàng mua vé: thường sẽ ưu tiên cho người già, phụ nữ có thai, người tàn tật Trạm thu phí: thường ưu tiên sẽ cứu thương, xe cứu hỏa Hàng đợi ưu tiên Định nghĩa 1 Hàng đợi ưu tiên (priority queue) là một hàng đợi trong đó mỗi phần tử được gắn với một con số...

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

Các thao tác trên cây m-nhánh Đối với cây m-nhánh có các thao tác cơ bản trên cây Duyệt từng khóa của cây Tìm một khóa trong cây Thêm một khóa vào cây Xóa một khóa khỏi cây Thao tác duyệt cây Ta có thể xem cây như một đồ thị tổng quát và áp dụng các thuật toán duyệt của đồ thị để duyệt cây. Có hai thuật toán duyệt cơ bản Duyệt theo chiều ...

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

Cây nhị phân tìm kiếm cân bằng (cont.) Ý tưởng Có hai chiến lược cân bằng: Cân bằng theo chu kỳ hoạt động Cân bằng theo thao tác cập nhật Đa số kỹ thuật sử dụng biến đổi xoay để cân bằng lại Các phép biến đổi Để duy trì được sự cân bằng trong cây T, các nhà lập trình thường sử dụng các phép biến đổi sau Phép xoay trái (left rotation) Ph...

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