Bináris fák és algoritmusaik

Bináris keresés

Vegyünk egy különböző valós számokból álló $n$-elemű listát. Keressünk meg benne egy adott számot. Végigmenni az elemeken amíg meg nem találjuk, átlagosan $n/2$ összehasonlítást, legrosszabb esetben $n$ összehasonlítást igényel. Ez az algoritmus tehát a lista hosszának konstansszorosányi műveletettel megoldható, amit úgy fejezünk ki, hogy az algoritmus a műveletigénye a lista hosszában lineáris, azaz $O(n)$ (estsd: ordó $n$).

Ennél lehet gyorsabban is, a bináris kereséssel, ha a lista már rendezve van. Ez $O(\log(n))$ idő alatt megtalálja a listában a keresett elemet. Akkor érdemes használni, ha több elemet is meg kell keresni a listában: ekkor egyszer kell rendezni, utána már gyorsan lehet benne keresni elemeket.

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(i, end=' ', file=sys.stderr)
        if l[i] < x:
            a = i+1
        elif l[i] > x:
            b = i-1
        else:
            print(file=sys.stderr)
            return i
    print(file=sys.stderr)
    return None

stderr (standard error) a Linux redszereken az a file ahová egy processz írni tudja a hibaüzeneteket. A terminálról futó processzek esetén ez a terminálon jelenik meg a stdout (standard output) kimenetekkel együtt. A jupyter halvány színnel különbözteti meg az outputtól. A fenti kódban nyomkövetésre használjuk, elkülönítendő a standard kimenettől.

In [2]:
l = [3, 10, -1, 3.14, 20, 2, 11, 12, 1]
l.sort()
print(l)
b = binary_search(l, 10)
print(b, l[b])

[-1, 1, 2, 3, 3.14, 10, 11, 12, 20]
5 10

4 6 5
In [3]:
b = binary_search(l, 13)
print(b)

None

4 6 7 8

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 [4]:
for i in range(-1, 11):
    print(binary_search(list(range(10)), i), end=" ")

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. Kérdés, mit tegyünk, ha egy új elemet akarunk a listába tenni. 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 [5]:
class OrderedList:

    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 [6]:
