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 M-nhánh với B-cây - 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 M nhánh với B cây cung cấp cho người học các kiến thức về cây m nhánh, các thao tác trên cây m-nhánh, thao tác duyệt cây, B-cây,. . | 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 M-nhánh với B-cây - Bùi Tiến Lên CẤU TRÚC DỮ LIỆU CÂY M-NHÁNH VS B CÂY Bùi Tiến Lên 01/01/2017 CÂY M-NHÁNH Cây m-nhánh Định nghĩa 1 Cây m-nhánh (m-way tree) là một cây tìm kiếm có những tính chất sau I Mỗi nút có I tối thiểu 1 khóa I tối đa m − 1 khóa có giá trị phân biệt I Các khóa trong mỗi nút được sắp thứ tự tăng dần Spring 2017 Data structure & Algorithm 3 Cây m-nhánh (cont.) Định nghĩa 1 I Mỗi nút có k khóa {v1 , ., vk } thì sẽ có k + 1 cây con {T1 , ., Tk+1 }, các cây con có thể rỗng I Cây con đầu T sẽ chứa các khóa v trong khoảng 1 v ∈ (−∞, v1 ) (1) I Cây con cuối Tk+1 sẽ chứa các khóa v trong khoảng v ∈ (vk , ∞) (2) I Cây con Ti , i = 2, , k sẽ chứa các khóa v trong khoảng v ∈ (vi , vi+1 ) (3) I Mỗi khóa vi sẽ có cây con trái là Ti và cây con phải Ti+1 Spring 2017 Data structure & Algorithm 4 Minh họa v1 vi vi+1 vk T1 Ti Tk+1 Hình 1: Nút và các khóa và các cây con Spring 2017 Data structure & Algorithm 5 Minh họa (cont.) v1 vi vi+1 vk Ti Ti+1 Hình 2: Khóa và cây con trái và con phải Spring 2017 Data structure & Algorithm 6 Minh họa (cont.) 16 18 6 22 26 4 20 24 28 30 Hình 3: Cây 3-nhánh Spring 2017 Data structure & Algorithm 7 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 I Duyệt từng khóa của cây I Tìm một khóa trong cây I Thêm một khóa vào cây I Xóa một khóa khỏi cây Spring 2017 .

Không thể tạo bản xem trước, hãy bấm tải xuống
TỪ KHÓA LIÊN QUAN
TÀI LIỆU MỚI ĐĂNG
Đã 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.