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:
