Tämän viikon aiheena ovat puussa tehtävät kyselyt. Keskeinen kysely on etsiä solmun esivanhempi, mikä onnistuu tehokkaasti hyppytaulukolla.

Hyppytaulukko

Tarkastellaan funktiota $f(x)$, jonka parametrit ja arvot ovat kokonaislukuja välillä $1 \dots n$. Merkitään lisäksi $f(x,k)$ arvoa, joka saadaan soveltamalla funktiota $k$ kertaa.

Esimerkki: $f(1)=2$, $f(2)=3$ ja $f(3)=2$. Nyt $f(1,4)=f(f(f(f(1))))=3$.

Voimme laskea minkä tahansa arvon $f(x,k)$ tehokkaasti luomalla hyppytaulukon, johon on laskettu etukäteen vastaukset tapauksiin, joissa $k$ on $2$:n potenssi. Nämä arvot riittävät, koska pystymme aina esittämään $k$:n $2$:n potenssien summana.

Esimerkki: $f(x,22)=f(f(f(x,16),4),2)$.

Hyppytaulukon luominen vie aikaa $O(n \log m)$, missä $m$ on suurin sallittu $k$:n arvo. Tämän jälkeen jokainen arvon $f(x,k)$ laskeminen vie aikaa $O(\log k)$.

Hyppytaulukon avulla voimme liikkua tehokkaasti eteenpäin verkossa, jonka jokaisesta solmusta lähtee tasan yksi kaari eteenpäin.

Esivanhemman etsiminen

Tavallinen kysely puussa on selvittää solmun esivanhempi, johon pääsee kulkemalla tasoja ylöspäin puussa. Merkitään $f(x,k)$ solmun $x$ esivanhempaa $k$ tasoa ylempänä. Esimerkiksi seuraavassa kuvassa $f(2,1)=1$ ja $f(8,2)=4$.

Voimme vastata tällaisiin kyselyihin tehokkaasti $O(\log n)$-ajassa hyppytaulukon avulla. Esikäsittely vie aikaa $O(n \log n)$.

Alin yhteinen esivanhempi

Solmujen $a$ ja $b$ alin yhteinen esivanhempi on alin puun solmu, joka on kummankin solmun esivanhempi. Esimerkiksi seuraavassa kuvassa solmujen $5$ ja $8$ alin yhteinen esivanhempi on solmu $2$.

Pystymme selvittämään alimman yhteisen esivanhemman tehokkaasti kahdessa vaiheessa. Ensin nostamme alemman tason solmua ylöspäin niin, että molemmat solmut ovat samalla tasolla. Tämän jälkeen nostamme solmuja yhtä aikaa ylöspäin, kunnes ne törmäävät. Molemmat vaiheet onnistuvat ajassa $O(\log n)$ hyppytaulukon avulla.

Etäisyydet puussa

Kun meillä on keino selvittää tehokkaasti kahden solmun alin yhteinen esivanhempi, voimme myös laskea tehokkaasti kahden solmun etäisyyden eli niiden välillä olevan polun pituuden.

Oletetaan, että solmut ovat $a$ ja $b$ ja niiden alin yhteinen esivanhempi on $c$. Merkitään lisäksi $d(x)$ solmun $x$ syvyyttä. Voimme laskea näiden tietojen perusteella solmujen $a$ ja $b$ etäisyyden kaavalla $d(a)+d(b)-2 d(c)$.