Laborations- och programmeringsuppgift 2: binära sökträd.

1. Kopiera paketet till din egen katalog. När detta är gjort måste -classpath användas för att java ska hitta paketet. Läs mer om classpath här.
2. Skriv en metod treeHeight som returnerar höjden på ett träd. Metoden skall räkna ut höjden med hjälp av rekursivitet. (Höjden av ett löv är 1 (eller 0, vilket man tycker), höjden av en intern nod är 1 plus den största av de två barnerns höjder. Trödets höjd är detsamma som rotens höjd.)
3. Modifiera metoden printTree så att man får en strukturerad utskrift av trädet, där man kan se nodernas höjd och på så sätt få en uppfattning av trädets form. Den strukturerade utskriften görs så att noden skrivs längre åt höger ju högre upp i trädet den befinner sig. Man får alltså hålla reda på höjden i printTree. OBS: du skall inte använda treeHeight för varje nod; det blir ju väldigt långsamt. I stället tar du först reda på hela trädets höjd genom att använda treeHeight på roten, sedan räknar du ner höjden alteftersom du traverserar nedåt i trädet under printTree.
   Exempel: Det här trädet kan se ut så här:

                  D
            H
         j
               K
                     M
               P
                  Q
         R
            S
               T
      U
         V
            X
         Z
   

   I ditt fall skall du dock visa mer information i den strukturerade utskriften. Förutom nodens nyckel, som i utskriften ovan, skall du skriva ut balanseringsinformationen. För det randomiserade sökträdet innebär detta att exempelvis en nod med nyckeln algoritm och prioritet 4352, skriver du ut algoritm:4352. För ett AA-träd innebär det att en nod med nyckeln algoritm och level 2, skrivs som algoritm:2.
4. Modifiera definitionen av en binär nod så att den också innehåller nodens vikt, definierad som antalet element som finns under noden, inklusive noden själv. I bilden ovan har noden X vikten 4, medan noden M har vikten 14. Vikterna skall updateras vid insättning och uttag, framförallt gäller det att få det hela rätt vid rotationerna. ( OBS: Uppdatering av vikterna måste givetvis göras på ett effektivt sätt, så att de tinte försämrar tidskomplexiteten hos implementationen.) Skriv en metod findOrder som tar som parameter ett tal index och som returnerar en referens till den nod som innehåller element nr index, räknat i alfabetisk ordning. Metoden skall på ett bra sättt använda sig av viktinformationen.
5. Skriv ett litet interaktivt program som låter användaren sätta in och ta ut strängar i ett sökträd. programmet börjar med att ge instruktioner till användaren, i stil med:
   

   Välkommen till mitt trädvisningsprogram för randomiserade träd. 
   Du använder det så här:
   
        + str     sätter in strängen str i trädet
        - str     tar bort strängen str, om den finns i trädet
        f str     svarar om strängen str finns med eller ej.
        o x       anger sträng nr x i bokstavsordning.
        v         visar hur trädet ser ut 
        c         tömmer trädet
        q         avslutar programmet
        ?         skriver ut den här hjälptexten