Bài giảng chương 4: B-Cây

B-CÂY Chương 4 Cây tìm kiếm nhiều đường Cây tìm kiếm nhiều đường (Multiway Search Trees): Cây tìm kiếm cấp m (m > 2) là sự mở rộng của cây nhị phân tìm kiếm BST, trong đó mỗi nút có tối đa m con Một ứng dụng của cây tìm kiếm nhiều đường là được sử dụng để truy xuất bộ nhớ ngoài theo nguyên tắc: “Số lần truy xuất càng ít càng tốt” Để thực hiện điều này thì nếu một phần tử trên bộ nhớ ngoài được truy xuất thì toàn bộ một nhóm phần tử cũng được truy xuất theo Cây tìm kiếm nhiều đường Điều nầy dẫn đến một cây được chia thành các cây con (gọi là trang) và các phần tử trong một trang sẽ được truy xuất đồng thời Ví dụ, cây nhị phân được chia thành các trang, mỗi trang có 3 nút: Cây tìm kiếm nhiều đường Giả sử mỗi trang có 100 nút và cây này có 1 triệu phần tử thì trung bình chỉ cần lần truy xuất thay vì lần ở cây BST B-cây (Bayer tree) Ta nhận thấy cây cân bằng đòi hỏi phải cân bằng lại trong quá trình cây bị biến đổi Việc cân bằng này bao gồm nhiều thao tác phức tạp và tốn thời gian Một tiêu chuẩn được R. Bayer đưa ra năm 1970 là mọi trang (trừ trang gốc) chứa ít nhất là n nút và nhiều nhất là 2*n nút, với n là hằng số cho trước và được gọi là cấp của B-cây Cấu trúc dữ liệu của B-cây cấp n có đặc tính như sau: B-cây Mỗi trang có tối đa 2*n phần tử Mỗi trang, ngoại trừ trang gốc chứa ít nhất n phần tử. Trang gốc được phép chứa 1, 2, ... , 2*n phần tử Mỗi trang hoặc là trang lá (không có con) hoặc có m + 1 trang con, với m là số phần tử của trang này Tất cả các trang lá phải có cùng mức Mỗi phần tử trên một trang có thứ tự theo khoá tăng dần từ trái qua phải B-cây Ví dụ: B-cây cấp 2 có ba mức sau: Tất cả các trang chứa 2, 3, hay 4 phần tử ngoại trừ trang gốc chỉ chứa 1 phần tử Tất cả các trang lá xuất hiện ở cùng mức 3 B-cây Nếu dồn B-cây lại thành một mức duy nhất bằng cách chèn các trang con vào giữa các nút trong trang cha của chúng thì được các giá trị sắp theo thứ tự tăng dần Đây là sự mở rộng tự nhiên của cây tìm kiếm nhị phân Cài đặt B-cây const int N = 2; // cấp của B-cây const int NN = 4; // kích thước trang typedef struct Page* ref; struct Node { int key; // giá trị của nút ref pR; // trỏ đến trang con bên phải int count; // số lần xuất hiện của khóa // có giá trị bằng key }; Cài đặt B-cây struct Page { int m; // số phần tử của trang ref pL; // trỏ đến trang con bên trái Node e[NN]; // các nút (phtử) của trang }; ref root; // trỏ đến trang gốc Các phép toán trên B-cây Tìm kiếm và thêm vào B-cây: Nếu một nút được thêm vào trang chưa đầy (< 2*n) thì nút đó được thêm vào trang này Ngược lại, phải cấp thêm trang mới Ví dụ, có B-cây cấp 2 như sau: Các phép toán trên B-cây Nếu thêm vào nút 22, thực hiện các bước sau: Không thể thêm 22 và trang C vì trang này đã đầy (4 nút) Do đó, trang C được tách thành hai trang là C và D (trang mới) Các nút được phân bố đều vào C và D, nút giữa (30) được chuyển lên trang cha A Các phép toán trên B-cây Cấu trúc mới này vẫn giữ được các tính chất của B-cây. Các trang tách chứa đúng n nút Nút được chuyển lên trang cha có thể làm nó trang này bị tràn và gây ra sự tách trang lan truyền Các phép toán trên B-cây Giải thuật tìm kiếm và thêm vào như sau: Gọi x là khóa cần tìm a là trang hiện tại đang tìm x h là chiều cao của cây (h = 0: chiều cao không tăng, h = 1: chiều cao tăng) v là nút tạm có kiểu Node void search(int x, ref a, int &h, Node &v) { if(a == NULL) { Các phép toán trên B-cây // x không có trên a - h = 1 // chiều cao tăng - v.key = x - v.count = 1; - v.p = NULL; } else { // tìm x xem có trên a không - tìm kiếm nhị phân - if(found) // tìm thấy Tăng số lần xuất hiện khóa x lên 1 Các phép toán trên B-cây else // không thấy { Dựa vào kết quả tìm kiếm mà cho q trỏ đến trang con bên trái hay bên phải của trang a search(x, q, h, v); // q là trang con if(h) thì // thêm phần tử mới if(số phần tử trang hiện tại < 2n) Xen v vào trang hiện tại, cho h = 0 else Tách trang và chuyển phần tử giữa lên trang cha } } Các phép toán trên B-cây Ví dụ, tạo B-cây cấp 2 với giá trị lần lượt là: 20, 40, 10, 30, 15, 35, 7, 26, 18, 22, 5, 42, 13, 46, 27, 8, 32, 38, 24, 45, 25 Quá trình được diễn ra như sau: 1. Sau khi thêm các giá trị 20, 40, 10, 30 thì kết quả như sau: Các phép toán trên B-cây 2. Khi giá trị 15 được thêm vào, vì trang cấp 2 có tối đa 4 phần tử nên xảy ra việc tách trang (phần tử giữa 20 của dãy 10 15 30 20 40 được đưa lên trang cha mới): Các phép toán trên B-cây 3. Sau khi thêm các giá trị 35, 7, 26, 18: 4. Khi thêm giá trị 22, vì các trang lá có đủ 4 phần tử nên xảy ra việc tách trang (phần tử giữa 30 của dãy 22 26 30 35 40 được đưa lên trang cha): Các phép toán trên B-cây 5. Khi thêm giá trị 5 vào cũng xảy ra việc tách trang, phần tử giữa 10 của dãy 5 7 10 15 18 được đưa lên trang cha: Các phép toán trên B-cây 6. Sau khi thêm các giá trị 42, 13, 46, 27, 8: 7. Khi thêm giá trị 32 xảy ra việc tách trang, phần tử giữa 40 của dãy 32 35 40 42 46 được đưa lên trang cha Các phép toán trên B-cây 8. Sau khi thêm các giá trị 38, 24, 45: Các phép toán trên B-cây Khi thêm giá trị 25 xảy ra việc tách trang, phần tử giữa 25 của dãy 22 24 25 26 27 được đưa lên trang cha. Nhưng trang cha chứa đủ 4 phần tử nên tách trang xảy ra lan truyền. Trang cha được tách thành hai trang con và 25 được đưa lên trang cha mới: Các phép toán trên B-cây Tìm kiếm và loại bỏ khỏi B-cây: Xét hai trường hợp sau: 1. Phần tử bị loại bỏ ở trang lá: Trường hợp này được thực hiện dễ dàng 2. Phần tử bị loại bỏ không ở trang lá: Nó phải được thay thế Các phép toán trên B-cây Xét B-Cây sau: Khi loại bỏ nút 25 ở trang A, nút 24 của trang F (phần tử cực phải của cây con bên trái trang A) được đưa lên thay thế. Khi này trang F chỉ chứa 1 (< n) nút 22, phải đem nút 20 của trang B vào trang F và đem nút 18 của trang E vào trang B Các phép toán trên B-cây Sau khi loại bỏ nút 45: Các phép toán trên B-cây Khi loại bỏ nút 24, nút 22 của trang F sẽ thay thế. Khi này, trang F chỉ chứa nút 20, nhập trang F vào trang E và đem nút 18 của trang B vào trang E và hủy đi trang F. Nhưng khi này, trang B chỉ chứa nút 10 nên phải nhập trang C vào B và đưa nút 22 của trng A vào B, hủy trang A và C Các phép toán trên B-cây Sau khi loại bỏ nút 38: Khi loại bỏ nút 32, trang H chỉ chứa nút 35, phải nhập trang I vào trang H và đem nút 40 của trang B vào trang H, hủy bỏ trang I Các phép toán trên B-cây Khi loại bỏ nút 8: Các phép toán trên B-cây Khi loại bỏ nút 27, đem nút 30 của trang B vào G và nút 35 của trang H vào B Khi loại bỏ nút 46 và 13: Các phép toán trên B-cây Khi loại bỏ nút 42, nhập trang H vào G, đem nút 35 của trang B vào G, hủy trang H Khi loại bỏ nút 5, đem nút 10 của trang B vào D và nút 15 của trang E vào B: Các phép toán trên B-cây Khi loại bỏ nút 22, đem nút 26 của trang G vào B Khi loại bỏ nút 18, đem nút 26 của trang B vào E và nút 30 của trang G vào B Các phép toán trên B-cây Khi loại bỏ nút 26, nhập trang G vào E, đem nút 30 của trang B vào E, hủy trang G Các phép toán trên B-cây Khi loại bỏ nút 7, đem nút 15 của trang B vào trang D và nút 20 của trang E vào B Khi loại bỏ nút 35: Các phép toán trên B-cây Khi loại bỏ nút 15, nhập trang E vào D, đem nút 20 của trang B vào D, hủy trang E và B