Bài giảng Phân tích thiết kế giải thuật: Chương 4 - ĐH Bách khoa

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PPT | Số trang:36

Thêm vào BST

Báo xấu

51
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Phân tích thiết kế giải thuật: Chương 4 - B-Cây bao gồm những nội dung về cấu trúc dữ liệu trong bộ nhớ ngoài; truy cập đĩa; các thao tác lên một đĩa; hệ số phân nhánh; định nghĩa của B-cây; các thao tác lên một B-cây và một số nội dung khác.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Phân tích thiết kế giải thuật: Chương 4 - ĐH Bách khoa

BCây 23.2.2004 Ch. 4: BTrees 1
Cấu trúc dữ liệu trong bộ nhớ ngoài ° Bcây tổng quát hoá cây tìm kiếm nhị phân. – “Hệ số phân nhánh” (branching factor) ° Bcây là cây tìm kiếm cân bằng được thiết kế để làm việc hữu hiệu trong bộ nhớ ngoài (đĩa cứng). – Bộ nhớ chính (main memory) – Bộ nhớ ngoài (secondary storage) ° Disk – Track – Page ° Thời gian chạy gồm – số các truy cập vào đĩa – thời gian CPU 23.2.2004 Ch. 4: BTrees 2
Truy cập đĩa ° Một nút của Bcây thường chiếm nguyên cả một disk page. ° Hệ số phân nhánh tùy thuộc vào tỉ lệ giữa kích thước của khóa và kích thước của disk page. 23.2.2004 Ch. 4: BTrees 3
Các thao tác lên một đĩa ° Cho x là một con trỏ đến một đối tượng (ví dụ: một nút của một B cây). Đối tượng x có thể có nhiều trường – Nếu x nằm trong bộ nhớ chính, truy cập các trường của x như thường lệ, ví dụ như key[x], leaf [x],... – Nếu x còn nằm trên đĩa thì dùng DISKREAD(x) để đọc nó vào bộ nhớ chính. – Nếu x đã thay đổi thì dùng DISKWRITE(x) để trữ nó vào đĩa. ° Cách làm việc tiêu biểu với một đối tượng x ... x một con trỏ đến một đối tượng nào đó DISKREAD(x) các thao tác truy cập/thay đổi các trường của x DISKWRITE(x) các thao tác không thay đổi một trường của x ... 23.2.2004 Ch. 4: BTrees 4
Hệ số phân nhánh ° Ví dụ một Bcây mà: – mỗi nút có 1000 khóa (số trong mỗi nút là số khóa nó chứa), tức là Bcây có hệ số phân nhánh là 1001 root[T] 1 nút 1000 1000 khóa 1001 1001 nút 1000 1000 1000 1.001.000 khóa 1001 1001 1001 1.002.001 nút 1000 1000 1000 1.002.001.000 khóa 23.2.2004 Ch. 4: BTrees 5
Định nghĩa của Bcây Một Bcây T là một cây có gốc, mà gốc là root[T], có các tính chất sau ° Mỗi nút x có các trường sau – n[x], số lượng khóa đang được chứa trong nút x – các khóa: có n[x] khóa, được xếp theo thứ tự không giảm, tức là key1[x] key2[x] keyn[x ][x] – leaf [x], có trị bool là TRUE nếu x là một lá FALSE nếu x là một nút trong ° Mỗi nút trong x chứa n[x] 1 con trỏ c1 [x], c2 [x],…, cn[x ]+1[x] đến các nút con của nó. 23.2.2004 Ch. 4: BTrees 6
Định nghĩa của Bcây (tiếp) ° Nếu ki là khóa trữ trong cây con có gốc là ci [x] thì • k1 key1[x] k2 key2[x] kn[x ] keyn[x ][x] kn[x ]+1 ° Tất cả các lá có cùng một độ sâu, đó là chiều cao h của cây ° Có một số nguyên t 2 gọi là bậc tối thiểu của cây sao cho – Mọi nút không phải là nút gốc phải có ít nhất t 1 khóa. Nếu cây không trống thì nút gốc phải có ít nhất một khóa. – Mổi nút có thể chứa tối đa 2t 1 khóa. Một nút là đầy nếu nó chứa đúng 2t 1 khóa. 23.2.2004 Ch. 4: BTrees 7
Chiều cao của một Bcây Định lý Nếu n 1 thì mọi Bcây T với n khóa, chiều cao h, và bậc tối thiểu t 2 n 1 có h log t 2 Chứng minh Có tối thiểu 2 nút ở độ sâu 1, 2t nút ở độ sâu 2,..., và 2t h 1 nút ở độ sâu h. Vậy số khóa tối thi h ểu là n 1 (t 1) 2t i 1 i 1 th 1 1 2(t 1) t 1 2t h 1 n 1 th 2 Do đó , từ đây suy ra định lý. 23.2.2004 Ch. 4: BTrees 8
Số khóa tối thiểu trong một Bcây ° Bcây sao cho mọi nút đều có t 1 khóa, ngoại trừ nút gốc chỉ có 1 khóa. — Vậy số khóa trong cây là tối thiểu cho mọi cây có bậc tối thiểu là t và chiều cao là h. 1 độ sâu 0, số nút: 1 t 1 độ sâu 1, số nút: 2 t 1 ... ... độ sâu 2, số nút: 2t t 1 ... t 1 t 1 ... t 1 ... ... ... ... t 1 ... t 1 t 1 ... t 1 t 1 ... t 1 t 1 ... t 1 độ sâu 3, số nút: 2t2 23.2.2004 Ch. 4: BTrees 9
Các thao tác lên một Bcây ° Các thao tác lên một Bcây: – BTREESEARCH – BTREECREATE – BTREEINSERT – BTREEDELETE ° Trong các thủ tục trên ta quy ước: – Gốc của Bcây luôn luôn nằm trong bộ nhớ chính. – Bất kỳ một nút mà là một tham số được truyền đi trong một thủ tục thì đều đã thực thi thao tác DISKREAD lên nó. 23.2.2004 Ch. 4: BTrees 10
Tìm trong một Bcây Thủ tục để tìm một khóa trong một Bcây — Input: một con trỏ chỉ đến nút gốc x của một cây con, và một khóa k cần tìm trong cây con. — Output: nếu k có trong cây thì trả về một cặp (y, i) gồm một nút y và một chỉ số i sao cho keyi [y] = k nếu k không có trong cây thì trả về NIL. BTREESEARCH(x, k) 1 i 1 2 while i n[x] and k keyi [x] 3 do i i 1 4 if i n[x] and k = keyi [x] 5 then return (x, i) 6 if leaf [x] 7 then return NIL 8 else DISKREAD(ci [x]) 9 return BTREESEARCH(ci [x], k) 23.2.2004 Ch. 4: BTrees 11
Tìm trong một Bcây (tiếp) ° Các nút mà giải thuật truy cập tạo nên một đường đi từ gốc xuống đến nút có chứa khóa (nếu có). Thời gian CPU để xử lý mỗi nút là O(t). ° Do đó – số disk pages mà BTREESEARCH truy cập là (h) = (log t n), với h là chiều cao của cây, n là số khoá của cây. – BTREESEARCH cần thời gian CPU O(t h) = O(t log t n). 23.2.2004 Ch. 4: BTrees 12
Tạo một Bcây trống Thủ tục để tạo một nút gốc trống ° Gọi thủ tục ALLOCATENODE để chiếm một disk page làm một nút mới. BTREECREATE(T ) 1 x ALLOCATENODE() 2 leaf [x] TRUE 3 n[x] 0 4 DISKWRITE(x) 5 root[T] x ° BTREECREATE cần O(1) thời gian CPU và O(1) disk operations. 23.2.2004 Ch. 4: BTrees 13
Chèn một khóa vào một Bcây ° Khi một nút y là đầy (n[y] = 2t 1), định nghĩa khóa giữa (median key) của y là khóa keyt [y]. ° Ta sẽ chèn khóa vào một lá của cây. Để tránh trường hợp chèn khóa vào một lá đã đầy, ta cần một thao tác tách (split) một nút đầy y. Thao tác này – tách nút đầy y quanh nút giữa của nó thành hai nút, mỗi nút có t 1 khóa – di chuyển nút giữa lên nút cha của y (phải là nút không đầy) vào một vị trí thích hợp. ° Để chèn khóa mà chỉ cần một lượt đi từ nút gốc đến một lá, ta sẽ tách mọi nút đầy mà ta gặp trên đường đi từ gốc đến nút lá. – Phải đảm bảo được rằng khi tách một nút đầy y thì nút cha của nó phải là không đầy. 23.2.2004 Ch. 4: BTrees 14
Ví dụ tách một nút đầy ° Bậc tối thiểu t = 4. Vậy số khóa tối đa của một nút là 7. ° Tách nút đầy y là con của nút không đầy x. [ x] [x] [1 x] [x] [1 x] y i 1 key i yi yi ke key ke i x ke N W N S W y = ci [x] y = ci [x] z = ci 1[x] P Q R S T U V P Q R T U V T 1 T2 T 3 T 4 T5 T 6 T 7 T8 T1 T 2 T 3 T4 T5 T 6 T 7 T8 23.2.2004 Ch. 4: BTrees 15
Tách một nút của một Bcây Thủ tục BTREESPLITCHILD – Input: một nút trong không đầy x, một chỉ số i, và một nút y sao cho y = ci [x] là một nút con đầy của x – Thủ tục tách y thành hai nút và chỉnh x để cho x có thêm một nút con. BTREESPLITCHILD(x, i, y) 1 z ALLOCATENODE 2 leaf [z] leaf [y] 3 n[z] t 1 4 for j 1 to t 1 5 do keyj [z] keyj + t [y] 6 if not leaf [y] 7 then for j 1 to t 8 do cj [z] cj + t [y] 9 n[y] t 1 23.2.2004 Ch. 4: BTrees 16
Tách một nút của một Bcây (tiếp) 10 for j n[x] 1 downto i 1 11 do cj +1 [x] cj [x] 12 ci +1 [x] z 13 for j n[x] downto i 14 do keyj +1 [x] keyj [x] 15 keyi [x] keyt [y] 16 n[x] n[x] 1 17 DISKWRITE(y) 18 DISKWRITE(z) 19 DISKWRITE(x) 23.2.2004 Ch. 4: BTrees 17
Tách một nút của một Bcây (tiếp) ° BTREESPLITCHILD cần (t) thời gian CPU (các dòng 45 và 78) – O(1) disk operations (các dòng 1719). 23.2.2004 Ch. 4: BTrees 18
Chèn một khóa vào trong một Bcây Thủ tục BTREEINSERT để chèn một khóa k vào một Bcây T. — Thủ tục gọi BTREESPLITCHILD để đảm bảo khi gọi đệ quy thì sẽ không bao giờ xuống một nút đã đầy. BTREEINSERT(T, k) 1 r root[T ] 2 if n[r] = 2t 1 3 then s ALLOCATENODE() 4 root[T] s 5 leaf [s] FALSE 6 n[s] 0 7 c1[s] r 8 BTREESPLITCHILD(s, 1, r) 9 BTREEINSERTNONFULL(s, k) 10 else BTREEINSERTNONFULL(r, k) 23.2.2004 Ch. 4: BTrees 19
Tách một nút gốc đầy ° Ví dụ: tách một nút gốc đầy của một Bcây mà bậc tối thiểu là t = 4. ° Nút gốc mới là s. Nút gốc cũ r được tách thành hai nút con của s. ° Chiều cao của một Bcây tăng thêm 1 mỗi khi nút gốc được tách. root[T ] s H root[T ] r r A D F H L N P A D F L N P T1 T2 T3 T4 T5 T6 T7 T8 T1 T2 T3 T4 T5 T6 T7 T8 23.2.2004 Ch. 4: BTrees 20