Invariantas ir keturi apėjimai

Visa struktūra remiasi vienu sakiniu.

BST invariantas

Kiekvienam mazgui: visi kairiojo pomedžio raktai yra mažesni už jo raktą, visi dešiniojo — didesni.

Ne „vaikas kairėje mažesnis", o visas pomedis. Iš to plaukia viskas kita.

Mazgas turi raktą ir dvi rodykles:

node:
    key    raktas (pavadinimas)
    item   įrašas
    left   rodyklė į mažesniuosius
    right  rodyklė į didesniuosius

Dešimtoje pamokoje mazgas turėjo vieną rodyklę (next grandinėlėje). Čia jų dvi — ir šeštame žingsnyje pamatysi, kiek tai kainuoja atmintimi.

Paieška

Kiekvienas palyginimas atmeta visą pomedį:

Get(title):
    cur ← root
    kol cur ≠ nil:
        c.Hit()
        jei title < cur.key: cur ← cur.left
        jei title > cur.key: cur ← cur.right
        kitaip:              grąžink cur.item, true
    grąžink tuščią, false

Tai šeštos pamokos dvejetainė paieška, tik kelias iš anksto įrašytas į rodykles, o ne skaičiuojamas iš indeksų. Ta pati mintis: vienas palyginimas perpus sumažina liekančią erdvę.

„Perpus" — jeigu pomedžiai vienodo dydžio. Kai jie ne, kaina kyla, ir septintas žingsnis parodo, kaip toli tai gali nueiti.

Įterpimas

Įterpimas — ta pati paieška, tik baigiama ne radus, o pasiekus tuščią vietą:

Put(item):
    ieškok item.Title lygiai kaip Get
    jei radai: pakeisk įrašą (vienodas raktas, kaip 10 pamokoje)
    jei priėjai nil: čia ir įrašyk naują mazgą

Naujas mazgas visada tampa lapu. Medis niekada nesitvarko iš naujo — todėl įterpimo tvarka nulemia formą, ir todėl septintas žingsnis apskritai įmanomas.

Apėjimas didėjimo tvarka (in-order)

Pirmojo žingsnio atsakymas, trimis eilutėmis:

walk(n):
    jei n = nil: grįžk
    walk(n.left)      // pirma visi mažesni
    išvesk n.key      // paskui aš
    walk(n.right)     // paskui visi didesni

Iš invarianto seka tiesiogiai: kairysis pomedis yra visi mažesni raktai, tad išvedus juos pirma, tada save, tada visus didesnius, gaunama didėjimo tvarka. O(n), be papildomos atminties ir be nė vieno palyginimo.

Rėžio užklausa

Tas pats apėjimas, tik su dviem sąlygomis, kurios nukerta nereikalingas šakas:

Range(lo, hi, n):
    jei n = nil: grįžk
    jei lo < n.key:            Range(lo, hi, n.left)    // kairėje gali būti
    jei lo ≤ n.key ≤ hi:       išvesk n.key
    jei n.key < hi:            Range(lo, hi, n.right)   // dešinėje gali būti

Būtent tos dvi jei sąlygos pavertė pirmo žingsnio 1 000 mazgų į 11: kai n.key jau didesnis už hi, visame dešiniajame pomedyje atsakymo būti negali, tad į jį net neužeinama.

Maišos lentelė tokio sprendimo priimti negali. Ji nežino, kas yra „didesnis".