Login using mooc.fi
—
Dark mode
Tietorakenteet ja algoritmit kevät 2023
Binäärihakupuu
Task
CSES - Binäärihakupuu
Toteuta kurssikirjan luvun 6.2 mukainen binäärihakupuu, jossa pystyy lisäämään alkion puuhun sekä laskemaan puun korkeuden.
Jos puuhun lisättäisiin alkiot $1,2,\dots,n$ pienimmästä suurimpaan, puun korkeudeksi tulisi $n-1$. Entä jos alkiot lisätäänkin satunnaisessa järjestyksessä?
Toteuta testi, jossa $n=10^5$ ja alkiot $1,2,\dots,n$ lisätään satunnaisessa järjestyksessä. Mikä on puun korkeus kaikkien lisäysten jälkeen?
Voit tallentaa jokaisen solmun
Node
-luokan oliona, jossa on viittaus vasempaan ja oikeaan lapseen sekä solmussa oleva arvo. Seuraavassa on esimerkki, miten luokan voi tehdä Pythonilla.
class Node: def __init__(self, value): self.left = None self.right = None self.value = value
Tässä tehtävässä saat pisteen automaattisesti, kun ilmoitat tulokset ja käyttämäsi koodin ja painat lähetysnappia.
Puun korkeus:
Testissä käyttämäsi koodi:
Viikko 6
Puun läpikäynti
Binäärihakupuu
Lehdet
Sama taso
Alipuut
Solmujärjestys
Puun polut
Lisäystavat