Garantija, iki milijono

Pirmame žingsnyje užsirašei spėjimą: koks bus aukštis prie milijono įrašų, kai įvestis griežtai didėjanti?

$ go test -run AVLHeightGrowth -v

         n   height     log2 n    h/log2n    cmps/lookup   rot/insert
      1000       10       10.0       1.00          8.987        0.990
     10000       14       13.3       1.05         12.363        0.999
    100000       17       16.6       1.02         15.689        1.000
   1000000       20       19.9       1.00         18.951        1.000

20.

Milijonas įrašų, blogiausia įmanoma įterpimo tvarka, ir bet kurį pavadinimą randi per 19 palyginimų.

Stulpelis h/log2n

1.00   1.05   1.02   1.00

Ne „maždaug logaritmas". Aukštis yra log2(n), suapvalintas.

Palygink su vienuoliktos pamokos ta pačia lentele, kur BST buvo maitinamas maišyta — jam palankia — įvestimi:

	h ÷ log2 n
BST, maišyta įvestis (11 pamoka)	1.97 – 2.47
AVL, surikiuota įvestis (12 pamoka)	1.00 – 1.05

AVL medis blogiausiu atveju yra maždaug dvigubai negilesnis už BST jam geriausiu realiu atveju.

Ir tai galioja bet kuriai tvarkai

Vienuoliktos pamokos namų darbe reikėjo sugalvoti trečią blogiausią tvarką — nei didėjančią, nei mažėjančią. Atsakymas buvo zigzagas: imk pakaitomis iš abiejų likusios aibės galų. Jis irgi duodavo aukštį n.

n = 20000, riba 20.3

ascending    aukštis 15    0.999 rotacijos įterpimui
descending   aukštis 15    0.999 rotacijos įterpimui
zigzag       aukštis 18    1.623 rotacijos įterpimui

Zigzagas — brangiausia iš trijų: 1.62 rotacijos vienam įterpimui vietoj 1.0, ir medis trimis lygiais aukštesnis. Ir vis tiek gerokai po riba.

Būtent to ir reiškia žodis „garantija". Ne „mūsų bandytoms įvestims pavyko", o „nėra tokios įvesties, kuriai nepavyktų" — nes riba plaukia iš invarianto, kurį kiekvienas mazgas patikrina pats.

Kas pasikeitė, palyginti su vienuolikta pamoka

Vienuoliktos pamokos aštuntas žingsnis reikalavo keturių dalykų. Sudėkim juos šalia to, kas gauta:

reikalavimas	ar įvykdytas
medis persitvarko įterpimo metu	taip — rebalance grįžtant atgal
persitvarkymas kainuoja O(log n), ne O(n)	taip — patikrų tiek, koks kelio ilgis
BST invariantas išlieka	taip — TestRotationsPreserveTheOrdering
aukštis O(log n) garantuotai	taip — riba, patikrinta testu

Ir tai reiškia, kad vienuoliktos pamokos testas dabar turi kristi. Taip ir yra: TestSortedInsertDegeneratesIntoAList reikalauja Height() == n, o šis medis duoda 14. Sulaužyti tą testą ir buvo šios pamokos tikslas.