Bináris fák és algoritmusaik

Bináris keresés

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.

  • lineáris vagy
  • $O(n)$ azaz "ordó $n$"

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

  • Nézzük meg hogy a lista közepe nagyobb-e vagy kisebb, mint a keresett elem.
    • Ha kisebb, akkor a keresett elem ez után kell legyen.
      • Ekkor folytassuk az első lépéstől a lista második felében keresve.
    • Ha nagyobb, akkor a keresett elem ez előtt kell legyen.
      • Ekkor folytassuk az első lépéstől a lista első felében keresve.
    • Ha egyenlő, akkor metaláltuk.
In [1]:
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
In [2]:
l = [3,10,-1,3.14,20,2]
l.sort()
print l
print binary_search(l,10)
[-1, 2, 3, 3.14, 10, 20]
4
2 4

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.

In [3]:
for i in range(-1,11):
    print binary_search(range(10),i)
None
0
1
2
3
4
5
6
7
8
9
None
4 1 0
4 1 0
4 1
4 1 2
4 1 2 3
4
4 7 5
4 7 5 6
4 7
4 7 8
4 7 8 9
4 7 8 9

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.

In [4]:
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)
In [5]:
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)
[-1, 1, 2]
[-1, 1, 2, 5]
[-1, 1, 5]
[-1, 0, 1, 3.14, 5]
2

Bináris fák

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.

In [6]:
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:

  • Ha a beszúrandó adat kisebb, mint az aktuális csúcsban tárolt, akkor, ha a bal oldal üres, eltároljuk a bal ágon, egyébként rekurzívan meghívjuk a bal oldal beszúr metódusát.
  • Ha a beszúrandó elem nagyobb, akkor ugyanígy járunk el a jobb oldallal.
  • Ha egyenlő, akkor már ott van, akkor nem csinálunk semmit.

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.

Python Tutor link

In [7]:
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()
[1, 4, 5, 7]

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!

In [8]:
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.

Python Tutor link

In [9]:
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()
<__main__.Node object at 0x00000000088BB400>
[1, 4]

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.

Érdemes lekövetni!

In [10]:
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()
[1, 4, 5, 6, 8]

Mire jók a bináris fák?

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.

In [11]:
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)
32
((7)*(5))+(-3)

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.