Tietorakenteet ja algoritmit

syksy 2023

12. Binäärihakupuu

Binäärihakupuu (binary search tree) on tietorakenne, joka pitää yllä joukkoa alkioista. Sen perustoiminnot ovat samat kuin hajautuksessa: alkioita pystyy lisäämään, etsimään ja poistamaan tehokkaasti.

Binäärihakupuun keskeinen ero hajautukseen verrattuna on, että se säilyttää alkioita suuruusjärjestyksessä. Tämän ansiosta voidaan etsiä esimerkiksi tehokkaasti joukon pienin tai suurin alkio, mikä ei olisi mahdollista hajautuksen avulla.

Pythonin standardikirjastossa ei ole binäärihakupuun toteutusta, minkä vuoksi sen käyttäminen Pythonissa on hankalampaa kuin hajautuksen käyttäminen. Tässä luvussa toteutamme itse binäärihakupuun Pythonilla.

Joukko binääripuuna

Binäärihakupuu on binääripuu, jonka jokaisessa solmussa on yksi joukon alkioista. Esimerkiksi seuraava binäärihakupuu vastaa joukkoa \(\{2,3,5,7,8,9\}\):

Binäärihakupuun alkiot on järjestetty niin, että jokaisessa solmussa kaikki vasemman alipuun alkiot ovat pienempiä kuin solmun alkio ja vastaavasti kaikki oikean alipuun alkiot ovat suurempia kuin alkio. Esimerkiksi yllä olevassa kuvassa juuren vasemman alipuun alkiot \(2\) ja \(3\) ovat pienempiä kuin juuren alkio \(5\). Vastaavasti juuren oikean alipuun alkiot \(7\), \(8\) ja \(9\) ovat suurempia kuin juuren alkio \(5\).

Huomaa, että solmujen sijoittuminen binäärihakupuuhun voidaan valita muuten vapaasti, kunhan äsken mainittu järjestykseen liittyvä ehto pätee. Niinpä on erilaisia tapoja esittää tietty joukko binäärihakupuuna. Esimerkiksi seuraavat kaksi binäärihakupuuta vastaavat molemmat joukkoa \(\{1,2,3,4,5\}\):

Katsotaan seuraavaksi, miten binäärihakupuun avulla voidaan toteuttaa joukkoon liittyviä operaatioita.

Alkion etsiminen

Kun halutaan etsiä joukosta alkiota, lähdetään liikkeelle puun juuresta. Jos solmussa oleva alkio on pienempi kuin etsittävä alkio, siirrytään oikeaan lapseen. Jos solmussa oleva alkio on suurempi kuin etsittävä alkio, siirrytään vasempaan lapseen. Näin jatketaan, kunnes haluttu alkio on löytynyt tai solmulla ei ole lasta, johon tulisi siirtyä. Jälkimmäinen tapaus tarkoittaa, ettei etsittävää alkiota ole joukossa.

Esimerkiksi alkio \(7\) voidaan löytää puusta kulkemalla seuraavaa reittiä:

Alkion etsiminen alkaa juuresta, jossa on alkio \(5\). Koska tämä on pienempi kuin etsittävä alkio \(7\), siirrytään oikeaan lapseen. Tässä solmussa on alkio \(8\), joka on suurempi kuin etsittävä alkio \(7\). Niinpä haku jatkuu vasempaan lapseen, josta löytyy etsittävä alkio \(7\).

Alkion lisääminen

Joukkoon voidaan lisätä alkio etsimällä ensin alkiota joukosta. Jos alkio löytyy, sitä ei lisätä, koska sama alkio voi esiintyä joukossa vain kerran. Jos alkiota ei löydy, puuhun lisätään uusi solmu siihen kohtaan, johon haku olisi edennyt seuraavaksi, ja uusi alkio sijoitetaan siihen.

Esimerkiksi alkio \(4\) voidaan lisätä joukkoon seuraavasti:

Alkion \(4\) etsiminen alkaa juuresta, jossa on alkio \(5\). Tästä siirrytään vasempaan lapseen, jossa on alkio \(3\). Tästä tulisi siirtyä oikeaan lapseen, mutta solmulla ei ole oikeaa lasta. Tämä tarkoittaa, ettei alkiota \(4\) ole vielä puussa ja se tulee lisätä solmun oikeaksi lapseksi. Tämän ansiosta alkio löytyy, kun sitä etsitään myöhemmin.

