Legyen egy lista, amiben meg akarunk találni egy elemet. Tegyük fel, hogy csak különböző valós számok vannak benne. Ha végigmegyünk az elemeken amíg meg nem találjuk, az annyi ideig tart, mint a lista hossza.
Ennél lehet jobbat is, ha a lista már rendezve van. Előnye, hogy $O(\log(n))$ idő alatt megtalálja a listában a keresett elemet, hátránya viszont, hogy a listát rendezni kell előtte. Akkor érdemes használni, ha már nem szúrunk bele újabb elemeket, vagy nem törlünk belőle elemet. Ekkor egyszer kell rendezni, utána már gyorsan lehet benne keresni.
Bináris keresés
import sys
def binary_search(l, x):
a = 0
b = len(l)-1
while a <= b:
i = (a + b)/2
print >>sys.stderr, i,
if l[i] < x:
a = i+1
elif l[i] > x:
b = i-1
else:
print >>sys.stderr
return i
print >>sys.stderr
return None
l = [3,10,-1,3.14,20,2]
l.sort()
print l
print binary_search(l,10)
Ez a keresés legrosszabb esetben $\log_2(n)$ felső egészrésze lépést vesz igénybe, mert minden lépésben feleződik a lehetséges helyek száma.
for i in range(-1,11):
print binary_search(range(10),i)
Ebben az algoritmusban egy fontos kritérium, hogy előre rendezve legyen a lista. Ez problémás, amikor hozzáadunk egy új elemet. Ezt könnyítendő megtehetjük, hogy úgy szúrunk be elemet, hogy az a megfelelő helyre kerüljön és akkor mindvégig rendezve is marad a lista (törlésnél nem romlik el a rendezés).
Írjunk osztályt rendezett lista kezelésére.
class OrderedList(object):
def __init__(self, elements=[]):
self.l = sorted(elements)
def search(self, x):
a = 0
b = len(self.l)-1
while a <= b:
i = (a + b)/2
if self.l[i] < x:
a = i+1
elif self.l[i] > x:
b = i-1
else:
return i
return None
def insert(self, x):
a = 0
b = len(self.l)-1
while a <= b:
i = (a + b)/2
if self.l[i] < x:
a = i+1
elif self.l[i] > x:
b = i-1
else:
return
self.l.insert(a, x)
def erase(self, index):
if index >= 0 and index < len(self.l):
del self.l[index]
def __iter__(self):
return iter(self.l)
def __repr__(self):
return str(self.l)
l = OrderedList([1, -1, 2])
print l
l.insert(5)
print l
l.erase(2)
print l
l.insert(3.14)
l.insert(0)
print l
print l.search(1)
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 (ága vagy kifelé mutató éle).
Most olyan fát fogunk implementálni, ami azt csinálja, mint az előző lista, de fában tárolja az elemeket.
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)
elif self.data < data:
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 a 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 ág 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 ágra 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)
elif self.data < data:
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)
elif self.data < data:
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(4)
print root.find(4).to_list()
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)
elif self.data < data:
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.to_list()
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.