Előző alkalommal megismerkedtünk a bináris kereséssel. Előnye, hogy $O(\log(n))$ idő alatt megtalálja a listában a keresett elemet, annak indexével együtt, hátránya viszont, hogy a listát rendezve kell tárolnunk. Egy listát akkor érdemes rendezve tárolni, ha már nem szúrunk bele újabb elemeket, vagy nem törlünk belőle elemet.
Természetesen erre is van Python parancs, de hogy tudjuk, mit csinál, írjuk meg kézzel. Ha törölni akarjuk az i.
elemet, akkor i
-től a lista végéig az összes elemet eggyel előrébb kell pakolni. Ez akár n
lépésbe is kerülhet, ha a lista hossza n
.
def del_from_list(l, i):
if i >= len(l):
return
else:
for j in range(i,len(l)-1):
l[j] = l[j+1]
del l[-1]
L = [1,2,3,4,5,6]
del_from_list(L,3)
print L
def insert_into_list(l, i, x):
if i >= len(l):
l.append(x)
else:
l.append(l[-1])
for j in range(len(l)-2,i,-1):
l[j] = l[j-1]
l[i] = x
L = [1,2,3,4,5,6]
insert_into_list(L,6,"X")
print L
Látjuk, hogy törölni és beszúrni is költséges. Mindenesetre, ne kézzel töröljünk, hiszen a Python az l.insert(i,x)
és a del l[i]
parancsokkal mindezt elvégzi, ráadásul sokkal gyorsabban mint mi, hiszen ezek a függvények/metódusok közvetlenül elérik a memóriát.
A bináris fa egy olyan irányított gráf, amelynek vagy egy gyökere, továbbá minden csúcsnak van legfeljebb két gyereke. Python nyelven a következőképp lehet implementálni egy ilyen fát.
class Node(object):
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def insert(self, data):
if self.data > data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
else:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
A bináris fa jelen implementációja eleve rendezve tárol elemeket a fa csúcsaiban. A módszer az, hogy agy csúcs üres (None
értékű) bal- és jobb gyerekkel jön létre. Ha be akarunk szúrni egy elemet, akkor a következőképp járunk el:
Most bővítsük ki az osztályunkat egy to_list()
metódussal. Ez a fa elemeit rendezett listaként adja vissza. Először létrehozunk egy üres listát. Ha a bal gyerek nem üres, meghívjuk rekurzívan a metódust, és hozzáadjuk a listához a visszaadott listát, majd hozzáadjuk a listához az aktuális Node
adatát, majd a jobb gyerekre is meghívjuk a to_list
metódust és a visszaadott listát hozzáadjuk a eddigiekhez.
class Node(object):
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def insert(self, data):
if self.data > data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
else:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
def to_list(self):
s = []
if self.left is not None:
s += self.left.to_list()
s.append(self.data)
if self.right is not None:
s += self.right.to_list()
return s
root = Node(5)
root.insert(4)
root.insert(1)
root.insert(7)
print root.to_list()
Mit nyertünk ezzel? Először is, az adatainkat rendezve tároljuk, beszúrni pedig átlagosan $O(\log(n))$ lépésben tudunk, hiszen a fa mélysége nagyjából ennyi. Persze ez nem mindig igaz, hiszen ha az adataink eleve rendezve érkeznek, a fa nem lesz kiegyensúlyozott. Nézzük meg!
root = Node(5)
root.insert(4)
root.insert(3)
root.insert(2)
root.insert(1)
Önkiegyensúlyozó, AVL-fákról az Algoritmuselmélet tárgy keretein belül lesz szó. Most implementáljuk a find(data)
metódust, ami visszaadja azt a csúcsot, ami a data
adatot tárolja.
class Node(object):
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def insert(self, data):
if self.data > data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
else:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
def to_list(self):
s = []
if self.left is not None:
s += self.left.to_list()
s.append(self.data)
if self.right is not None:
s += self.right.to_list()
return s
def find(self, data):
if data == self.data:
return self
elif data < self.data and self.left is not None:
return self.left.find(data)
elif self.right is not None:
return self.right.find(data)
else:
return None
root = Node(5)
root.insert(4)
root.insert(1)
root.insert(7)
print root.find(1)
Még nem beszéltünk a törlésről. Ha a törlendő adat egy levélben van (nincs gyereke), vagy csak egy gyereke van, a helyzet egyszerű: kitöröljük és az egyetlen gyerekével (ha egyáltalán létezik) helyettesítjük. Ha két gyereke van, megkeressük a legkisebb elemet, ami még nagyobb nála (ez a leg-baloldalibb levél a jobb oldali részfában) és azzal helyettesítjük, a levelet pedig töröljük.
class Node(object):
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def insert(self, data):
if self.data > data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
else:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
def to_list(self):
s = []
if self.left is not None:
s += self.left.to_list()
s.append(self.data)
if self.right is not None:
s += self.right.to_list()
return s
def find(self, data):
if data == self.data:
return self
elif data < self.data and self.left is not None:
return self.left.find(data)
elif self.right is not None:
return self.right.find(data)
else:
return None
def minValue(self):
current = self
while(current.left is not None):
current = current.left
return current
def deleteNode(node, data):
if node is None:
return root
if data < node.data:
node.left = deleteNode(node.left, data)
elif data > node.data:
node.right = deleteNode(node.right, data)
else:
if node.left is None :
temp = node.right
node = None
return temp
elif node.right is None :
temp = node.left
node = None
return temp
temp = node.right.minValue()
node.data = temp.data
node.right = deleteNode(node.right, temp.data)
return node
root = Node(5)
root.insert(4)
root.insert(1)
root.insert(8)
root.insert(6)
root.insert(7)
root = deleteNode(root,7)
print root.data
Például műveletek elvégzésére. Az alábbi fa olyan, hogy vagy két gyereke van egy csúcsnak, vagy egy sem. Ha két gyereke van, akkor a csúcs egy műveletet reprezentál, ha nincs gyereke, akkor egy szám.
class Node:
pass
def calculate(node):
if node.data == "+":
return calculate(node.left) + calculate(node.right)
elif node.data == "*":
return calculate(node.left) * calculate(node.right)
else:
return node.data
def write(node):
if node.data == "+" or node.data == "*":
return "({})".format(write(node.left)) + str(node.data) + "({})".format(write(node.right))
else:
return node.data
x0 = Node()
x0.data = "+"
x1 = Node()
x1.data = "*"
x2 = Node()
x2.data = 7
x3 = Node()
x3.data = 5
x1.left = x2
x1.right = x3
x4 = Node()
x4.data = -3
x0.left = x1
x0.right = x4
print calculate(x0)
print write(x0)
A fenti kódot rövidített objektumjelöléssel írtam meg, ráadásul csak a +
és a *
jeleket ismeri. A kiírás pedig a kelleténél dagályosabb. Természetesen folytatjuk.