Bináris fák és algoritmusaik

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.

Törlés és beszúrás

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.

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

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. Python nyelven a következőképp lehet implementálni egy ilyen fát.

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

  • Ha a beszúrandó adat kisebb, mint az aktuális csúcsban tárolt, akkor, ha a bal gyerek üres, eltároljuk a bal gyerekben, egyébként rekurzívan meghívjuk a bal gyerek beszúr metódusát.
  • Ha a beszúrandó elem nagyobb vagy egyenlő, akkor ugyanígy járunk el a jobb gyerekre

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.

Python Tutor link

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

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

Érdemes lekövetni!

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

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