6. Vyhľadávacie stromy

Na minulej prednáške sme sa venovali asociatívnym poliam z pohľadu efektívnosti rôznych implementácií:

Zložitosť operácií
operácie unsorted sorted hash  
valueof() O(n) O(log n) O(1)  
add() O(n) O(n) O(1)  
delete() O(n) O(n) O(1)  

Vidíme, že hašovacie tabuľky sú bezkonkurenčne najefektívnejšou realizáciou asociatívnych polí.

Lenže, čo by sme mali použiť, ak je požiadavkou mať stále k dispozícii aj utriedenú postupnosť kľúčov? Zatiaľ to vyzerá tak, že sa zmierime s realizáciou SortedMap: jedine tu utriedenú postupnosť kľúčov získame so zložitosťou O(n). Pre obe zvyšné realizácie bude utriedená postupnosť kľúčov stáť prinajlepšom O(n log n).

Binárny vyhľadávací strom

V prvom ročníku sme sa zoznámili s binárnymi vyhľadávacími stromami (označujeme BVS), ktorých základné operácie majú zložitosť závislú len od výšky stromu, t.j. O(h). Ak by sme predpokladali, že výška stromu je blízka log n, tak by sme vedeli skonštruovať asociatívne pole s utriedenými kľúčmi operáciami so zložitosťou O(log n).

Skôr ako si pripomenieme vlastnosti BVS, pripravme si základnú triedu BinTree pre binárne stromy. Táto bude vychádzať z definícii triedy v 3. prednáške:

Implementácia BinTree

Súbor bin_tree.py:

import tkinter
import random

