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 ja Javalla.

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

class Node {
    Node left, right;
    int value;

    public Node(int value) {
        this.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:

Tietorakenteet ja algoritmit syksy 2021

Binäärihakupuu

Viikko 6