Pienin alkio

Joukon pienin alkio löytyy lähtemällä liikkeelle juuresta ja etenemällä solmun vasempaan lapseen niin kauan, kuin tämä on mahdollista. Kun tämä ei ole enää mahdollista, pienin alkio on löytynyt.

Suurin alkio

Tässä voidaan menetellä vastaavasti kuin pienimmän alkion etsimisessä, mutta joka vaiheessa siirrytään solmun oikeaan lapseen.

Pienin suurempi alkio

Tavoitteena on löytää pienin alkio, joka on suurempi kuin \(x\). Lähdetään liikkeelle juuresta ja siirrytään vasempaan lapseen aina, kun solmun alkio on suurempi kuin \(x\), ja muuten oikeaan lapseen. Haku päättyy, kun siirtyminen ei ole mahdollista. Haluttu alkio on pienin alkiota \(x\) suurempi alkio kaikista alkioista, joiden kautta reitti kulki.

Suurin pienempi alkio

Tavoitteena on löytää suurin alkio, joka on pienempi kuin \(x\). Tässä voidaan toimia käänteisesti edelliseen kohtaan verrattuna: siirrytään oikeaan lapseen aina, kun solmun alkio on pienempi kuin \(x\). Haluttu alkio on suurin alkiota \(x\) pienempi alkio reitillä olleista alkioista.

Alkion poistaminen

Kun joukosta halutaan poistaa alkio, etsitään ensin alkiota vastaava solmu puusta. Tässä on kolme mahdollista tapausta:

Seuraava kuva näyttää esimerkin, jossa halutaan poistaa alkio \(5\). Koska alkion \(5\) solmulla on kaksi lasta, vaihdetaan ensin keskenään alkiot \(5\) ja \(7\). Tämän jälkeen alkio \(5\) on helppoa poistaa, koska sillä ei ole lasta.

Huomaa, että kahden lapsen tapauksessa pienimmän alkiota suuremman alkion etsiminen takaa, että uudella solmulla ei voi olla kahta lasta. Niinpä uuden solmun pystyy aina poistamaan helposti.

Toteutus Pythonilla

Aletaan seuraavaksi toteuttaa binäärihakupuuta Pythonilla. Tavoitteena on saada aikaan luokka TreeSet, jota voidaan käyttää seuraavasti:

s = TreeSet()

s.add(1)
s.add(2)
s.add(3)

print(2 in s) # True
print(4 in s) # False

print(s) # [1, 2, 3]

Tässä metodi add lisää alkion joukkoon, operaattori in ilmoittaa, onko alkio joukossa, ja joukon merkkijonoesityksenä on lista sen alkioista.

Seuraava luokka Node sisältää tiedon puussa olevasta solmusta:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

Jokaiseen solmuun liittyy kolme tietoa: solmussa olevan alkion arvo (value) sekä viittaus solmun vasempaan ja oikeaan lapseen (left ja right).

Luokka TreeSet sisältää varsinaisen binäärihakupuun toteutuksen. Tässä on pohja luokalle:

class TreeSet:
    def __init__(self):
        self.root = None

Metodi __init__ luo muuttujan root, jossa on viittaus puun juureen. Alussa puussa ei ole yhtään solmua, minkä vuoksi root on None.

Alkion lisääminen

Seuraava metodi add lisää alkion joukkoon:

    def add(self, value):
        if not self.root:
            self.root = Node(value)
            return

        node = self.root
        while True:
            if node.value == value:
                return
            if node.value > value:
                if not node.left:
                    node.left = Node(value)
                    return
                node = node.left
            else:
                if not node.right:
                    node.right = Node(value)
                    return
                node = node.right

Jos puu on tyhjä, alkio lisätään sen juureksi uuteen solmuun ja metodi päättyy. Muuten metodi etsii paikan alkiolle juuresta alkaen.

Jos solmun alkio on sama kuin lisättävä alkio, metodi päättyy, koska alkio on jo lisätty. Jos solmun alkio on suurempi kuin lisättävä alkio, haku jatkuu vasemmalle, ja jos solmun alkio on pienempi kuin lisättävä alkio, haku jatkuu oikealle. Jos solmulla ei ole lasta, johon haun tulisi jatkua, uusi alkio lisätään kyseiseksi lapseksi ja metodi päättyy.