class BinTree:
    class _Node:
        def __init__(self, key, value=None, parent=None):
            self._key = key
            self._value = value
            self._parent = parent
            self._left = None
            self._right = None

        def __repr__(self):
            if self._value is not None:
                return '{!r}:{!r}'.format(self._key, self._value)
            else:
                return repr(self._key)

    #------------------------------------------------------------------

    def __init__(self):
        self._root = None
        self._size = 0

    def add_root(self, key, value=None):
        if self._root:
            raise ValueError('koren existuje')
        self._size = 1
        self._root = self._Node(key, value)

    def add_left(self, node, key, value=None):
        if node._left:
            raise ValueError('lavy syn existuje')
        self._size += 1
        node._left = self._Node(key, value, node)

    def add_right(self, node, key, value=None):
        if node._right:
            raise ValueError('pravy syn existuje')
        self._size += 1
        node._right = self._Node(key, value, node)

    def delete(self, node):
        '''vyhodi vrchol node a nahradi ho potomkom (ak ma prave jedneho)

        ValueError ak ma vrchol dvoch potomkov
        '''
        if node._left and node._right:
            raise ValueError('vrchol ma dvoch synov')
        child = node._left if node._left else node._right    # moze byt None
        if child:
            child._parent = node._parent      # prepise sa potomkom
        if node is self._root:
            self._root = child                # moze sa stat rootom
        else:
            parent = node._parent
            if node is parent._left:
                parent._left = child
            else:
                parent._right = child
        self._size -= 1

    #------------------------------------------------------------------

    def __len__(self):
        return self._size

    def is_empty(self):
        return len(self) == 0     # return self._root is None

    def __iter__(self):
        return self.inorder()

    def inorder(self, node=None):
        if node is None:
            if self.is_empty():
                return
            node = self._root
        if node._left:
            yield from self.inorder(node._left)
        yield node
        if node._right:
            yield from self.inorder(node._right)

    def height(self, node=None):
        if node is None:
            node = self._root
        if node is None or node._left is None and node._right is None:
            return 0
        h1 = self.height(node._left) if node._left else 0
        h2 = self.height(node._right) if node._right else 0
        return 1 + max(h1, h2)
    
    #-------------------- testovacie metody ---------------------------

    def add_random(self, key, value=None):
        if self.is_empty():
            self.add_root(key, value)
        else:
            node = self._root
            while True:
                if random.randrange(2):
                    if node._left:
                        node = node._left
                    else:
                        self.add_left(node, key, value)
                        return
                else:
                    if node._right:
                        node = node._right
                    else:
                        self.add_right(node, key, value)
                        return

    canvas_width = 800
    canvas = None

    def draw(self, node=None, width=None, x=None, y=None):
        if self.canvas is None:
            self.canvas = tkinter.Canvas(bg='white', width=self.canvas_width, height=600)
            self.canvas.pack()
        elif node is None:
            self.canvas.delete('all')
        if node is None:
            self.canvas.delete('all')
            if self.is_empty():
                return
            node = self._root
            if width is None: width = int(self.canvas['width'])//2
            if x is None: x = width
            if y is None: y = 30
        if node._left:
            self.canvas.create_line(x, y, x - width//2, y + 50)
            self.draw(node._left, width//2, x - width//2, y + 50)
        if node._right:
            self.canvas.create_line(x, y, x + width//2, y + 50)
            self.draw(node._right, width//2, x + width//2, y + 50)
        self.canvas.create_oval(x-15, y-15, x+15, y+15, fill='white')
        self.canvas.create_text(x, y, text=node)
        if node is self._root:
            self.canvas.update()
            self.canvas.after(300)

Môžeme sem pridať aj otestovanie:

if __name__ == '__main__':
    strom = BinTree()
    for prvok in range(15):
        strom.add_random(prvok)
        strom.draw()

Pomocné metódy

Trieda BinTree obsahuje aj niekoľko pomocných metód, pričom niektoré z nich budú slúžiť len na ladenie:

  • add_root(), add_left(), add_right() - pridajú nový vrchol na konkrétne miesto stromu
  • add_random() - pridá nový vrchol náhodne na niektoré voľné miesto v strome
  • draw() - nakreslí strom, ak sa zavolá znovu, pôvodný obrázok zmaže a nakreslí znovu
  • delete() - vymaže zo stromu konkrétny zadaný vrchol
    • lenže vrchol vyhadzuje len v prípade, že je to list (nemá synov) alebo má iba jedného syna
    • ak je vrchol listom, vyhodenie je jednoduché: jeho otcovi nastavíme namiesto tohto syna None
    • ak má vyhadzovaný vrchol len jedného syna, tak jeho otcovi nastavíme namiesto neho jeho jediného syna (vnuk sa stáva synom)

Po spustení testu, ktorý sme pridali do modulu bin_tree.py, dostaneme napr. takýto strom:

_images/06_01.png

Ešte skontrolujeme metódy height() a inorder():

>>> strom.height()
5
>>> list(strom.inorder())
[7, 5, 9, 6, 14, 0, 12, 10, 4, 1, 11, 3, 13, 8, 2]

Metóda delete() bude v tomto strome fungovať len pre listy alebo vrcholy, ktoré majú iba jedného syna. Napr. môžeme vyhodiť vrchol 4 (strom.delete(strom._root._right._left)): jeho otec 1 dostáva nového ľavého syna a to vrchol 10 (znovu zavoláme strom.draw()):

_images/06_02.png

Podobne môžeme vyhodiť aj vrchol 2 (strom.delete(strom._root._right._right)), jeho otec 1 dostáva nového pravého syna, vrchol 3:

_images/06_03.png

V tomto konkrétnom strome nám metóda delete() nedovolí vyhodiť tieto vrcholy: 0, 5, 6, 1, 3.

Vlastnosti BVS

Pripomeňme si, čo už vieme o binárnych vyhľadávacích stromoch z 1. ročníka:

  • sú to binárne stromy
  • pre koreň platí, že v jeho ľavom podstrome sú iba menšie hodnoty ako v koreni a v pravom iba väčšie
  • táto vlastnosť platí pre všetky vrcholy stromu, t.j. každý má v ľavom podstrome iba menšie hodnoty a v pravom iba väčšie

Z prvého ročníka si pripomeňme hľadanie nejakej hodnoty v strome, resp. vkladanie novej hodnoty do stromu:

class BVS:                                # kopia z 1. rocnika
    class Vrchol:
        def __init__(self, data, left=None, right=None):
            self.data = data
            self.left = left
            self.right = right

    def __init__(self, pole=None):
        self.root = None

    def hladaj(self, hodnota):
        vrch = self.root
        while vrch is not None:
            if vrch.data == hodnota:
                return True
            if vrch.data > hodnota:
                vrch = vrch.left
            else:
                vrch = vrch.right
        return False

    def vloz(self, hodnota):
        if self.root is None:
            self.root = self.Vrchol(hodnota)
        else:
            vrch = self.root
            while vrch.data != hodnota:
                if vrch.data > hodnota:
                    if vrch.left is None:
                        vrch.left = self.Vrchol(hodnota)
                        break
                    vrch = vrch.left
                else:
                    if vrch.right is None:
                        vrch.right = self.Vrchol(hodnota)
                        break
                    vrch = vrch.right

Algoritmus hladaj() (približne zodpovedá metóde valueof()):

  • porovná hľadanú hodnotu s koreňom stromu a ak sa rovná, našli sme hľadaný prvok
  • inak, ak je hodnota v koreni väčšia ako hľadaný prvok, pokračujeme v hľadaní v ľavom podstrome
  • inak, ak je hodnota v koreni menšia ako hľadaný prvok, pokračujeme v hľadaní v pravom podstrome
  • ak je niektorý z podstromov prázdny, hľadanie končí neúspechom (nenašiel)

Keďže sa tento algoritmus stále hlbšie a hlbšie vnára do podstromov celého stromu, ale vždy len jedným smerom, takýchto vnorení nemôže byť viac ako výška stromu (teda O(h)).

Algoritmus vloz() najprv nájde vrchol s danou hodnotou (týmto istým postupom), alebo zistí, že sa v strome nenachádza - na danom mieste sa algoritmus zastavil na prázdnom podstrome. V tomto prípade na toto miesto napojí nový vrchol so zadanou hodnotou.

V prvom ročníku sme neriešili problém vyhadzovania vrcholu z BVS, budeme to robiť teraz.

Vyhodenie vrcholu z BVS

Už vieme, že metóda delete() triedy BinTree dokáže korektne vyhodiť vrchol z ľubovoľného binárneho stromu, pričom, ak bol tento strom BVS, táto vlastnosť sa tým zachová. Potrebujeme doriešiť situáciu, keď vyhadzovaný vrchol má oboch synov. Zišlo by sa nám také riešenie, ktoré nebude mať veľkú zložitosť a podľa možnosti len prehodí v strome zopár referencií. Použijeme takúto ideu algoritmu:

  • vyhadzovaný vrchol (nazveme ho node) naozaj nevyhodíme, ale nahradíme ho iným obsahom tak, aby nepokazil zvyšok stromu

  • z ľavého podstromu tohoto vrcholu (všetky majú hodnotu menšiu ako v node) vyberieme najväčšiu a tá sa stane novým obsahom node - všetky zvyšné vrcholy v ľavom podstrome majú menšiu hodnotu a v pravom podstrome node sú aj tak všetky hodnoty väčšie - preto je táto hodnota dobrým kandidátom, aby nahradila hodnotu v node

  • maximálna hodnota v BVS sa hľadá veľmi jednoducho: stačí prechádzať po pravých synoch a keď narazíme na vrchol, ktorý už pravého syna nemá, toto je maximálny vrchol:

    max = node.left
    while max.right:
        max = max.right
    
  • prekopírujeme obsah tohto vrcholu do node a samotný tento vrchol teraz môžeme jednoducho vyhodiť pomocou delete(), keďže tento určite nemá pravého syna (buď je to list alebo má iba jedného syna)

Teraz prepíšeme metódy tejto verzie BVS tak, aby spolupracovali s triedou BinTree. Pomocná metóda _find() nájde hľadaný vrchol, prípadne nájde vrchol, kam by sa hľadaný vrchol mal pripojiť. Tiež pridáme metódu na vyhadzovanie vrcholu:

Implemetácia BVS - 0. verzia

Táto verzia triedy BVS okrem hladaj() a vloz() realizuje aj vyhadzovanie vrcholu vyhod().

from bin_tree import BinTree

class BVS(BinTree):                                # BVS - 0. verzia

    def _find(self, node, key):
        if key == node._key:
            return node                            # našiel
        elif key < node._key and node._left:
            return self._find(node._left, key)     # vnorenie do ľavého podstromu
        elif key > node._key and node._right:
            return self._find(node._right, key)    # vnorenie do pravého podstromu
        return node

    def hladaj(self, key):
        if self.is_empty():
            return False
        node = self._find(self._root, key)
        return key == node._key

    def vloz(self, key, value=None):
        if self.is_empty():
            self.add_root(key, value)
        else:
            node = self._find(self._root, key)
            if key == node._key:
                node._value = value                # nastav novú asociovanú hodnotu
            elif key < node._key:
                self.add_left(node, key, value)    # zdedené z BinTree
            else:
                self.add_right(node, key, value)   # zdedené z BinTree

    def vyhod(self, key):
        if self.is_empty():
            raise KeyError
        node = self._find(self._root, key)
        if key != node._key:
            raise KeyError
        if node._left and node._right:             # vrchol má oboch synov
            r = node._left                         # hľadá vrchol s maximálnou hodnotou
            while r._right:
                r = r._right
            node._key = r._key
            node._value = r._value
            node = r                               # nastavíme, že vyhadzovať budeme r
        # teraz má vrchol max. 1 syna
        self.delete(node)                          # zdedené z BinTree

Môžeme sem pridať aj otestovanie:

if __name__ == '__main__':
    import random
    strom = BVS()
    pole = [random.randrange(100) for i in range(50)]
    for i in pole:
        strom.vloz(i)
        strom.draw()
    print('pocet =', len(strom), '  vyska =', strom.height())
    for i in range(1, 100, 2):
        if strom.hladaj(i):
            strom.vyhod(i)
        strom.draw()
    print('pocet =', len(strom), '  vyska =', strom.height())
    print('inorder:', *strom.inorder())

Tento test najprv vytvorí BVS z 50 náhodných hodnôt a potom postupne všetky nepárne vyhodí. Napr.

_images/06_04.png

a teraz vyhodenie nepárnych:

_images/06_05.png

Výpis môžeme dostať napr. takýto:

pocet = 41   vyska = 9
pocet = 17   vyska = 5
inorder: 4 8 10 12 16 22 26 42 54 60 68 70 72 78 82 84 88

Zložitosť operácií

Máme teraz tri nové operácie hladaj(), zmen(), vyhod(), z ktorých by sa po malých úpravách dali vyrobiť tri operácie valueof(), add() a delete() (resp. __getitem__(), __setitem__(), __delitem__()). Zložitosť všetkých týchto troch operácií závisí od výšky stromu. Všetky tri totiž obsahujú cyklus, ktorý sa vnára len smerom k listom. Ak by sme predpokladali, že binárny strom má dobrý tvar a jeho výška je približne log n, máme výborné riešenie asociatívneho poľa s utriedenými kľúčmi (niečo ako SortedMap).

Zložitosť operácií
operácie unsorted sorted hash dobré BVS  
valueof() O(n) O(log n) O(1) O(log n)  
add() O(n) O(n) O(1) O(log n)  
delete() O(n) O(n) O(1) O(log n)  

Lenže nás zaujíma nie dobrý prípad, ale najhorší. Najhoršími prípadmi sú napr.

_images/06_06.png _images/06_07.png

Teda sú to také stromy, ktoré majú jediný list. Sú to vlastne obyčajné jednosmerné spájané zoznamy, ktoré bude treba preliezať vždy celé pre hľadanie, nahrádzanie alebo vyhadzovanie ľubovoľnej hodnoty. Zložitosť všetkých troch operácií v takýchto prípadoch je O(n) a nie očakávané O(log n). Výška týchto stromov nie je log n ale n-1

Vyvažovanie vyhľadávacích stromov

Tu by veľmi pomohol mechanizmus, ktorým by sme vedeli zabezpečiť, aby bol tvar stromu pri ľubovoľných operáciách vyvážený, t.j. výška ľavého aj pravého podstromu (pre každý vrchol) by bola približne rovnaká. Takýmto vyhľadávacím stromom budeme hovoriť vyvážené vyhľadávacie stromy, resp. balanced search tree.

Rôznych algoritmov, ktorými sa to dá zabezpečiť je viac, my si ukážeme len jeden z nich (učebnicovo) najbežnejší AVL (pomenovaný podľa mien dvoch ruských informatikov - autorov tejto idey: Adelson-Velsky a Landis, môžete si pozrieť wikipediu). Vyvažovacie techniky vychádzajú z idey rotácie vrcholov, t.j. ak v BVS dva vrcholy a a b majú pod sebou zavesené podstromy (všetko sú to BVS) t0, t1 a t2 každý nejakých výšok, tak tieto dva tvary stromov sú oba BVS s rovnakými hodnotami vrcholov len sú trochu inak poukladané:

    b                  a
   / \                / \
  a   t2             t0  b
 / \                    / \
t0  t1                 t1  t2

Takýmto prerobením stromu z jedného tvaru na druhý niekedy vieme „jemne“ zmeniť výšku stromu, resp. podstromov. Ak by sa napr. ukázalo, že pridaním alebo odobraním nejakého vrcholu sa zmenila vyváženosť stromu (napr. ľavý podstrom má výrazne väčšiu výšku ako pravý), môžeme zarotovať nejaké vrcholy, prípadne zarotovať aj viackrát a tým strom opäť vyvážiť.

Budeme hovoriť, že BVS je vyvážený (spĺňa podmienku AVL) vtedy, keď sa výšky jeho podstromov líšia maximálne o 1. Pre každý vrchol vieme určiť jeho výšku (ako hlboko je v jeho celom podstrome: budeme predpokladať, že listy majú výšku 1, vrchol, z ktorého vychádza iba 1 alebo 2 listy, má výšku 2, …).

Potom rovnováha (balance) pre každý vrchol vypočítame napr. takto balance = výška ľavého podstromu - výška pravého podstromu. V každom vrchole stromu si budeme pamätať jeho výšku (atribút _height), aby sme mohli rýchlo vypočítať jeho rovnováhu. Niektoré iné prístupy si v každom vrchole pamätajú priamo tento balance.

Implemetácia BVS - s prípravou na vyvažovanie

Všimnite si, že do súboru bvs.py:

from bin_tree import BinTree

class BVS(BinTree):                                # BVS - s prípravou na vyvažovanie

    def _find(self, node, key):
        if key == node._key:
            return node                            # našiel
        elif key < node._key and node._left:
            return self._find(node._left, key)     # vnorenie do ľavého podstromu
        elif key > node._key and node._right:
            return self._find(node._right, key)    # vnorenie do pravého podstromu
        return node

    def hladaj(self, key):
        if self.is_empty():
            return False
        node = self._find(self._root, key)
        return key == node._key

    def vloz(self, key, value=None):
        if self.is_empty():
            self.add_root(key, value)
        else:
            node = self._find(self._root, key)
            if key == node._key:
                node._value = value                # nastav novú asociovanú hodnotu
            elif key < node._key:
                self.add_left(node, key, value)    # zdedené z BinTree
                self.rebalance(node)
            else:
                self.add_right(node, key, value)   # zdedené z BinTree
                self.rebalance(node)

    def vyhod(self, key):
        if self.is_empty():
            raise KeyError
        node = self._find(self._root, key)
        if key != node._key:
            raise KeyError
        if node._left and node._right:             # vrchol má oboch synov
            r = node._left                         # hľadá vrchol s maximálnou hodnotou
            while r._right:
                r = r._right
            node._key = r._key
            node._value = r._value
            node = r                               # nastavíme, že vyhadzovať budeme r
        # teraz má vrchol max. 1 syna
        parent = node._parent
        self.delete(node)                          # zdedené z BinTree
        self.rebalance(parent)

    def rebalance(self, node):
        pass

sme na niektoré miesta vložili volanie metódy self.rebalance(...), pričom samotná metóda je zatiaľ prázdna:

class BVS(BinTree):
    ...
    def rebalance(self, node):
        pass

Sú to všetky tie miesta, ktoré môžu ovplybniť tvar stromu a teda tu predpokladáme, že bude treba robiť vyvažovanie.

Implementácia AVL

Zapíšme súbor avl.py:

from bvs import BVS

class AVL(BVS):

    #-------------------------- vnorena trieda Node --------------------------
    class _Node(BVS._Node):

        def __init__(self, key, value=None, parent=None):
            super().__init__(key, value, parent)
            self._height = 1            # este sa to prepocita

        def left_height(self):
            return self._left._height if self._left is not None else 0

        def right_height(self):
            return self._right._height if self._right is not None else 0

    #------------------------- pomocne metody -------------------------------
    def recompute_height(self, node):
        node._height = 1 + max(node.left_height(), node.right_height())

    def isbalanced(self, node):
        return abs(node.left_height() - node.right_height()) <= 1

    def tall_child(self, node, favorleft=False):
        if node.left_height() + (1 if favorleft else 0) > node.right_height():
            return node._left
        else:
            return node._right

    def tall_grandchild(self, node):
        child = self.tall_child(node)
        alignment = (child == node._left)
        return self.tall_child(child, alignment)

    def rebalance(self, node):
        while node is not None:
            old_height = node._height
            if not self.isbalanced(node):
                node = self.restructure(self.tall_grandchild(node))
                self.recompute_height(node._left)
                self.recompute_height(node._right)
            self.recompute_height(node)
            if node._height == old_height:
                node = None
            else:
                node = node._parent

  #--------------------- pomocne metody pre tree balancing ---------------------

    def relink(self, parent, child, make_left_child):
        if make_left_child:
            parent._left = child
        else:
            parent._right = child
        if child is not None:
            child._parent = parent

    def rotate(self, node):
        """Rotate node p above its parent.

        Switches between these configurations, depending on whether p==a or p==b.

              b                  a
             / \                /  \
            a  t2             t0   b
           / \                     / \
          t0  t1                  t1  t2

        Caller should ensure that p is not the root.
        """
        """Rotate Position p above its parent."""
        x = node
        y = x._parent
        z = y._parent
        if z is None:
            self._root = x
            x._parent = None
        else:
            self.relink(z, x, y == z._left)

        if x == y._left:
            self.relink(y, x._right, True)
            self.relink(x, y, False)
        else:
            self.relink(y, x._left, False)
            self.relink(x, y, True)

    def restructure(self, x):
        """Perform a trinode restructure among Position x, its parent, and its grandparent.

        Return the Position that becomes root of the restructured subtree.

        Assumes the nodes are in one of the following configurations:

            z=a                 z=c           z=a               z=c
           /  \                /  \          /  \              /  \
          t0  y=b             y=b  t3       t0   y=c          y=a  t3
             /  \            /  \               /  \         /  \
            t1  x=c         x=a  t2            x=b  t3      t0   x=b
               /  \        /  \               /  \              /  \
              t2  t3      t0  t1             t1  t2            t1  t2

        The subtree will be restructured so that the node with key b becomes its root.

                  b
                /   \
              a       c
             / \     / \
            t0  t1  t2  t3

        Caller should ensure that x has a grandparent.
        """
        """Perform trinode restructure of Position x with parent/grandparent."""
        y = x._parent
        z = y._parent
        if (x == y._right) == (y == z._right):
            self.rotate(y)
            return y
        else:
            self.rotate(x)
            self.rotate(x)
            return x

Táto nová trieda je odvodená od triedy BVS, pričom prekýva definíciu _Node (pridáva sem nový atribút _height) a prekýba aj metódu rebalance(), vďaka čomu vkladanie a vyhadzovanie vrcholov do vyhľadávacieho stromu do bude automaticky vyvažovať.

Odsledujte napr. takéto otestovanie:

if __name__ == '__main__':
    import random
    strom = AVL()
    pole = [random.randrange(100) for i in range(50)]
    for i in pole:
        strom.vloz(i)
        strom.draw()
    print('pocet =', len(strom), '  vyska =', strom.height())
    for i in range(1, 100, 2):
        if strom.hladaj(i):
            strom.vyhod(i)
        strom.draw()
    print('pocet =', len(strom), '  vyska =', strom.height())
_images/06_08.png

a teraz vyhodenie nepárnych:

_images/06_09.png

Mohli ste spozorovať, že v každom okamihu bol vyhľadávací strom pekne vyvážený (rozdiel výšok podstromov pre každý vrchol bol maximálne 1). Tento test vypísal:

pocet = 38   vyska = 5
pocet = 23   vyska = 4

Asociatívne pole

Zatiaľ sme vytvárali dátové štruktúry BVS, resp. AVL, ktoré realizujú príslušné algoritmy, ale zatiaľ to nie je asociatívne pole. Potrebovali by sme premenovať a trochu aj prerobiť niektoré metódy, prípadne dodefinovať všetky abstraktné aj neabstraktné metódy, ktoré potrebujeme, aby to bolo naozaj asociatívne pole (aby sa to podobalo na pythonovský dict).

Teraz využijeme už zadefinovaný abstraktný dátový typ v štandardnom module collections. V tomto module má táto abstraktná trieda meno MutableMapping preto si tento názov pri importe upravíme:

from collections import MutableMapping as MapBase

Namiesto triedy BVS vytvoríme triedu TreeMap, ktorá bude odvodená od MapBase (aby to bolo asociatívne pole). Ale zároveň musí byť odvodená aj od BinTree, keďže tu sa nachádzajú všetky dôležité metódy, ktoré potrebujeme pre fungovanie binárneho stromu. Tomuto hovoríme viacnásobná dedičnosť tried.

Implementácia TreeMap a AVLTreeMap

Asociatívne pole TreeMap pomocou binárneho vyhľadávacieho stromu zapíšeme do súboru tree_map.py:

from bin_tree import BinTree
from collections import MutableMapping as MapBase

class TreeMap(BinTree, MapBase):

    def _find(self, node, key):
        if key == node._key:
            return node                            # našiel
        elif key < node._key and node._left:
            return self._find(node._left, key)     # vnorenie do ľavého podstromu
        elif key > node._key and node._right:
            return self._find(node._right, key)    # vnorenie do pravého podstromu
        return node

    def __getitem__(self, key):
        if self.is_empty():
            raise KeyError
        node = self._find(self._root, key)
        if key == node._key:
            return node._value
        else:
            raise KeyError

    def __setitem__(self, key, value):
        if self.is_empty():
            self.add_root(key, value)
        else:
            node = self._find(self._root, key)
            if key == node._key:
                node._value = value                # nastav novú asociovanú hodnotu
            elif key < node._key:
                self.add_left(node, key, value)    # zdedené z BinTree
                self.rebalance(node)
            else:
                self.add_right(node, key, value)   # zdedené z BinTree
                self.rebalance(node)

    def __iter__(self):
        if not self.is_empty():
            for node in self.inorder():
                yield node._key

    def __delitem__(self, key):
        if self.is_empty():
            raise KeyError
        node = self._find(self._root, key)
        if key != node._key:
            raise KeyError
        if node._left and node._right:             # vrchol má oboch synov
            r = node._left                         # hľadá vrchol s maximálnou hodnotou
            while r._right:
                r = r._right
            node._key = r._key
            node._value = r._value
            node = r                               # nastavíme, že vyhadzovať budeme r
        # teraz má vrchol max. 1 syna
        parent = node._parent
        self.delete(node)                          # zdedené z BinTree
        self.rebalance(parent)

    def rebalance(self, node):
        pass

A trieda, ktorá bude realizovať aj AVL vyvažovanie:

from tree_map import TreeMap

class AVLTreeMap(TreeMap):

    #-------------------------- vnorena trieda Node --------------------------
    class _Node(TreeMap._Node):

        def __init__(self, key, value=None, parent=None):
            super().__init__(key, value, parent)
            self._height = 1            # este sa to prepocita

        def left_height(self):
            return self._left._height if self._left is not None else 0

        def right_height(self):
            return self._right._height if self._right is not None else 0

    #------------------------- pomocne metody -------------------------------
    def recompute_height(self, node):
        node._height = 1 + max(node.left_height(), node.right_height())

    def isbalanced(self, node):
        return abs(node.left_height() - node.right_height()) <= 1

    def tall_child(self, node, favorleft=False):
        if node.left_height() + (1 if favorleft else 0) > node.right_height():
            return node._left
        else:
            return node._right

    def tall_grandchild(self, node):
        child = self.tall_child(node)
        alignment = (child == node._left)
        return self.tall_child(child, alignment)

    def rebalance(self, node):
        while node is not None:
            old_height = node._height
            if not self.isbalanced(node):
                node = self.restructure(self.tall_grandchild(node))
                self.recompute_height(node._left)
                self.recompute_height(node._right)
            self.recompute_height(node)
            if node._height == old_height:
                node = None
            else:
                node = node._parent

  #--------------------- pomocne metody pre tree balancing ---------------------

    def relink(self, parent, child, make_left_child):
        if make_left_child:
            parent._left = child
        else:
            parent._right = child
        if child is not None:
            child._parent = parent

    def rotate(self, node):
        """Rotate node p above its parent.

        Switches between these configurations, depending on whether p==a or p==b.

              b                  a
             / \                /  \
            a  t2             t0   b
           / \                     / \
          t0  t1                  t1  t2

        Caller should ensure that p is not the root.
        """
        """Rotate Position p above its parent."""
        x = node
        y = x._parent
        z = y._parent
        if z is None:
            self._root = x
            x._parent = None
        else:
            self.relink(z, x, y == z._left)

        if x == y._left:
            self.relink(y, x._right, True)
            self.relink(x, y, False)
        else:
            self.relink(y, x._left, False)
            self.relink(x, y, True)

    def restructure(self, x):
        """Perform a trinode restructure among Position x, its parent, and its grandparent.

        Return the Position that becomes root of the restructured subtree.

        Assumes the nodes are in one of the following configurations:

            z=a                 z=c           z=a               z=c
           /  \                /  \          /  \              /  \
          t0  y=b             y=b  t3       t0   y=c          y=a  t3
             /  \            /  \               /  \         /  \
            t1  x=c         x=a  t2            x=b  t3      t0   x=b
               /  \        /  \               /  \              /  \
              t2  t3      t0  t1             t1  t2            t1  t2

        The subtree will be restructured so that the node with key b becomes its root.

                  b
                /   \
              a       c
             / \     / \
            t0  t1  t2  t3

        Caller should ensure that x has a grandparent.
        """
        """Perform trinode restructure of Position x with parent/grandparent."""
        y = x._parent
        z = y._parent
        if (x == y._right) == (y == z._right):
            self.rotate(y)
            return y
        else:
            self.rotate(x)
            self.rotate(x)
            return x

Príslušný test potom môže vyzerať napr. takto:

if __name__ == '__main__':
    import random
    dic1 = AVLTreeMap()
    pole = [random.randrange(10000) for i in range(5000)]
    dic2 = {}
    for i in pole:
        dic1[i] = dic1.get(i, 0) + 1
        dic2[i] = dic2.get(i, 0) + 1
    print(len(dic1), dict(dic1.items())==dic2, list(dic1)==sorted(dic2), dic1.height())
    for i in range(1, 10000, 2):
        try:
            del dic1[i]
        except KeyError:
            pass
        try:
            del dic2[i]
        except KeyError:
            pass
    print(len(dic1), dict(dic1.items())==dic2, list(dic1)==sorted(dic2), dic1.height())

Všimnite si, že teraz pracujeme s binárnym vyhľadávacím stromom ako s asociatívnym poľom.

Zložitosť operácií

Zapíšme zložitosť operácií aj pre dnešné nové dve dátové štruktúry:

Zložitosť operácií
operácie unsorted sorted hash BVS AVL  
valueof() O(n) O(log n) O(1) O(h) O(log n)  
add() O(n) O(n) O(1) O(h) O(log n)  
delete() O(n) O(n) O(1) O(h) O(log n)  
sort() O(n log n) O(n) O(n log n) O(n) O(n)  

Posledný riadok sort označuje zložitosť operácie, ak by sme potrebovali získať utriedenú postupnosť kľúčov (napr. ako iterátor). h pre BVS označuje výšku stromu, čo je často O(log n), ale najhorší prípad je O(n).



Cvičenia

L.I.S.T.

  1. Ručne vyrob BVS (bez vyvažovania) z čísel (kľúčov) v tomto poradí: 30, 40, 24, 58, 48, 26, 11, 13
    • ku každému vrcholu pripíš jeho výšku (self._height) aj balance (výška ľavého podstromu mínus výška pravého podstromu)
    • navrhni, ktoré dva vrcholy v tomto strome by sa mohli „zrotovať“, aby sa strom stal AVL - ručne tento strom prekresli a prepočítaj balance

  1. Úloha zo staršieho testu: Nakresli všetky binárne vyhľadávacie stromy, v ktorých sú uložené kľúče {1,2,3,4} a vyznač tie z nich, ktoré spĺňajú podmienku AVL stromov.
    • upravenú verziu tejto úlohy budeš riešiť ako domáce zadanie

  1. Spojazdni triedu TreeMap z prednášky (asociatívne pole realizované pomocou BVS)

    • otestuj frekvenčnú tabuľku (z prednášky) ale zatiaľ bez AVL

    • otestuj na 30 náhodných údajoch a pritom priebežne vykresľuj celý strom

    • trieda TreeMap je odvodená z dvoch tried: BinTree a MapBase; mal by si rozumieť, na čo tu slúžia obe tieto základné triedy a čo by sa napr. stalo, keby sme TreeMap odvodili len z BinTree, teda by sme zapísali:

      class TreeMap(BinTree):
          ...
      
    • prestane teraz niečo fungovať?


  1. Pomocná metóda _find() v triede TreeMap je rekurzívna:
    • v niektorých situáciách to spadne na preplnení rekurzie - vygeneruj také testovacie dáta, aby táto funkcia naozaj spadla na rekurzii
    • prepíš túto metódu bez rekurzie a otestuj jej funkčnosť na dátach, na ktorých to v predchádzajúcom teste spadlo

  1. Do triedy TreeMap dopíš pomocné metódy:
    • balance(node) - pre daný vrchol vráti jeho rovnováhu, teda rozdiel výšok ľavého a pravého podstromu metód
    • is_bvs() - zistí, či daný strom spĺňa podmienky pre binárny vyhľadávací strom (či je korektný)
    • is_avl() - zistí, či daný strom spĺňa AVL podmienky
    • upravte metódu draw() tak, aby namiesto hodnoty vo vrchole vypisovala jeho balance

  1. Spojazdni AVLTreeMap z prednášky:
    • sleduj (vykresľuj), ako sa priebežne vyvažuje celý strom, keď sa do neho pridávajú, resp. vyhadzujú vrcholy
    • otestuj na veľkých údajoch (napr. frekvenčná tabuľka z prednášky)
    • skontroluj, či je AVL-strom skonštruovaný korektne - využi metódu is_avl()

  1. Do BinTree dopíš dve metódy next(p) a prev(p), pre ktoré je parametrom referencia na niektorý vrchol (typu _Node):

    • metóda next(None) vráti najľavejší vrchol stromu (bol by prvý pri výpise inorder)

    • metóda next(p) pre p rôzne od None vráti nasledovný vrchol, ktorý by nasledoval vo výpise inorder za daným p

    • za posledným vrcholom (najpravejším v strome, t.j. posledným v inorder) metóda vráti None

      p = strom.next(None)
      while p is not None:
          print(p._key, end=' ')
          p = strom.next(p)
      print()
      

      takto by sa vypísala kompletná postupnosť inorder

    • metóda prev() funguje opačne k next(), t.j. pre None vráti posledný vrchol v inorder, inak vráti predchádzajúci vrchol, resp. None pre prvý

    • obe metódy otestuj na TreeMap - mali by vygenerovať usporiadané postupnosti hodnôt (kľúčov)



4. Domáce zadanie

L.I.S.T.

Množina AVL stromov

Definujte všetky metódy tried BST a AVLSet, pomocou ktorých sa bude dať vyriešiť takáto úloha:

  • Zistite všetky binárne vyhľadávacie stromy, v ktorých sú uložené kľúče {1,2,3,4} a spĺňajú podmienku AVL stromov.

Trieda BST (binary search tree) okrem základnej metódy insert (vloží do stromu novú hodnotu na správne miesto) má aj ďalšie pomocné metódy:

  • preorder() vráti n-ticu (tuple) všetkých kľúčov v strome v poradí preorder
    • uvedomte si, že toto poradie jednoznačne určuje tvar stromu
  • avl() zistí, či daný binárny vyhľadávací strom spĺňa podmienku AVL stromov: t.j. pre každý vrchol platí, že výšky ľavého a pravého podstromu sa líšia maximálne o 1; vráti True alebo False
  • __eq__(other) zistí, či daný binárny vyhľadávací strom je presne rovnaký ako nejaký iný (má rovnaký tvar aj hodnoty vo vrcholoch); vráti True alebo False
  • __repr__() vráti znakový reťazec reprezentácie stromu, ktorý bude reťazcovou reprezentáciou preorderu
  • __hash__() vráti celé číslo, ktoré reprezentuje celý strom: pre rôzne stromy vráti rôzne čísla, pre rovnaké vráti rovnaké číslo (využite preorder)

Vďaka dvom magickým metódam (__eq__ a __hash__) Python dovolí z objektov BST vytvárať normálnu pythonovskú množinu.

Trieda AVLSet slúži na vytváranie množiny rôznych binárnych vyhľadávacích stromov, ktoré spĺňajú podmienku AVL. Naprogramujte tieto metódy:

  • add(seq) - zo zadanej postupnosti seq vytvorí binárny vyhľadávací strom (objekt BST) a ak to spĺňa podmienku avl(), zaradí ho do množiny (atribút self.set); metóda testuje, či je to AVL po každom pridaní ďalšej hodnoty z postupnosti seq do stromu (hoci výsledný strom by mohol byť AVL, ale už pri jeho vytváraní môže vzniknúť strom, ktorý by nebol AVL, preto sa takýto strom do množiny zaraďovať nebude)
  • all(seq) - z danej postupnosti hodnôt vygeneruje všetky permutácie prvkov (zrejme ich bude faktoriál počtu prvkov) a z každej takejto permutácie sa bude snažiť vytvoriť AVL strom - použije metódu self.add()

Ak by sme triedy otestovali týmito volaniami metód:

if __name__ == '__main__':
    t1 = BST()
    for i in (1, 2, 3, 4):
        t1.insert(i)
    print(t1)
    print('avl =', t1.avl())
    t2 = BST()
    for i in (2, 4, 3, 1):
        t2.insert(i)
    print(t2)
    print('avl =', t2.avl())
    t3 = BST()
    for i in (2, 1, 4, 3):
        t3.insert(i)
    print('eq =', t2 == t3)
    mn = AVLSet()
    mn.add((1, 2, 3, 4))
    mn.add((2, 4, 3, 1))
    mn.add((2, 1, 4, 3))
    mn.add((2, 4, 1, 3))
    print('set:')
    for t in mn:
        print(t)
    print('all:')
    mn = AVLSet()
    mn.all((1, 2, 3, 4))
    print(*mn, sep='\n')
    mn = AVLSet()
    mn.all(range(5))
    print('all range(5) =', len(mn))

dostaneme tento výstup:

(1, 2, 3, 4)
avl = False
(2, 1, 4, 3)
avl = True
eq = True
set:
(2, 1, 4, 3)
all:
(3, 2, 1, 4)
(2, 1, 3, 4)
(3, 1, 2, 4)
(2, 1, 4, 3)
all range(5) = 6

Z úlohového servera L.I.S.T. si stiahnite kostru programu riesenie4.py. Mali by ste dodržať tieto vlastnosti programu:

  • Nemeňte me ná už zadaných atribútov (metód a premenných).

  • Do existujúcich tried môžete pridávať vlastné atribúty a metódy.

  • Pri testovaní vášho riešenia sa budú kontrolovať aj vami vytvorené binárne vyhľadávacie stromy (s koreňom v atribúte BST.root).

  • Na začiatok pridajte tieto tri komentárové riadky (s vašim menom a dátumom):

    # 4. zadanie: mnozina AVL stromov
    # autor: Alan Turing
    # datum: 9.11.2018
    

Aby ste mohli spúšťať skúškové testy, riešenie (bez ďalších súborov) odovzdajte na úlohový server L.I.S.T.. Testy postupne preverujú vlastnosti vašich algoritmov, pri prvej chybe sa testovanie preruší a ďalšie časti sa netestujú:

  • 20% bodov za vytvorenie BST stromu a metódu repr()
  • 20% bodov za testovanie, či má BST strom AVL vlastnosť
  • 20% bodov za funkčnosť metód __eq__() a __hash__()
  • 20% bodov za metódu add() v triede AVLSet
  • 20% bodov za metódu all() v triede AVLSet

Súbor riesenie4.py odovzdávajte najneskôr do 23:00 25. novembra. Môžete zaň získať 10 bodov.



© Copyright 2018-2019, Andrej Blaho.
Naposledy aktualizované 14. feb. 2019.
Vytvorené pomocou Sphinx 1.8.4.

Creative Commons License This work is licensed under a Creative Commons Attribution 4.0 International License.