37
b. Setiap
node dapat
berisi
maksimal
2t-1 key disebut
keadaan
penuh.
Dengan
demikian,
sebuah
node internal dapat
mempunyai maksimal 2t node anak.
Tinggi
untuk
sebuah
B-Tree
dengan
jumlah
data
n
dalam
keadaan
terburuk adalah :
h
=
log
t
n
+
1
2
Keterangan:
h = tinggi
t
=
derajat minimum
n = banyak data (Cormen, 2001, p447)
Operasi dasar pada B-Tree terdiri dari :
a. Operasi Searching
Prosedur
pencarian B-Tree
hampir sama dengan pencarian
pada
tree
umumnya,
namum
pada
setiap
node
internal,
terdapat
(n[x]
+
1)
cara
penentuan
percabangan. Pencarian
B-Tree
menggunakan
inputan sebagai pointer
dari root
x
dan
key
k
untuk
dicari
dalam
subtreenya.
Jika
terdapat
key
k
yang
dicari,
maka
akan dikembalikan pasangan
nilai
(y, i) dengan node y dan
indeks
i
sehingga
key
i
[y]
=
k,
sedangkan
jika
tidak
ditemukan, akan
dikembalikan nilai NIL.
B-TREE-SEARCH (x, k)
i
1
 |