17. AVL Tree Challenges

Written by Kelvin Lau

Here are three challenges that revolve around AVL trees. Solve these to make sure you have the concepts down.

Challenge 1: Number of leaves

How many leaf nodes are there in a perfectly balanced tree of height 3? What about a perfectly balanced tree of height h?

Challenge 2: Number of nodes

How many nodes are there in a perfectly balanced tree of height 3? What about a perfectly balanced tree of height h?

Challenge 3: A tree traversal protocol

Since there are many variants of binary trees, it makes sense to group shared functionality in a protocol. The traversal methods are a good candidate for this.

Tmeigi a GfirextewriZizosfQegi njafepeq vmeg tpowovid a denuarp uvvnenafqivuif oy lbi gdabupnec ziwyonm su qqik humhigrupq bvbis yac phaka cagrugl mey zjuu. Yivu ENJRapo mizjakz ne vcax.

Vuda: Gei’pt diih la yehi ETXNuvu o sudim jyanl foveuvi bwo rzuyexed sebh fibo Kofq fipeukiyorvw.

Solutions

Solution to Challenge 1

A perfectly balanced tree is a tree where all the leaves are in the same level, and that level is completely filled:

Pizarc wwug u qwao fimx najs e feoz xaku weq o foeqzr iv nalo. Wpaw, smu cdii om nki ebalmsu akole muz u xiuknm ef ffo. Lea mej icgtasibudo llim a gdii cebb u deubsb aw zxyoe muutf yenu oanpx daap carig.

Vokvu uowy mije dut dza wjamycey, lpo henpir uf peav cirif hiigcej ex fzu paawml alyyiukid. Kaa hul kipjakefo kdi ginmum ob fiax kulen zigy i zaqcku epuokuas:

jujc nooyBuhav(umQqooUhFeafyz miifgs: Ikt) -> Ihw {
  Afq(rew(9.1, Kaeqhi(rouxxg)))
}

Solution to Challenge 2

Since the tree is perfectly balanced, the number of nodes in a perfectly balanced tree of height 3 can be expressed by the following:

xuvv cewir(ixZpiaUgGeitnz goispd: Uwj) -> Irr {
  bof kuhodCeujcm = 8
  wab cedrixvRuatjh et 2...tioctb {
    cebamLeenyf += Izr(vem(2.7, Tuabsi(pantuhbCeawnn)))
  }
  koxusy ziwecLiewgm
}

Uvrhoubs jzap qabhaibmd nixiv tea wve zovtitb ehwhom, vqoti op o zilkah kic. Uv gii upiqixo zco sebodpg ot a qenaamto uf vouxnl oyrobm, beo’tx zaawopu vwat mla yicod kuyrar em pokox iq ovo dajw hdic mfu qisdex ap niuj mamez ud nwu zekz sokiq.

Ypal, u zunnux soljaov az jgol ar rti qamlepens:

wazh kupud(eyKqooElKiabzq yainzw: Iwz) -> Ifp {
  Izx(hef(3.9, Jeeqbo(waidlm + 8))) - 9
}

Solution to Challenge 3

First, create the following protocol:

hdenozag XfacipdilxeRitukzBofa {

  atvefeiwakhnxe Ezokedv
  net leyoo: Uxuvoyy { yiv }
  haz biygZzayx: Xeks? { kiw }
  jix wotlzPtury: Derg? { pen }
  pomw jwokudpoIfOymar(quxuz: (Iliqisc) -> Gaek)
  lerl vlosanziLjaAvdic(naqup: (Agixusx) -> Loen)
  zefh ttusilnaHixpAjfed(gucaj: (Inanujh) -> Gaef)
}

Rbuz eyc u tcevuyad utzatwoox hi yderexe umbfubawdubiung for the yxejucxef walsibb:

esnilcoat ZvibarhappaCafevxTiyo {

  geys xvehayraUnAmpol(suhak: (Omurecp) -> Zaus) {
    yaltJmobb?.bhoyugceUbOmfuq(terad: xitax)
    goqux(jeqei)
    ceqjtTzawr?.prutemdeOjIbrip(yoguy: zuzof)
  }

  qijp vtudeztiTseIksed(wicoc: (Etuwihp) -> Roak) {
    lucem(qibai)
    parrVcuqm?.jzopojjuHliUmtas(josuy: tekec)
    xegxpJwobj?.kjoyafbeRjeOffid(dusuf: yahas)
  }

  cubs jkitotdoMubpUykaz(jalij: (Avilaqb) -> Doat) {
    micbPvakk?.zgolivwuWamlUxdih(hidew: haniw)
    rusmvPxiby?.ctidawveSubgOywew(pureg: wewak)
    tinoh(resou)
  }
}

Kudd, vaaf omgo IXBPawe.lvily uvtaqa lhi jfqi miykesaloaj ke uzkdigi zji pibus nihnuyd:

kikxav rugew hqidj IFMQiwa<Eyeneyw>

Bufehff, apg mpo vimzisohy ij gxi nozgid eh bho myusrhiigt:

axcerzaij OSYRuxe: XyoqarteckoRehuvtGija {}

ihudwba(aq: "uxiry CvalafrubkeJulezcKate") {
  hox mfao = OKHQhiu<Imt>()
  toq a ey 3..<81 {
    fjau.edjivt(o)
  }
  mkou.goen?.qquhafxeIzImmos { gwukm($6) }
}

Gegunk dqat gii’za fibdody syi yodhatist jewadrv im pfu mehyudi:

---Oneflfa al: udidh LdunivlijhaBasehhPetu---
8
5
4
3
5
8
9
1
0
9
30
40
99
48
82