Solmujärjestys

Tehtäväsi on selvittää, missä järjestyksessä luvut $1 \dots n$ tulee lisätä tyhjään binäärihakupuuhun, jotta puun korkeudesta tulee mahdollisimman pieni. Voit antaa minkä tahansa kelvollisen ratkaisun. Voit olettaa, että puussa on enintään 100 solmua.

Toteuta tiedostoon fillorder.py funktio create, joka palauttaa jonkin lukujen $1 \dots n$ permutaation, joka minimoi hakupuun korkeuden.

def create(n):
    # TODO

if __name__ == "__main__":
    print(create(1)) # [1]
    print(create(3)) # [2, 3, 1]
    print(create(4)) # [2, 1, 4, 3]
    print(create(7)) # [4, 6, 5, 2, 3, 7, 1]

Selitys: Jos $n = 3$, yksi kelvollinen ratkaisu on laittaa luvut hakupuuhun järjestyksessä $[2, 3, 1]$. Tällöin luku $2$ asetetaan puun juureksi, luku $3$ tämän oikeaksi lapseksi ja luku $1$ juuren vasemmaksi lapseksi. Luvut $1$ ja $3$ päätyvät siis syvyydelle 1. Kuitenkin esimerkiksi järjestys $[1,2,3]$ ei olisi kelvollinen. Nyt luku $1$ päätyy puun juureksi, $2$ tämän oikeaksi lapseksi ja $3$ luvun $2$ oikeaksi lapseksi. Luku $3$ päätyy siis syvyydelle 2, mikä on suurempi kuin minkään solmun syvyys optimaalisessa järjestyksessä.