Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 6 - Trần Minh Thái (2016)
lượt xem 5
download
Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 6: Cây nhiều nhánh B-Tree" trình bày khái niệm về cây nhiều nhánh B-Tree, đặc điểm và cấu trúc, chèn phần tử vào cây, xóa phần tử khỏi cây. Mời các bạn cùng tham khảo.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 6 - Trần Minh Thái (2016)
- Chương 6. Cây nhiều nhánh: B-Tree Trần Minh Thái Email: minhthai@huflit.edu.vn Website: www.minhthai.edu.vn 1
- Nội dung 1. Khái niệm 2. Đặc điểm và cấu trúc 3. Chèn phần tử vào cây 4. Xóa phần tử khỏi cây 2
- Cây nhiều nhánh: M-Phân • Mỗi node có tối đa M node con • Một cây M-Phân đầy đủ có chiều cao logMN • Ví dụ cây 5-Phân đầy đủ: 3
- Khái niệm • Thứ tự các khóa tương tự cây nhị phân tìm kiếm • Mỗi node có M-1 khóa • M càng lớn cây càng thấp • Giữ tính chất cân bằng trên cây tìm kiếm M-Phân: B-Cây 4
- B-Tree B-Tree bậc M là cây M-Phân tìm kiếm có các tính chất: • Mỗi node (ngoại trừ gốc) có ít nhất M/2 node con • Node gốc (nếu không phải nút lá) có ít nhất 2 nút con • Mọi nút lá đều nằm cùng một mức • Các khóa và cây con được sắp xếp theo cây tìm kiếm 5
- B-Tree • Hạn chế số thao tác đọc mỗi lần tìm kiếm trên cây • Thích hợp cho việc tìm kiếm trên bộ nhớ ngoài • Chiều cao cây = logMN, tăng M chiều cao cây giảm rất nhanh 6
- Chèn node vào cây Ý tưởng: Tìm vị trí khóa có thể thêm vào cây. Việc tìm kiếm sẽ kết thúc tại một lá. Khóa mới sẽ được thêm vào nút lá: 1. Nếu chưa đầy Việc thêm hoàn tất 2. Nếu đầy Phân đôi nút lá cần thêm: • Tách nút lá ra làm hai nút cạnh nhau trong cùng một mức • Chuyển phần tử giữa lên nút cha Quá trình phân đôi các nút có thể được lan truyền ngược về gốc và kết thúc khi có một nút cha nào đó cần được thêm một khóa từ dưới lên 7mà chưa đầy
- Ví dụ • Cho B-tree bậc 5 rỗng • Hãy xây dựng B-Tree theo thứ tự từ trái sang phải cho dãy số sau: 1 1 8 2 2 5 1 2 1 7 5 1 4 6 3 2 2 5 5 45 2 5 4 8 7 2 6 8 8 6 9 3 5 8
- 1 1 8 2 2 5 1 2 1 7 5 1 4 6 3 2 2 5 5 45 2 5 4 8 7 2 6 8 8 6 9 3 5 Chèn 1 1 Chèn 12 1 12 Chèn 8 1 8 12 Chèn 2 1 2 8 12 9
- 1 1 8 2 2 5 1 2 1 7 5 1 4 6 3 2 2 5 5 45 2 5 4 8 7 2 6 8 8 6 9 3 5 Do nút gốc đã đầy (4 phần tử) Chèn 25 vào nút gốc sẽ tách nút gốc thành 2 nút và đưa khóa ở giữa lên trên tạo thành nút gốc mới 1 2 8 12 25 8 1 2 12 25 10
- 1 1 8 2 2 5 1 2 1 7 5 1 4 6 3 2 2 5 5 45 2 5 4 8 7 2 6 8 8 6 9 3 5 Thêm 5 8 1 2 5 12 25 Thêm 14 8 1 2 5 12 14 25 11
- 1 1 8 2 2 5 1 2 1 7 5 1 4 6 3 2 2 5 5 45 2 5 4 8 7 2 6 8 8 6 9 3 5 Thêm 28 8 1 2 5 12 14 25 28 Thêm 17, do nút lá bên phải đã đầy nên phân đôi và đưa nút giữa lên trên nút cha (nút gốc) 8 17 1 2 5 12 14 25 28 12
- 1 1 8 2 2 5 1 2 1 7 5 1 4 6 3 2 2 5 5 45 2 5 4 8 7 2 6 8 8 6 9 3 5 Thêm 7 8 17 1 2 5 7 12 14 25 28 Thêm 52 8 17 1 2 5 7 12 14 25 28 52 13
- 1 1 8 2 2 5 1 2 1 7 5 1 4 6 3 2 2 5 5 45 2 5 4 8 7 2 6 8 8 6 9 3 5 Thêm 16 8 17 1 2 5 7 12 14 16 25 28 52 Thêm 48 8 17 1 2 5 7 12 14 16 25 28 48 52 14
- 1 1 8 2 2 5 1 2 1 7 5 1 4 6 3 2 2 5 5 45 2 5 4 8 7 2 6 8 8 6 9 3 5 Thêm 68, do nút lá bên phải đã đầy nên phân đôi nút lá và đưa nút giữa lên nút cha (nút gốc) 8 17 48 1 2 5 7 12 14 16 25 28 52 68 Thêm 3, do nút lá bên trái đã đầy nên phân đôi nút lá và đưa nút giữa lên nút cha (nút gốc) 3 8 17 48 1 2 5 7 12 14 16 25 28 52 68 15
- 1 1 8 2 2 5 1 2 1 7 5 1 4 6 3 2 2 5 5 45 2 5 4 8 7 2 6 8 8 6 9 3 5 Thêm 26 3 8 17 48 1 2 5 7 12 14 16 25 2 28 52 68 6 Thêm 29 3 8 17 48 1 2 5 7 12 14 16 2 2 2 2 52 68 5 616 8 9
- 1 1 8 2 2 5 1 2 1 7 5 1 4 6 3 2 2 5 5 45 2 5 4 8 7 2 6 8 8 6 9 3 5 Thêm 53 3 8 17 48 1 2 5 7 12 14 16 2 2 2 2 52 53 68 5 6 8 9 Thêm 55 3 8 17 48 1 2 5 7 12 14 16 2 2 2 2 5 5 5 6 5 6 8 17 9 2 3 5 8
- 1 1 8 2 2 5 1 2 1 7 5 1 4 6 3 2 2 5 5 45 2 5 4 8 7 2 6 8 8 6 9 3 5 Thêm 45, do nút lá thứ 3 đầy nên phân đôi và đưa nút giữa lên trên nút cha, nút cha cũng đầy nên phân đôi tiếp nút cha và đưa nút giữa lên trên, tạo thành nút gốc mới 17 3 8 28 48 1 2 5 7 12 14 16 2 2 2 4 5 5 5 6 5 6 9 5 2 3 5 8 18
- Bài tập áp dụng Cho dãy số: 1, 3, 9, 2, 4, 10, 25, 30, 11, 40, 21, 8, 7, 6, 19, 5, 30, 12, 15, 16 Hãy trình bày từng bước vẽ cây B-Tree bậc 4 19
- Xóa khóa trên cây 1. Nếu khóa cần xóa nằm ở nút lá Xóa 2. Nếu khóa cần xóa không nằm ở nút lá Xóa khóa cần xóa, đưa khóa có giá trị gần nhất từ nút lá lên thay thế cho khóa đã xóa 20
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Cấu trúc dữ liệu - Bài 1:Tổng quan về cấu trúc dữ liệu và giải thuật
47 p | 175 | 17
-
Bài giảng Cấu trúc dữ liệu 1: Chương 1 - Lương Trần Hy Hiến
7 p | 162 | 9
-
Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 8: Cấu trúc dữ liệu ngăn xếp
28 p | 77 | 9
-
Bài giảng Cấu trúc dữ liệu giải thuật: Các kiểu dữ liệu trừu tượng cơ bản - Cấu trúc dữ liệu tuyến tính
92 p | 116 | 9
-
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 đỏ đen - Bùi Tiến Lên
25 p | 81 | 8
-
Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 17: Cấu trúc dữ liệu dạng cây
21 p | 77 | 8
-
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
193 p | 58 | 7
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (2016)
62 p | 94 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (Trường Đại học Hồng Bàng )
62 p | 159 | 6
-
Bài giảng Cấu trúc dữ liệu - Chương 3: Cấu trúc cây
65 p | 58 | 6
-
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 AA - Bùi Tiến Lên
30 p | 35 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 – Trần Minh Thái (2017)
67 p | 106 | 4
-
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 - Bùi Tiến Lên
68 p | 40 | 4
-
Bài giảng Cấu trúc dữ liệu: Chương 1 - ThS. Thiều Quang Trung (2018)
44 p | 43 | 4
-
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
38 p | 47 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - Ngô Quang Thạch
24 p | 58 | 3
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - Th.S Thiều Quang Trung
41 p | 68 | 3
-
Bài giảng Cấu trúc dữ liệu giải thuật: Cấu trúc dữ liệu
17 p | 50 | 2
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