Viikon 6 aiheena on luentomateriaalin sivut 198–251.
AVL-puu on binäärihakupuu, joka pitää automaattisesti huolen siitä, että alkiot jakautuvat tasaisesti eri puolille puuta. Tämän ansiosta lisäämisen, hakemisen ja poistamisen aikavaativuus on varmasti O(log n).
AVL-puu on monimutkaisempi kuin kaikki aiemmat tietorakenteet kurssilla. AVL-puuta ei tarvitse osata koodata, eikä sen yksityiskohtia tarvitse muistaa kurssin jälkeen. On kuitenkin tärkeää ymmärtää, mihin ideoihin puun toiminta perustuu.
AVL-puun lisäksi on monia muitakin tasapainoisia binääripuita, jotka takaavat aikavaativuuden O(log n).
Javan luokat TreeSet ja TreeMap
perustuvat tasapainoiseen binääripuuhun
(ei kuitenkaan AVL-puuhun, lisätietoa laskareissa).
Luokka TreeSet toteuttaa joukon,
jossa lisäämisen, hakemisen ja poistamisen
aikavaativuus on O(log n). Joukosta
voi hakea myös pienimmän, suurimman ja
haluttua arvoa lähimmän arvon.
Luokka TreeMap on kuin taulukko,
mutta indekseinä voi käyttää minkä tahansa tyyppisiä arvoja.
Tätä voi ajatella myös luokan TreeSet
laajennuksena, jossa joukkoon lisätään avaimia,
joihin taas liittyy arvoja.
Näiden luokkien käyttäminen vaatii,
että binääripuuhun laitettavat arvot ovat vertailtavissa
eli toteuttavat rajapinnan Comparable.
Javan luvuissa ja merkkijonoissa vertailu toimii automaattisesti,
mutta omiin luokkiin se täytyy lisätä tekemällä
metodi compareTo.