Alkion etsiminen

Seuraava metodi __contains__ tarkastaa, onko joukossa tiettyä alkiota. Metodia __contains__ kutsutaan, kun koodissa on operaattori in.

    def __contains__(self, value):
        if not self.root:
            return False

        node = self.root
        while node:
            if node.value == value:
                return True
            if node.value > value:
                node = node.left
            else:
                node = node.right

        return False

Jos puu on tyhjä, alkiota ei ole varmasti puussa, ja metodi palauttaa heti False. Muuten metodi etsii alkiota juuresta alkaen samaan tapaan kuin lisäämisessä. Jos alkio löytyy jossain vaiheessa, metodi palauttaa True. Jos haku etenee puun ulkopuolelle, metodi palauttaa lopuksi False.

Merkkijonoesitys

Seuraava metodi __repr__ muodostaa joukon merkkijonoesityksen, joka sisältää joukon alkiot listana.

    def __repr__(self):
        items = []
        self.traverse(self.root, items)
        return str(items)

    def traverse(self, node, items):
        if not node:
            return
        self.traverse(node.left, items)
        items.append(node.value)
        self.traverse(node.right, items)

Metodi __repr__ hyödyntää metodia traverse, joka käy läpi puun alkiot ja lisää ne listalle. Metodi käy ensin läpi vasemman alipuun, lisää sitten solmun alkion listalle ja käy sen jälkeen vielä läpi oikean alipuun. Tämän ansiosta lista sisältää lopuksi joukon alkiot suuruusjärjestyksessä.

Muut operaatiot

Tässä toteutuksessa ei ole vielä metodeja pienimpien ja suurimpien alkioiden etsimiseen eikä alkion poistamiseen. Näiden metodien toteuttaminen kuuluu tämän viikon tehtäviin.

Tasapainoisuus

Binäärihakupuun operaatiot käyvät läpi reittejä puun juuresta puun lehtiin. Tämän vuoksi puun tehokkuus riippuu siitä, miten pitkiä nämä reitit voivat olla. Pisimmän reitin pituus on yhtä suuri kuin puun korkeus \(h\), joten binäärihakupuun operaatioiden tehokkuus voidaan ilmoittaa muodossa \(O(h)\).

Binäärihakupuu ei sellaisenaan ole vielä tehokas tietorakenne, koska puun korkeus saattaa olla suuri. Esimerkiksi jos puuhun lisätään \(n\) alkiota järjestyksessä \(1,2,\dots,n\), kaikki alkiot menevät samaan ketjuun ja puun korkeus on \(n-1\). Tällöin puun operaatiot vievät aikaa \(O(n)\).

Kuitenkin binäärihakupuu voidaan toteuttaa niin, että alkiot jakautuvat tasaisesti puun eri puolille ja puun korkeus on aina luokkaa \(\log n\). Tällöin puun operaatiot toimivat tehokkaasti ja vievät aikaa vain \(O(\log n)\). Tällaista binäärihakupuuta kutsutaan tasapainoiseksi (balanced).

Tasapainoinen binäärihakupuu on toteutettu niin, ettei puun korkeus kasva liian suureksi. Esimerkiksi AVL-puu on tasapainoinen binäärihakupuu, jossa jokaisen solmun vasemman ja oikean alipuun korkeuksien ero saa olla enintään \(1\). Tämän ehdon ansiosta puun korkeus on aina luokkaa \(\log n\). Jotta ehto säilyisi voimassa, puun rakennetta muutetaan tarvittaessa alipuiden kiertojen avulla.

Esimerkki: Hotelli

Seuraavassa on esimerkki tehtävästä, joka voidaan ratkaista tehokkaasti binäärihakupuun avulla:

Tehtävä

Hotellissa on \(n\) huonetta, joihin jokaiseen mahtuu tietty määrä ihmisiä. Hotelliin saapuu \(m\) ryhmää asiakkaita. Sinun tulee käsitellä ryhmät järjestyksessä vasemmalta oikealle ja antaa jokaiselle ryhmälle pienin huone, johon he kaikki mahtuvat, tai ilmoittaa, ettei sopivaa huonetta ole saatavilla.

