B-fa
Kiejtés
- IPA: [ ˈpfɒ]
Főnév
B-fa
A B-fa (B-tree) egy önkiegyensúlyozó keresőfa, amelyet adatok rendezett tárolására és gyors keresésére, beszúrására, valamint törlésére használnak. A B-fa biztosítja, hogy a fa mindig kiegyensúlyozott maradjon, így a műveletek időbonyolultsága garantáltan logaritmikus ((O(n))).
Jellemzők
- Több kulcs egy csomópontban:
- Egy B-fa csomópontja több kulcsot is tárolhat.
- A kulcsok rendezettek egy csomóponton belül.
- Gyökér, belső csomópontok, levelek:
- A gyökérnek legalább egy kulcsa van.
- Az összes levél azonos mélységben található.
- Gyermekek száma:
- Ha egy csomópont (k) kulcsot tartalmaz, akkor pontosan (k+1) gyermeke lehet.
- Rugalmas méret:
- A csomópontok egy előre meghatározott minimális ((t)) és maximális ((2t-1)) számú kulcsot tartalmazhatnak, ahol (t) a B-fa rendje (minimum 2).
- Egyensúly:
- A fa mindig kiegyensúlyozott, azaz az összes levélcsomópont azonos távolságra van a gyökértől.
Műveletek
1. Keresés
A keresés egy adott kulcsra ((k)) a B-fában rekurzív vagy iteratív módon végezhető el. Minden csomópont kulcsait rendezetten tárolják, így az adott kulcs gyorsan megtalálható, vagy eldönthető, hogy melyik gyermekágat kell vizsgálni.
2. Beszúrás
- Nem teljes csomópont esetén:
- Ha a célcsomópontban van szabad hely, a kulcsot egyszerűen beszúrjuk.
- Teljes csomópont esetén:
- A telített csomópontot ketté kell osztani, és a középső kulcsot fel kell tolni a szülőbe.
- Ez a művelet rekurzívan feljebb vihet kulcsokat, és akár a gyökércsomópontot is megoszthatja, így a fa magassága nő.
3. Törlés
- Levélből:
- Ha a törlendő kulcs egy levélben van, egyszerűen eltávolítjuk.
- Belső csomópontból:
- A kulcs helyettesíthető az előtte vagy utána lévő legnagyobb vagy legkisebb kulccsal.
- Ha szükséges, csomópontok összevonására vagy kölcsönzésére van szükség a gyermekcsomópontok között.
Pszeudokód
Keresés B-fában
function BTreeSearch(x, k):
i = 1
amíg i <= n[x] és k > key[i][x]:
i = i + 1
ha i <= n[x] és k == key[i][x]:
térj vissza (x, i) # Kulcs megtalálva
ha leaf[x]:
térj vissza None # Kulcs nem található
térj vissza BTreeSearch(child[i][x], k)
Beszúrás B-fában
function BTreeInsert(T, k):
ha root[T] tele:
s = CreateNode()
root[T] = s
SplitChild(s, 1, root[T])
InsertNonFull(s, k)
különben:
InsertNonFull(root[T], k)
function InsertNonFull(x, k):
ha leaf[x]:
add k-t megfelelő helyre key[x]-ben
különben:
keressük meg child[i][x]-et, ahová k kerülne
ha child[i][x] tele:
SplitChild(x, i, child[i][x])
InsertNonFull(child[i][x], k)
function SplitChild(x, i, y):
z = CreateNode()
z lesz az y második fele
középső kulcs felkerül az x-be
Python implementáció
class BTreeNode:
def __init__(self, t, leaf=False):
self.t = t # A B-fa rendje
self.keys = [] # Kulcsok
self.children = [] # Gyermekek
self.leaf = leaf # Levél-e a csomópont
class BTree:
def __init__(self, t):
self.root = BTreeNode(t, leaf=True)
self.t = t
def search(self, node, k):
i = 0
while i < len(node.keys) and k > node.keys[i]:
i += 1
if i < len(node.keys) and node.keys[i] == k:
return node, i
if node.leaf:
return None
return self.search(node.children[i], k)
def insert(self, k):
root = self.root
if len(root.keys) == 2 * self.t - 1:
s = BTreeNode(self.t)
self.root = s
s.children.append(root)
self.split_child(s, 0)
self.insert_non_full(s, k)
else:
self.insert_non_full(root, k)
def insert_non_full(self, node, k):
if node.leaf:
node.keys.append(k)
node.keys.sort()
else:
i = len(node.keys) - 1
while i >= 0 and k < node.keys[i]:
i -= 1
i += 1
if len(node.children[i].keys) == 2 * self.t - 1:
self.split_child(node, i)
if k > node.keys[i]:
i += 1
self.insert_non_full(node.children[i], k)
def split_child(self, parent, i):
t = self.t
child = parent.children[i]
new_child = BTreeNode(t, child.leaf)
parent.keys.insert(i, child.keys[t - 1])
parent.children.insert(i + 1, new_child)
new_child.keys = child.keys[t:]
child.keys = child.keys[:t - 1]
if not child.leaf:
new_child.children = child.children[t:]
child.children = child.children[:t]
# Példa használat
btree = BTree(2) # B-fa rendje 2
btree.insert(10)
btree.insert(20)
btree.insert(5)
btree.insert(6)
btree.insert(12)
node, index = btree.search(btree.root, 12)
if node:
print(f"Kulcs megtalálva: {node.keys[index]}")
else:
print("Kulcs nem található.")
Kimenet:
Kulcs megtalálva: 12
Összegzés
A B-fa tulajdonságai: - Időbonyolultság: - Keresés, beszúrás, törlés: (O(n)) - Előnyök: - Nagy adatszerkezetek hatékony kezelése. - Disk alapú tárolásra is alkalmas (pl. adatbázisokban). - Hátrányok: - Az implementáció összetettebb, mint más adatszerkezeteké.
Alkalmazása széleskörű, például adatbázisokban, fájlrendszerekben és keresőmotorokban.