Bài giảng B-Tree

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

Thêm vào BST

Báo xấu

97
lượt xem 8
download

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

Bài giảng B-Tree được biên soạn nhằm giúp cho các bạn biết cách để xóa một khóa ra khỏi một B-cây. Mời các bạn tham khảo bài giảng để nắm bắt nội dung chi tiết. Với các bạn chuyên ngành Công nghệ thông tin thì đây là tài liệu hữu ích.

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 B-Tree

B-Tree 1
Xoùa moät khoùa khoûi moät B-caây Thuû tuïc B-TREE-DELETE(x, k) ñeå xoùa khoùa k khoûi caây con coù goác taïi x baûo ñaûm raèng khi B-TREE-DELETE ñöôïc goïi ñeä quy leân x thì — soá khoùa trong x phaûi  t (baäc toái thieåu cuûa caây). Do ñoù, khi thuû tuïc thöïc thi, ñoâi khi moät khoùa ñöôïc di chuyeån (töø moät nuùt thích hôïp khaùc) vaøo moät nuùt tröôùc khi ñeä quy xuoáng nuùt ñoù. 2
Xoùa moät khoùa khoûi moät B-caây B-TREE-DELETE(x, k) 1. Neáu khoùa k coù trong nuùt x vaø x laø moät nuùt laù thì xoùa k khoûi x, rồi tái cân bằng (phần sau). 2. Neáu khoùa k coù trong nuùt x vaø x laø moät nuùt trong thì a. Neáu nuùt con y ôû tröôùc k coù ít nhaát t khoùa thì tìm khoùa tröôùc (predecessor) k’ cuûa k trong caây con coù goác taïi y. Xoùa k’, trong nuùt x thay k baèng k’. (Tìm vaø xoùa k’ coù theå thöïc thi trong moät löôït ñi xuoáng duy nhaát.) x  k  y … caây con coù goác taïi y 3
Xoùa moät khoùa khoûi moät B-caây B-TREE-DELETE(x, k) 1. ... 2. Neáu khoùa k coù trong nuùt x vaø x laø moät nuùt trong thì a. ... b. Töông töï, neáu nuùt con z ôû sau k coù ít nhaát t khoùa thì tìm khoùa sau (successor) k’ cuûa k trong caây con coù goác taïi z. Xoùa k’, trong x thay k baèng k’. (Tìm vaø xoùa k’ coù theå thöïc thi trong moät löôït ñi xuoáng duy nhaát.) x  k  z … caây con coù goác taïi z 4
Xoùa moät khoùa khoûi moät B-caây B-TREE-DELETE(x, k) 1. ... 2. Neáu khoùa k coù trong nuùt x vaø x laø moät nuùt trong thì a. ... b. ... c. Neáu khoâng, caû y laån z ñeàu chæ coù t  1 khoùa, hôïp nhaát k vaø nguyeân caû z vaøo y, thaønh ra x maát k vaø con troû ñeán z , vaø baây giôø y chöùa 2t  1 khoùa. Giaûi phoùng (free) z vaø goïi ñeä quy B-TREE-DELETE(y, k) ñeå xoùa k khoûi caây con coù goác y. x  k  y  k’ z l’  5
Xoùa moät khoùa khoûi moät B-caây (tieáp) Minh họa bước hợp nhất x  k  y  k’ z l’  x   y  k’ k l’  z 6
Xoùa moät khoùa khoûi moät B-caây B-TREE-DELETE(x, k) 1. ... 2. ... 3. Neáu khoùa k khoâng coù trong nuùt trong x thì xaùc ñònh goác ci[x] cuûa caây con chöùa k, neáu k coù trong caây. Neáu ci [x] chæ coù t  1 khoùa, thöïc thi böôùc 3a hay 3b neáu caàn (ñeå ñaûm baûo raèng giaûi thuaät, khi ñöôïc goïi ñeä quy, seõ xuoáng moät nuùt chöùa ít nhaát t khoùa). Xong roài goïi B-TREE- DELETE leân nuùt con thích hôïp cuûa x. 7
Xoùa moät khoùa khoûi moät B-caây (tieáp) 3. ... a. Neáu ci [x] chæ coù t  1 khoùa, nhöng laïi coù moät nuùt anh em beân phaûi (hay beân traùi) vôùi ít nhaát t khoùa, thì cho nuùt ci [x] theâm moät khoùa baèng caùch ñem moät khoùa töø x xuoáng ci [x], ñem moät khoùa töø nuùt anh em cuûa ci [x] leân x, vaø ñem con troû töông öùng töø nuùt anh em vaøo nuùt ci [x]. x  m  ci [x] nuùt anh em beân phaûi  l n n’  8
Xoùa moät khoùa khoûi moät B-caây (tieáp) Minh hoïa x  m  ci [x]  l n n’  x  n  ci [x]  l m n’  9
Xoùa moät khoùa khoûi moät B-caây (tieáp) 3. ... a. ... b. Neáu ci [x] vaø moïi nuùt anh em cuûa noù chæ coù t  1 khoùa, thì hôïp nhaát ci [x] vaø moät nuùt anh em baèng caùch ñem moät khoùa töø x xuoáng nuùt môùi taïo, khoùa naøy seõ laø khoùa giöõa cuûa nuùt. x  l l’  ci [x]  h m  m’ n  10
Xoùa moät khoùa khoûi moät B-caây (tieáp) Minh hoïa x  l l’  ci [x]  h m  m’ n  x  l’   h l m  m’ n  11
Xoùa moät khoùa khoûi moät B-caây (tieáp) Thuû tuïc B-TREE-DELETE caàn — soá truy caäp leân ñóa laø O(h) vì coù O(1) laàn goïi DISK-READ vaø DISK-WRITE giöõa caùc goïi ñeä quy cuûa thuû tuïc. — thôøi gian CPU cuûa thuû tuïc laø O(t h) = O(t log t n). 12
Ví duï cho caùc tröôøng hôïp khi xoùa moät khoùa khoûi moät B-caây Cho moät B-caây coù baäc toái thieåu t = 3 ° Caây luùc ñaàu, xoùa F khoûi caây P C G M T X A B D E F J K L N O Q R S U V Y Z - F ñaõ ñöôïc xoùa: tröôøng hôïp 1 P C G M T X A B D E J K L N O Q R S U V Y Z 13
Ví duï cho caùc tröôøng hôïp khi xoùa moät khoùa khoûi moät B-caây ° Xoùa M khoûi caây: tröôøng hôïp 2a P C G M T X A B D E J K L N O Q R S U V Y Z - M ñaõ ñöôïc xoùa: P C G L T X A B D E J K N O Q R S U V Y Z 14
Ví duï cho caùc tröôøng hôïp khi xoùa moät khoùa khoûi moät B-caây ° Xoùa G khoûi caây: tröôøng hôïp 2c P C G L T X A B DD EE G JJ K K N O Q R S U V Y Z - G ñaõ ñöôïc xoùa: P C L T X A B D E J K N O Q R S U V Y Z 15
Ví duï cho caùc tröôøng hôïp khi xoùa moät khoùa khoûi moät B-caây ° Xoùa D khoûi caây: tröôøng hôïp 3b P C L T X A B D E J K N O Q R S U V Y Z C L P T X A B D E J K N O Q R S U V Y Z - D ñaõ ñöôïc xoùa: C L P T X A B E J K N O Q R S U V Y Z 16
Ví duï cho caùc tröôøng hôïp khi xoùa moät khoùa khoûi moät B-caây ° Xoùa B khoûi caây: tröôøng hôïp 3a C L P T X A B E J K N O Q R S U V Y Z E L P T X A B C J K N O Q R S U V Y Z - B ñaõ ñöôïc xoùa khoûi caây: E L P T X A C J K N O Q R S U V Y Z 17