Esimerkiksi oletetaan että huoneiden koot ovat \([2,4,4,8]\) ja ryhmien koot ovat \([4,6,2,5,2]\). Tässä tapauksessa haluttu tulos on \([4,8,2,0,4]\) seuraavan mukaisesti (\(0\) tarkoittaa, ettei ryhmä saanut huonetta):

  • Ensimmäinen ryhmä saa huoneen, jonka koko on \(4\).
  • Toinen ryhmä saa huoneen, jonka koko on \(8\).
  • Kolmas ryhmä saa huoneen, jonka koko on \(2\).
  • Neljäs ryhmä ei saa huonetta.
  • Viides ryhmä saa huoneen, jonka koko on \(4\).

Oletetaan, että käytössä on luokka TreeSet, jossa on seuraavat metodit:

Näiden metodien avulla tehtävä voidaan ratkaista seuraavasti:

def find_rooms(sizes, requests):
    rooms = TreeSet()
    counter = 0
    for size in sizes:
        counter += 1
        rooms.add((size, counter))
        
    result = []
    for request in requests:
        room = rooms.next((request, 0))
        if room == None:
            result.append(0)
        else:
            rooms.remove(room)
            result.append(room[0])
            
    return result

Funktio luo joukon rooms ja lisää sinne kaikki saatavilla olevat huoneet. Koska usealla huoneella voi olla sama koko mutta joukossa voi esiintyä vain kerran sama alkio, jokainen huone lisätään parina, jossa ensimmäinen alkio on huoneen koko ja toinen alkio on laskurin antama huoneen numero. Esimerkin tapauksessa joukkoon lisätään parit (2, 1), (4, 2), (4, 3) ja (8, 4).

Tämän jälkeen funktio käy läpi ryhmien koot ja lisää listalle result tiedot kunkin ryhmän saaman huoneen koosta. Metodilla next etsitään pienin alkio, joka on suurempi kuin (request, 0). Koska minkään huoneen numero ei ole 0, metodi löytää pienimmän huoneen, jonka koko on ainakin request.

Funktio vie aikaa \(O(n \log n + m \log n)\) olettaen, että binäärihakupuu on tasapainoinen ja sen operaatiot vievät aikaa \(O(\log n)\).

Miksi ei Pythonissa?

Binäärihakupuu on saatavilla valmiina monissa ohjelmointikielissä, mutta se puuttuu Pythonin standardikirjastosta. Miksi näin on?

Syy lienee siinä, että Pythonin kehittäjien näkemyksen mukaan binäärihakupuu ei ole niin usein tarvittava tietorakenne, että sen tulisi olla kielen standardikirjastossa. Pythonissa keskeisessä asemassa ovat hajautukseen perustuvat tietorakenteet (set ja dict), jotka riittävät monissa tapauksissa.

Usein binäärihakupuun sijasta voidaan käyttää juuri hajautusta ja mahdollisesti lisäksi järjestämistä tai kekoa. Monissa tehtävissä yksi mahdollinen tehokas ratkaisu on käyttää binäärihakupuuta, mutta tehtävän voi ratkaista myös jotenkin muulla tavalla tehokkaasti ilman binäärihakupuuta.

Jos kuitenkin Pythonissa tarvitsee binäärihakupuuta, saatavilla on monia valmiita standardikirjaston ulkopuolisia toteutuksia. Näiden käyttäminen voi olla järkevämpää kuin itse toteutetun binäärihakupuun käyttäminen.

Muiden kielten toteutukset

C++:ssa tietorakenteet std::set ja std::map toteuttavat binäärihakupuuhun perustuvan joukon ja hakemiston. Esimerkiksi seuraava koodi luo joukon, lisää sinne funktiolla insert sekä etsii funktiolla upper_bound pienimmän annettua alkiota suuremman alkion.

std::set<int> items;

items.insert(1);
items.insert(3);
items.insert(6);
items.insert(8);

auto it = items.upper_bound(4);
std::cout << *it << "\n"; // 6

Javassa vastaavat tietorakenteet ovat TreeSet ja TreeMap. Esimerkiksi seuraava koodi vastaa äskeistä C++-koodia:

TreeSet<Integer> items = new TreeSet<>();

items.add(1);
items.add(3);
items.add(6);
items.add(8);

int item = items.higher(4);
System.out.println(item); // 6

JavaScript noudattaa Pythonin linjaa siinä, että kielen standardikirjastossa ei ole binäärihakupuun toteutusta.