tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây AVL - Bùi Tiến Lên

Bài giảng "Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây AVL" trình bày một số vấn đề của cây nhị phân tìm kiếm, cây nhị phân tìm kiếm cân bằng, các phép biến đổi, thuật toán DSW,. nội dung chi tiết. | Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây AVL - Bùi Tiến Lên CẤU TRÚC DỮ LIỆU CÂY AVL Bùi Tiến Lên 01/01/2017 Một số vấn đề của cây nhị phân tìm kiếm Vấn đề Khi thực hiện các thao tác trên cây nhị phân tìm kiếm chẳng hạn như thêm, xóa có thể dẫn đến cây mất cân bằng. Dẫn đến cây nhị phân tìm kiếm không còn hiệu quả Spring 2017 Data structure & Algorithm 2 Một số vấn đề của cây nhị phân tìm kiếm (cont.) Ví dụ 1 Tạo cây nhị phân tìm kiếm từ dãy các số {4, 3, 2, 1} ta sẽ được 4 3 2 1 Hình 1: Cây tuyến tính Spring 2017 Data structure & Algorithm 3 Cây nhị phân tìm kiếm cân bằng Định nghĩa 1 Cây cân bằng tối ưu (perfect tree) là cây có chiều cao h = log2 (n + 1) với n là số nút của cây Spring 2017 Data structure & Algorithm 4 Cây nhị phân tìm kiếm cân bằng (cont.) Ví dụ 2 Cây hoàn chỉnh là một cây cân bằng tối ưu Hình 2: Cây nhị phân tìm kiếm hoàn chỉnh Spring 2017 Data structure & Algorithm 5 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: I Cân bằng theo chu kỳ hoạt động I 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 Spring 2017 Data structure & Algorithm 6 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 I Phép xoay trái (left rotation) I Phép xoay phải (right rotation) Định lý 1 Các phép biến đổi xoay trái và xoay phải không làm mất đi tính chất “tìm kiếm” của cây Spring 2017 Data structure & Algorithm .

TỪ KHÓA LIÊN QUAN
TÀI LIỆU MỚI ĐĂNG
46    179    0    29-03-2024
42    171    1    29-03-2024
10    148    0    29-03-2024
2    112    0    29-03-2024
crossorigin="anonymous">
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.