l = OrderedList([1, -1, 3])
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, 3]
[-1, 1, 3, 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 (egy kitüntetett csúcs, melynek 0 a befoka, a többi csúcsnak 1 a befoka), továbbá minden csúcsnak legfeljebb két „gyereke” van (azaz minden csúcs kifoka legföljebb 2). Az elemek sorrendben tartását egy bináris fával fogjuk megvalósítani elemek hozzáadása és törlése közben is.

In [7]:
class Tree:
    def __init__(self, root):
        self.root = root
        self.left = None
        self.right = None

    def insert(self, data):
        if self.root > data:
            if self.left is None:
                self.left = Tree(data)
            else:
                self.left.insert(data)
        elif self.root < data:
            if self.right is None:
                self.right = Tree(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 Tree 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 [8]:
class Tree:
    def __init__(self, root):
        self.root = root
        self.left = None
        self.right = None

    def insert(self, data):
        if self.root > data:
            if self.left is None:
                self.left = Tree(data)
            else:
                self.left.insert(data)
        elif self.root < data:
            if self.right is None:
                self.right = Tree(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.root)
        if self.right is not None:
            s += self.right.to_list()
        return s
In [9]:
tree = Tree(5)
tree.insert(4)
tree.insert(1)
tree.insert(7)
print(tree.to_list())

[1, 4, 5, 7]

       5
      / \
     4   7
    /
   1

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 a pythontutor-on!

In [10]:
tree = Tree(5)
tree.insert(4)
tree.insert(3)
tree.insert(2)
tree.insert(1)

        5
       /
      4
     /
    3
   /
  2
 /
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 részfát, melynek a data a gyökere.

Python Tutor link

In [11]:
class Tree:
    def __init__(self, root):
        self.root = root
        self.left = None
        self.right = None

    def insert(self, data):
        if self.root > data:
            if self.left is None:
                self.left = Tree(data)
            else:
                self.left.insert(data)
        elif self.root < data:
            if self.right is None:
                self.right = Tree(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.root)
        if self.right is not None:
            s += self.right.to_list()
        return s

    def find(self, data):
        if data == self.root:
            return self
        elif data < self.root and self.left is not None:
            return self.left.find(data)
        elif data > self.root and self.right is not None:
            return self.right.find(data)
        else:
            return None
In [12]:
tree = Tree(5)
tree.insert(3)
tree.insert(6)
tree.insert(4)
tree.insert(1)
tree.insert(2)
print(tree.find(3).root)
print(tree.find(3).to_list())

3
[1, 2, 3, 4]

       5
      / \
     3   6
    / \
   1   4
    \
     2

Hogyan törölhetünk egy csúcsot a fából? Ha a törlendő adat egy levélben van (nincs gyereke, azaz a kifoka 0), 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 végig követni!

In [13]:
class Tree:
    def __init__(self, root):
        self.root = root
        self.left = None
        self.right = None

    def insert(self, data):
        if self.root > data:
            if self.left is None:
                self.left = Tree(data)
            else:
                self.left.insert(data)
        elif self.root < data:
            if self.right is None:
                self.right = Tree(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.root)
        if self.right is not None:
            s += self.right.to_list()
        return s

    def minValue(self):
        current = self
        while(current.left is not None):
            current = current.left
        return current


def deleteNode(tree, node):
    if node < tree.root:
        tree.left = deleteNode(tree.left, node)
    elif node > tree.root:
        tree.right = deleteNode(tree.right, node)
    else:
        if tree.left is None:
            temp = tree.right
            tree = None
            return temp
        elif tree.right is None:
            temp = tree.left
            tree = None
            return temp
        temp = tree.right.minValue()
        tree.root = temp.root
        tree.right = deleteNode(tree.right, temp.root)
    return tree
In [14]:
tree = Tree(5)
tree.insert(3)
tree.insert(1)
tree.insert(4)
tree = deleteNode(tree, 3)
print(tree.to_list())

[1, 4, 5]

       5               5
      /               /
     3        =>     4
    / \             /
   1   4           1
In [15]:
tree = Tree(5)
tree.insert(4); tree.insert(1); tree.insert(8)
tree.insert(6); tree.insert(9)
print(tree.root, tree.to_list())
tree = deleteNode(tree, 5); print(tree.root, tree.to_list())
tree = deleteNode(tree, 6)
tree = deleteNode(tree, 9); print(tree.root, tree.to_list())
tree = deleteNode(tree, 1)
tree = deleteNode(tree, 8); print(tree.root, tree.to_list())

5 [1, 4, 5, 6, 8, 9]
6 [1, 4, 6, 8, 9]
8 [1, 4, 8]
4 [4]

    5            6           8          8       8      4
   / \          / \         / \        /       / 
  4   8   =>   4   8   =>  4   9  =>  4   =>  4   => 
 /   / \      /     \     /          /
1   6   9    1       9   1          1

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

Például formulák elemzésére, 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ámot. Az alábbi kód nagyon le van egyszerűsítve, de talán világos belőle, hogy pl. matematikai formulát hogy lehet feldolgozni.

In [16]:
class Node:
    def __init__(self, data):
        self.data = data

    def calculate(self):
        if self.data == "+":
            return self.left.calculate() + self.right.calculate()
        elif self.data == "*":
            return self.left.calculate() * self.right.calculate()
        else:
            return self.data

    def __str__(self):
        if self.data == "+" or self.data == "*":
            return f"({self.left.__str__()}){self.data}({self.right.__str__()})"
        else:
            return str(self.data)
        
    def __repr__(self):
        return self.__str__()

(7*(2+3))+(-3)

                 +          x0
                / \         / \
               *  -3      x1   x4
              / \         / \
             7   +      x2   x3
                / \          / \
               2   3       x5   x6
In [17]:
x0 = Node("+"); x1 = Node("*"); x3 = Node("+")
x2 = Node(7); x4 = Node(-3); x5 = Node(2); x6 = Node(3)
x0.left = x1; x0.right = x4
x1.left = x2; x1.right = x3
x3.left = x5; x3.right = x6
print(x0.calculate())
x0

32
Out[17]:
((7)*((2)+(3)))+(-3)
In [18]:
x1
Out[18]:
(7)*((2)+(3))
In [19]:
x5
Out[19]:
2
In [ ]: