Drevesa.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d0356b4b-3b66-4348-9a70-f772acb4876c",
   "metadata": {},
   "source": [
    "# Drevesa\n",
    "\n",
    "Drevo je abstraktni podatkovni tip, ki hrani hierarhijo podatkov v svojih vozliščih. Uporabljamo jih lahko za predstavitev hierarhije, datotečne strukture, opis strukture aritmetičnih izrazov ali gramatike, opis poteka postopka, učinkovito organizacijo podatkov, ... V računalništvu rastejo drevesa od zgoraj navzdol. Zaradi raznolikosti različnih dreves ne bomo naštevali posameznih operacij na tem mestu, temveč se bomo z njimi ukvarjali na konkretnih primer drevesnih podatkovnih struktur.\n",
    "\n",
    "![Drevo - wikipedija](https://upload.wikimedia.org/wikipedia/commons/5/5f/Tree_%28computer_science%29.svg)\n",
    "\n",
    "### Terminologija\n",
    "\n",
    "Da se bomo lahko pogovarjali o drevesih, si oglejmo nekaj običajne terminologije v zvezi z njimi.\n",
    "\n",
    "- **Vozlišče** (*node/vertex*) je osnovni gradnih drevesa, ki lahko hrani nek podatek in **povezave** (*edge/link*) do drugih vozlišč. Vrhnje vozlišče v drevesu, ki predstavlja začetek drevesa, se imenuje **koren** (*root*). Struktura drevesa je rekurzivna, saj vozlišča hranijo povezave do korenov **poddreves** (*subtree*), ki imajo enako strukturo. Vozliščem, ki nimajo nadaljnjih povezav, rečemo **listi** (*leaves*) ali **zunanja** (*external*) vozlišča, ostalim pa **notranja** (*internal*).\n",
    "\n",
    "- Povezave v drevesu povezujejo **starša** (*parent*) z **otrokom** (*child*). Starš in otroci vozlišča so njegovi **sosedi** (*neighbours*). Koren nima starša, vsa ostala vozlišča v drevesu pa imajo natanko enega. Vsa vozlišča razen listov imajo svoje otroke. Otrokom istega vozlišča rečemo **sorojenci** (*siblings*). Vsa vozlišča v poddrevesih otrok se imenujejo **potomci** (*descendants*). Do njih pridemo po poti od  vozlišča proti listom. Vzdolž poti od vozlišča proti korenu pa se nahajajo **predniki** (*ancestors*).\n",
    "\n",
    "- Številu otrok rečemo tudi **stopnja** (*degree*) vozlišča, skupnemu številu vozlišč v drevesu pa **velikost** (*size*) drevesa. **Globina** (*depth*) vozlišča je število povezav na poti od korena do tega vozlišča. Globina korena je tako običajno 0, včasih pa se uporablja tudi 1. **Višina** (*height*) drevesa je največja globina vozlišča v njem, torej dolžina najdaljše poti do nekega lista.\n",
    "\n",
    "- Običajno si predstavljamo, da so drevesa \"košata\" in ne prav globoka. Takim \"lepim\" drevesom z nizko višino rečemo **uravnotežena** (*balanced*) drevesa. Če temu ni tako, rečemo, da je drevo **izrojeno** (*degenerate*), npr. povezan seznam je ekstremen primer izrojenega drevesa. Ločnica med uravnoteženimi in izrojenimi primeri je odvisna od primera uporabe. Načeloma pa bomo rekli, da imajo uravnotežena drevesa višino, ki je logaritemsko odvisna od števila vozlišč v njem, torej $h = O(\\log n)$, izrojena pa so vsa ostala.\n",
    "\n",
    "Pomembna lastnost dreves je, da med vsakim parom vozlišč obstaja enolično določena pot. Drevesa so poseben primer grafov, kjer to v splošnem ne velja in predstavlja glaven vir komplikacij. Poleg tega se bomo ukvarjali z drevesi s korenom oz. ukoreninjenimi drevesi (*rooted tree*). V teoriji grafov namreč obstaja koncept drevesa, ki pomeni, da graf ne vsebuje ciklov in ima zato enolično določene poti med pari vozlišč, vendar nima posebej določenega korenskega vozlišča. Več o grafih pa kasneje.\n",
    "\n",
    "### Obhodi dreves\n",
    "\n",
    "Obhod drevesa je sistematičen postopek, ki obišče vsa vozlišča drevesa v nekem vrstnem redu. Poznamo štiri pogoste vrste obhodov:\n",
    "\n",
    "- **Premi** (*pre-order*) obhod obišče vozlišče, nato pa rekurzivno po vrsti vsa poddrevesa.\n",
    "- **Vmesni** (*in-order*) obhod obišče najprej levo poddrevo, nato vozlišče in nato še desno poddrevo (v primeru dvojiškega drevesa). Če gre za iskalno drevo, nam vmesni obhod vrne urejeno zaporedje.\n",
    "- **Obratni** (*post-order*) obhod obišče rekurzivon vsa poddrevesa in šele nato vozlišče.\n",
    "- **Nivojski** (*level-order*) obhod obišče vozlišča po nivojih, najprej koren, nato njegove otroke, nato otroke teh otrok, itd.\n",
    "\n",
    "![Obhodi drevesa - wikipedija](https://upload.wikimedia.org/wikipedia/commons/7/75/Sorted_binary_tree_ALL_RGB.svg)\n",
    "\n",
    "Zgornja slika prikazuje vrstni red obravnave vozlišč pri različnih obhodih. Premi obhod (F, B, A, D, C, E, G, I, H) je prikazan z rdečo, vmesni (A, B, C, D, E, F, G, H, I) z zeleno, obratni (A, C, E, D, B, H, I, G, F) pa z modro.\n",
    "\n",
    "### Vrste dreves\n",
    "\n",
    "V splošnem ni nobene potrebe po tem, da morajo biti podatkih v drevesu na kakšen poseben način urejeni, v praksi pa se izkažejo kot uporabna prav zaradi tega. Oglejmo si torej nekaj primerov posebnih drevesnih struktur in urejenost podatkov v njih.\n",
    "\n",
    "- Najbolj pogosta so **dvojiška** (*binary*) drevesa, kjer ima vsako vozlišče dva otroka. Bolj splošen koncept je **k-tiško** (*k-ary*) drevo, v katerem ima vsako vozliščo največ k otrok.\n",
    "- **Polno** (*full*) drevo ima v vsakem vozlišču maksimalno število otrok ali nobenega, torej v polnem dvojiškem drevesu ni vozlišč s samo enim otrokom. **Poravnano/celovito** (*complete*) drevo smo že spoznali na primeru kopice. **Popolna** (*prefect*) drevesa so polna in imajo vse liste na enaki globini oz. vsebujejo maksimalno število vozlišč glede na višino drevesa.\n",
    "- Glede na to, ali obstaja urejenost med otroci poznamo **urejena** in **neurejena** (*ordered/unordered*) drevesa. V slednjih je vrstni red otrok nepomemben. V neurejenem dvojiškem drevesu torej koncept levega in desnega otroka ne obstaja.\n",
    "- Pomembna so tudi **iskalna** (*search*) drevesa, ki so urejena drevesa, v katerih velja, da vsebuje prvi otrok v svojem poddrevesu najmanjše vrednosti, drugi malo večje itd. Vrednost ali vrednosti, ki predstavljajo ločnice med njimi, pa so shranjene v vozlišču.\n",
    "- Omenimo še **črkovna/znakovna** drevesa (*trie*). Ta so namenjena hrambi zaporedij, ki so sestavljena iz znakov majhne oz. omejene abecede. V njih posamezno vozlišče hrani povezavo do otroka za vsak možen znak abecede.\n",
    "\n",
    "### Predstavitev dreves\n",
    "\n",
    "Glede na funkcionalnost, ki jo želimo od drevesa, ga lahko predstavimo na različne načine. Najbolj običajna predstavitev je s *seznamom otrok*, kjer v vsakem vozlišču poleg podatka hranimo še povezave do otrok. Če gre za dvojiško drevo, sta to dve povezavi, sicer pa je lahko seznam povezav. Če se bomo v drevesu premikali samo po poteh proti korenu, je dovolj tudi, da za vsako vozlišče hranimo *povezavo do starša*. Morda pa se sploh ne bomo premikali med vozlišči in bo dovolj kar *seznam povezav* v drevesu.\n",
    "\n",
    "Povezave do otrok in do starša običajno hranimo kot kazalce ali reference do njih. V primeru posebej urejene strukture drevesa, pa lahko uporabljamo tudi *implicitno predstavitev* s tabelo, kjer lahko na podlagi indeksov določamo starše in otroke, kot smo to videli že pri kopici. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "57cbe1de-efcd-4916-8b99-20d91b43dfb7",
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <iostream>\n",
    "#include <vector>\n",
    "#include <random>\n",
    "#include <algorithm>\n",
    "using namespace std;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a3f3cab-e49b-48fa-bf45-e86b02147d62",
   "metadata": {},
   "source": [
    "Oglejmo si primer implementacije dvojiškega iskalnega drevesa. Podprli bomo samo **vstavljanje** novih vrednosti in vmesni obhod. Zaradi rekurzivne strukture drevesa je običajno dovolj, da predstavimo drevo kar s korenskim vozliščem in tudi funkcionalnost implementiramo na posameznih vozliščih."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "1847b942-e982-45b2-8a29-e36662cfeef3",
   "metadata": {},
   "outputs": [],
   "source": [
    "class BSTree {\n",
    "public:\n",
    "    int value;\n",
    "    BSTree *left, *right;\n",
    "    BSTree(int v, BSTree *l=NULL, BSTree *r=NULL) : value(v), left(l), right(r) {}\n",
    "\n",
    "    void insert(int x) {\n",
    "        if (x<=value) {\n",
    "            if (!left) left = new BSTree(x);\n",
    "            else left->insert(x);\n",
    "        } else {\n",
    "            if (!right) right = new BSTree(x);\n",
    "            else right->insert(x);\n",
    "        }\n",
    "    }\n",
    "\n",
    "    void inorder(vector<int> &seq) {\n",
    "        if (left) left->inorder(seq);\n",
    "        seq.push_back(value);\n",
    "        if (right) right->inorder(seq);\n",
    "    }\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "34538963-ae91-4cda-98d9-e2667b53d798",
   "metadata": {},
   "source": [
    "V drevo bomo vstavili večje število naključnih vrednosti. Zaradi naključnosti pričakujemo, da se drevo ne bo izrodilo in bo postopek dovolj učinkovit. Če izpišemo začetek vmesnega obhoda, vidimo, da so vrednosti urejene."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "512a73d8-cfcc-44cb-b1ba-4ee93ca26c3b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 0 1 3 3 3 6 6 8 9 \n"
     ]
    }
   ],
   "source": [
    "int n=100'000;\n",
    "default_random_engine rnd(123);\n",
    "BSTree bst(rnd()%n);\n",
    "for (int i=0;i<n-1;i++) bst.insert(rnd()%n);\n",
    "vector<int> s;\n",
    "bst.inorder(s);\n",
    "for (int i=0;i<10;i++) cout << s[i] << \" \";\n",
    "cout << endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d335a3eb-6882-4572-b6c0-8bf3721c2d49",
   "metadata": {},
   "source": [
    "Kako pa **izbrišemo** vrednost iz dvojiškega iskalnega drevesa? Če vozlišče nima otrok, ga preprosto odstranimo. Če ima samo enega otroka, ga lahko zamenjamo z njim. Težava nastane, če ima vozlišče oba otroka. V tem primeru ga zamenjamo z naslednjim večjim vozliščem. To je vozlišče, ki je najmanjše oz. najbolj levo vozlišče v desnem poddrevesu. To vozlišče zagotovo nima levega otroka, zato ga lahko enostavno odstranimo. V praksi lahko malo pogoljufamo, če je to sprejemljivo, in namesto brisanja samo označimo neko vozlišče kot izbrisano, namesto da bi ga prav odstranili."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "30eb2c9e-223d-4837-9146-3ebb9a787afc",
   "metadata": {},
   "source": [
    "Koncept organizacije podatkov v drevesno strukturo v večini primerov predstavlja samo izhodišče in v neprilagojeni obliki ne bo neposredno uporabno za učinkovito reševanje problema. Lahko pa podatkovno strukturo **razširimo** z dodatnimi podatki, ki bi nam prišli prav. V vsakem vozlišču bi lahko npr. hranili tudi velikost poddrevesa. To bi nam npr. omogočilo učinkovito štetje elementov v drevesu, ki so manjši od izbrane vrednosti."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f9842dc2-5273-451b-bd4f-2445f3b8ad1d",
   "metadata": {},
   "source": [
    "## Poizvedbe na območjih\n",
    "\n",
    "Namen dreves na področju algoritmov in podatkovnih struktur je učinkovita organizacija podatkov. Prav nam bodo prišla *statična drevesa*, ki ne omogočajo vstavljanj in brisanj elementov, ki bi spreminjala strukturo drevesa, ampak samo spremebo shranjenih vrednosti.\n",
    "\n",
    "Razvili bomo rešitve za nekaj vedno kompleksnejših problemov o poizvedbah na območjih tabele. Opravka bomo imeli s tabelo $A$, ki vsebuje $n$ celih števil, $A = [a_0, a_1, \\dots, a_{n-1}]$. Poizvedbe pa se bodo nanašale na neko območje $[l,r)$. Rezultat poizvedbe $q(l,r)$ je torej vrednost, če upoštevamo samo elemente $a_l, a_{l+1}, \\dots, a_{r-1}$. \n",
    "\n",
    "Podatke v tabeli bomo najprej obdelali in organizirali, da bomo lahko nato učinkovito odgovarjali na poizvedbe. Ločeno bomo torej obravnavali časovno in prostorsko zahtevnost predobdelave (*preprocessing*) in poizvedb (*query*).\n",
    "\n",
    "### Vsota\n",
    "\n",
    "Najprej si oglejmo poizvedbo o vsoti (*range sum query*): $q(l,r) = \\sum_{i=l}^{r-1} a_i$. Tu ni potrebe po prevelikem kompliciranju. Ker ima seštevanje inverzno operacijo odštevanja, si lahko pripravimo tabelo kumulativnih vsot od začetka tabele $c_r = \\sum_{i=0}^{r-1} a_i$. Če odštejemo dve kumulativni vsoti, nam ostane vsota elementov med obema mejama: $q(l,r) = c_r - c_l$.\n",
    "\n",
    "predobdelava (čas, prostor): $O(n)$, $O(n)$\n",
    "poizvedba (čas, prostor): $O(1)$, $O(1)$\n",
    "\n",
    "### Minimum\n",
    "\n",
    "Bistveno težja je poizvedba o najmanjši vrednosti oz. minimumu (*range minimum query*): $q(l,r) = \\min_{i=l..r-1} a_i$.\n",
    "\n",
    "#### Naivna rešitev\n",
    "\n",
    "Najbolj očitna rešitev je, da pri vsaki poizvedbi preverimo vse elemente na relevantnem območju in med njimi poiščemo najmanjšega.\n",
    "\n",
    "predobdelava (čas, prostor): $O(1)$, $O(1)$  \n",
    "poizvedba (čas, prostor): $O(n)$, $O(1)$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3fc373cb-d589-4286-938b-e5bb0571d6e2",
   "metadata": {},
   "source": [
    "#### Bloki\n",
    "\n",
    "Prejšnjo rešitev lahko poskusimo izboljšati s tem, da bi v procesu predobdelave že naredili nekaj izračunov, kar bi nam prihranilo kasnejše delo ob poizvedbah. Tabelo bomo razdelili na strnjene bloke (skupine, vedra, koše) velikosti $B$ in zanje vnaprej izračunali najmanjše vrednosti. Število blokov bo torej $\\lceil n/B \\rceil$. Ne glede na $B$ bomo potrebovali kvečjemu dvakrat toliko prostora. Za odgovor na posamezno poizvedbo lahko uporabimo že izračunane rezultate blokov, ki so v celoti znotraj intervala. Teh bo $O(n/B)$. Na levem in desnem robu pa obdelamo še preostale elemente, ki jih je $O(B)$.\n",
    "\n",
    "Oglejmo si primer s tabelo velikosti $n=11$ in velikostjo bloka $B=3$. Zgornja vrsta predstavlja vrednosti blokov, spodnja osnovno tabelo, pod njima pa so prikazani še indeksi. Za poizvedbo $[1, 10)$ bi uporabili označene vrednosti.\n",
    "\n",
    "<table>\n",
    "<tr>\n",
    "    <td colspan=\"3\" style=\"text-align: center; border: 1px solid\">4</td>\n",
    "    <td colspan=\"3\" style=\"text-align: center; border: 1px solid; background-color: coral\">2</td>\n",
    "    <td colspan=\"3\" style=\"text-align: center; border: 1px solid; background-color: coral\">1</td>\n",
    "    <td colspan=\"2\" style=\"text-align: center; border: 1px solid\">2</td>\n",
    "</tr>\n",
    "<tr>\n",
    "    <td style=\"border: 1px solid\">6</td>\n",
    "    <td style=\"border: 1px solid; background-color: coral\">8</td>\n",
    "    <td style=\"border: 1px solid; background-color: coral\">4</td>\n",
    "    <td style=\"border: 1px solid\">5</td>\n",
    "    <td style=\"border: 1px solid\">2</td>\n",
    "    <td style=\"border: 1px solid\">6</td>\n",
    "    <td style=\"border: 1px solid\">3</td>\n",
    "    <td style=\"border: 1px solid\">7</td>\n",
    "    <td style=\"border: 1px solid\">1</td>\n",
    "    <td style=\"border: 1px solid; background-color: coral\">2</td>\n",
    "    <td style=\"border: 1px solid\">9</td>\n",
    "</tr>\n",
    "<tr>\n",
    "    <td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td>\n",
    "</tr>\n",
    "</table>\n",
    "\n",
    "predobdelava (čas, prostor): $O(n)$, $O(n)$  \n",
    "poizvedba (čas, prostor): $O(n/B + B)$, $O(1)$\n",
    "\n",
    "Kakšen $B$ naj izberemo, da bodo poizvedbe čim hitrejše? Če so bloki majhne, moramo upoštevati veliko blokov. Če so bloki veliki, pa imamo veliko opravka z elementi na robu območja, ki niso del blokov v celoti vsebovanih v območju. Dober kompromis je izbira $B = \\sqrt{n}$, saj je $O(n/\\sqrt{n} + \\sqrt{n}) = O(\\sqrt{n})$.\n",
    "\n",
    "predobdelava (čas, prostor): $O(n)$, $O(n)$  \n",
    "poizvedba (čas, prostor): $O(\\sqrt{n})$, $O(1)$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "993587ec-fb8a-4640-b1b1-d60d523db863",
   "metadata": {},
   "source": [
    "#### Statično drevo\n",
    "\n",
    "Zakaj bi se ustavili samo pri enem nivoju skupin, če pa lahko naredimo še skupine skupin in nad njimi še en nivo itd. To pa je že drevesna struktura. Nad tabelo lahko sestavimo statično dvojiško drevo, ki bo v listih hranilo vrednosti iz tabele, v notranjih vozliščih pa najmanjšo vrednost na pripadajočem območju.\n",
    "\n",
    "Brez škode za računsko zahtevnost lahko podaljšamo tabelo do potence števila 2 in shranimo drevo kar implicitno v novi tabeli, ki predstavlja popolno dvojiško drevo (koren ima indeks 1). Število notranjih vozlišč ne presega števila listov oz. osnovne velikosti tabele, torej je prostorska zahtevnots $O(n)$.\n",
    "\n",
    "<table>\n",
    "<tr>\n",
    "    <td colspan=\"16\" style=\"text-align: center; border: 1px solid\">1</td>\n",
    "</tr>\n",
    "<tr>\n",
    "    <td colspan=\"8\" style=\"text-align: center; border: 1px solid\">2</td>\n",
    "    <td colspan=\"8\" style=\"text-align: center; border: 1px solid\">1</td>\n",
    "</tr>\n",
    "<tr>\n",
    "    <td colspan=\"4\" style=\"text-align: center; border: 1px solid\">4</td>\n",
    "    <td colspan=\"4\" style=\"text-align: center; border: 1px solid; background-color: coral\">2</td>\n",
    "    <td colspan=\"4\" style=\"text-align: center; border: 1px solid; background-color: coral\">1</td>\n",
    "    <td colspan=\"4\" style=\"text-align: center; border: 1px solid\">2</td>\n",
    "</tr>\n",
    "<tr>\n",
    "    <td colspan=\"2\" style=\"text-align: center; border: 1px solid\">6</td>\n",
    "    <td colspan=\"2\" style=\"text-align: center; border: 1px solid; background-color: coral\">4</td>\n",
    "    <td colspan=\"2\" style=\"text-align: center; border: 1px solid\">2</td>\n",
    "    <td colspan=\"2\" style=\"text-align: center; border: 1px solid\">3</td>\n",
    "    <td colspan=\"2\" style=\"text-align: center; border: 1px solid\">1</td>\n",
    "    <td colspan=\"2\" style=\"text-align: center; border: 1px solid\">2</td>\n",
    "    <td colspan=\"2\" style=\"text-align: center; border: 1px solid\">7</td>\n",
    "    <td colspan=\"2\" style=\"text-align: center; border: 1px solid\">2</td>\n",
    "</tr>\n",
    "<tr>\n",
    "    <td style=\"border: 1px solid\">6</td>\n",
    "    <td style=\"border: 1px solid; background-color: coral\">8</td>\n",
    "    <td style=\"border: 1px solid;\">4</td>\n",
    "    <td style=\"border: 1px solid\">5</td>\n",
    "    <td style=\"border: 1px solid\">2</td>\n",
    "    <td style=\"border: 1px solid\">6</td>\n",
    "    <td style=\"border: 1px solid\">3</td>\n",
    "    <td style=\"border: 1px solid\">7</td>\n",
    "    <td style=\"border: 1px solid\">1</td>\n",
    "    <td style=\"border: 1px solid\">2</td>\n",
    "    <td style=\"border: 1px solid\">9</td>\n",
    "    <td style=\"border: 1px solid\">2</td>\n",
    "    <td style=\"border: 1px solid; background-color: coral\">7</td>\n",
    "    <td style=\"border: 1px solid\">8</td>\n",
    "    <td style=\"border: 1px solid\">4</td>\n",
    "    <td style=\"border: 1px solid\">2</td>\n",
    "</tr>\n",
    "<tr>\n",
    "    <td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td><td>11</td><td>12</td><td>13</td><td>14</td><td>15</td>\n",
    "</tr>\n",
    "</table>\n",
    "\n",
    "Za poizvedbo $[1, 13)$ bi uporabili označena vozlišča. Za odgovor na poizvedbo bomo na vsakem nivoju potrebovali kvečjemu dve vozlišč (eno na levi eno na desni strani), zato jih bo vse skupaj $O(\\log n)$. Poiščemo jih lahko rekurzivno s premikanjem od korena proti listom, pri čemer se ustavimo, ko je vozlišče v celoti znotraj ali pa v celoti izven območja poizvedbe.\n",
    "\n",
    "predobdelava (čas, prostor): $O(n)$, $O(n)$  \n",
    "poizvedba (čas, prostor): $O(\\log{n})$, $O(\\log{n})$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "b5bcb525-20f3-42c4-9c4b-a198751e4833",
   "metadata": {},
   "outputs": [],
   "source": [
    "class RMQ {\n",
    "private:\n",
    "    int n;\n",
    "    vector<int> array;\n",
    "    struct Node { int min, begin, end; };\n",
    "    vector<Node> tree;\n",
    "    int INF=1e9;\n",
    "public:\n",
    "    RMQ(vector<int> &a) {\n",
    "        n = pow(2, ceil(log2((double)a.size())));  // potenca 2\n",
    "        array = a;\n",
    "        array.resize(n, INF);\n",
    "        tree.resize(2*n);\n",
    "        build();\n",
    "    }\n",
    "\n",
    "    void build(int id=1) {\n",
    "        if (id>=n) { tree[id] = {array[id-n], id-n, id-n+1}; return; }  // list\n",
    "        int left=2*id, right=2*id+1;\n",
    "        build(left); build(right);\n",
    "        tree[id] = {min(tree[left].min, tree[right].min), tree[left].begin, tree[right].end};\n",
    "    }\n",
    "\n",
    "    int query(int l, int r, int id=1) {\n",
    "        if (l<=tree[id].begin && tree[id].end<=r) return tree[id].min;  // znotraj\n",
    "        if (r<=tree[id].begin || tree[id].end<=l) return INF;           // zunaj\n",
    "        return min(query(l,r,2*id), query(l,r,2*id+1));\n",
    "    }\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3335c6e7-903c-4ca1-adf8-40692e93554a",
   "metadata": {},
   "source": [
    "Preverimo še pravilnost naše rešitve s primerjavo z naivnim pristopom iskanja najmanjšega elementa."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "a28fe641-50ff-48cd-a555-f5681db60d86",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "done\n"
     ]
    }
   ],
   "source": [
    "int n=100'000;\n",
    "default_random_engine rnd(123);\n",
    "vector<int> v;\n",
    "for (int i=0;i<n;i++) v.push_back(rnd()%1'000'000'000);\n",
    "RMQ rmq(v);\n",
    "for (int it=0;it<100;it++) {\n",
    "    int l=rnd()%n, r=rnd()%(n+1);\n",
    "    if (l>=r) continue;\n",
    "    if (rmq.query(l, r) != *min_element(v.begin()+l, v.begin()+r)) cout << \"ups\" << endl;\n",
    "}\n",
    "cout << \"done\" << endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ec2fddd3-edc8-4eeb-aa42-f136024d87a4",
   "metadata": {},
   "source": [
    "### Spremembe vrednosti\n",
    "\n",
    "Rešitev s statičnim drevesom je učinkovitejša od rešitve z bloki. Lahko morda omogočimo tudi spreminjanje posameznih vrednosti v statičnem drevesu, ne da bi imelo to vpliv na učinkovitost ostalih operacij? Sprememba vrednosti vpliva na vsa notranja vozlišča, ki se raztezajo čez njo. Tako vozlišče je na vsakem nivoju eno, zato jih je skupaj $O(\\log n)$. Relevantna vozlišča poiščemo enostavno s sprehodom od korena proti spremenjenemu listu. Nato pa od lista proti korenu popravljamo izračunane vrednosti oz. jih za vsako tako notranje vozlišče ponovno izračunamo iz rezultatov v obeh otrocih (kjer je bil rezultat enega otroka ravnokar spremenjen)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c8523448-f21f-4206-82fc-ace93cdbc0fb",
   "metadata": {},
   "source": [
    "### Druge funkcije/poizvedbe\n",
    "\n",
    "Pri izvajanju poizvedb na območju $[l,r)$ tabele $A$ nas lahko zanimajo tudi kakšne kompleksnejše funkcije od vsote in minimuma, ki smo si ju že ogledali. Oglejmo si par primerov.\n",
    "\n",
    "- število najmanjših vrednosti\n",
    "\n",
    "  Če v vozliščih hranimo zgolj odgovor na zastavljeno vprašanje, ne moremo združiti rezultatov dveh sosednjih območij v rezultat večjega starševskega območja. Lahko pa smo iznajdljivi in hranimo še kakšen dodaten podatek. Poleg števila najmanjših vrednosti $f$, bomo hranili še dejansko najmanjšo vrednost $m$. Če imamo rezultate za levo območje $(f_1, m_1)$ in desno območje $(f_2, m_2)$, ju lahko združimo. Če je $m_1 = m_2$, je združen rezultat $(f_1+f_2, m_1)$, sicer pa vzamemo rezultat tistega območja, ki ima manjšo najmanjšo vrednost ($m_1$ ali $m_2$).\n",
    "\n",
    "- $k$-ta ničla\n",
    "\n",
    "  Izračunamo predponske vsote števila neničelnih elementov in na tem seznamu predponskih vsot izvajamo bisekcijo. Torej ni nobene potrebe po kompliciranju z drevesno strukturo. Razen, če želimo omogočiti tudi spremembe elementov v tabeli, takrat pa potrebujemo drevo za učinkovito rešitev. Očitno je v vozliščih smiselno hraniti število ničel na pripadajočem območju. Tako lahko rekurzivno ugotavljamo, ali se $k$-ta ničla pojavi v levem podobmočju ali v desnem. Če se npr. pojavi v desnem, zmanjšamo $k$ za število ničel, ki se pojavijo v levem podobmočju in nadaljujemo z iskanjem na desni strani.\n",
    "\n",
    "- najmanjši element, ki je večji ali enak $x$\n",
    "\n",
    "  Problem izgleda precej zahteven, tudi če bi šlo ves čas za celotno območje $[1,n)$. V takem primeru bi želeli imeti urejene elemente, da lahko z bisekcijo poiščemo prvega, ki je večji ali enak meji $x$. Če imamo opravka še z različnimi območji, pa bomo v vsakem vozlišču drevesa hranili urejen seznam elementov s tega območja. Za združevanje dveh sosednjih območij, moramo samo zliti urejena seznama, kar lahko naredimo v linearnem času. Izgradnja je torej podobna urejanju z zlivanjem, le da shranjujemo vse vmesne zlite sezname. Vsak element tabele bo nastopal v $O(\\log n)$ zlivanjih, zato sta časovna in prostorska zahtevnost izgradnje $O(n \\log n)$. Na posamezno poizvedbo odgovorimo tako, da poiščemo odgovor v vseh $O(\\log n)$ vozliščih, ki pokrivajo območje. Odgovor za posamezno vozlišče pa tokrat zaradi bisekcije zahteva $O(\\log n)$ časa, zato je časovna zahtevnost poizvedbe $O(\\log^2 n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1a90ec70-fe12-41d9-9885-0565d44b7c5a",
   "metadata": {},
   "source": [
    "Ogledali smo si različne primere izvajanja poizvedb na območjih tabele v morebitni kombinaciji s spremembami posameznih elementov (*range query, point update*). S podobnimi prijemi se lahko lotimo nekoliko težjih problemov, kjer imamo opravka s spremembami na območju, zanimajo pa nas posamezne vrednosti v tabeli (*range update, point query*). Še kompleksnejša pa je kombinacija obeh, torej sprememb na območjih in poizvedb na območjih (*range update, range query*)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "27cd8380-ac73-4340-a4bc-7aa98a42d6fd",
   "metadata": {},
   "source": [
    "## Uravnotežena drevesa\n",
    "\n",
    "Navadna drevesa brez tehnike uravnoteževanja imajo težavo, da se lahko ob neugodnem vstavljanju elementov njihova struktura izrodi in lahko imajo višino, ki je linearno odvisna od števila elementov v drevesu. To je pravzaprav enako dobro oz. slabo kot navaden povezan seznam. V prejšnjem primeru smo se temu izognili z uporabo statičnega drevesa, ki ima fiksno strukturo, spreminja se zgolj vsebina vozlišč.\n",
    "\n",
    "Uravnoteženost pa lahko dosežemo tudi v nestatičnih drevesih, ki rastejo ali se manjšajo s številom vsebovanih elementov. Taka drevesa ohranjajo višino, ki je logaritemsko odvisna od števila elementov. Vse operacije dodajanja, odstranjevanja in iskanja elementov se izvedejo v $O(\\log n)$ časa. Tako dobimo strukturo, v katero lahko učinkovito vstavljamo, brišemo in v njej iščemo elemente, kar je pravzaprav podobno dvojiškemu iskanju. Struktura pa je povsem deterministična, torej ni odvisna od naključnosti kot npr. preskočni seznam. Tako jih lahko uporabimo za implementacijo slovarja ali množice."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1b2ba87a-d9a1-4532-aff1-f5750362db3d",
   "metadata": {},
   "source": [
    "### AVL drevo\n",
    "\n",
    "AVL drevo (avtorja Adelson-Velsky in Landis) je najbolj klasičen primer uravnoteženega drevesa. Gre za dvojiško iskalno drevo, kjer je uravnoteženost definirana s tem, da se v *vsakem vozlišču višini levega in desnega poddrevesa razlikujeta kvečjemu za 1*. Ta lastnost zagotavlja, da je višina drevesa $O(\\log n)$.\n",
    "\n",
    "Zakaj? Najmanj koliko vozlišč potrebujemo za AVL drevo višine $h$, recimo temu $f(h)$? Poddrevesi se lahko po višini razlikujeta za največ 1, zato bomo kot levo poddrevo uporabili AVL drevo višine $h-1$ s čim manj vozlišči, kot desno pa drevo višine $h-2$, ki potrebuje manj vozlišč. Potrebno število vozlišč je torej $f(h) = 1+f(h-1)+f(h-2)$. To zaporedje vrednosti se zgolj za 1 razlikuje od Fibonaccijevega zaporedja, za katerega vemo, da raste eksponentno.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "81fbd283-e9d7-4c42-902c-b403317ab918",
   "metadata": {},
   "source": [
    "Začnimo z enostavnim iskalnim drevesom brez uravnoteževanja, ki ga bomo nato dopolnili. Metoda za vstavljanje bo sprejela kazalec na vozlišče, v poddrevo katerega vstavljamo nov element. Vračala pa bo kazalec na koren drevesa z vstavljenim vozliščem. Strukturo dopolnimo še s podatkom o višini poddreves, ki nam bo prišel prav kasneje. Izračunajmo tudi faktorje uravnoteženosti v vsakem vozlišču (*balance*), ki je razlika med višino desnega in levega poddrevesa. Negativna vrednost torej predstavlja višje levo poddrevo, pozitivna pa višje desno."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "f6ec5c5b-aaf2-415c-9a35-2ec63d1eb1bc",
   "metadata": {},
   "outputs": [],
   "source": [
    "class AVLNode {\n",
    "public:\n",
    "\tint value;\n",
    "\tAVLNode *left, *right;\n",
    "\tint height;\n",
    "\tAVLNode(int v) : value(v), left(NULL), right(NULL), height(1) { }\n",
    "};\n",
    "\n",
    "class AVLTree {\n",
    "public:\n",
    "\tAVLNode *root = NULL;\n",
    "\n",
    "\tint height() { return height(root); }\n",
    "\tint height(AVLNode* node) { return (node!=NULL)?node->height:0; }\n",
    "\tint balance(AVLNode* node) { return height(node->right) - height(node->left); }\n",
    "\tvoid update(AVLNode* node) { node->height = 1 + max(height(node->left), height(node->right)); }\n",
    "\n",
    "    // implementirano kasneje\n",
    "    AVLNode* rotateLeft(AVLNode* node);\n",
    "    AVLNode* rotateRight(AVLNode* node);\n",
    "\n",
    "\tbool contains(int x) { return contains(x, root); }\n",
    "\tbool contains(int x, AVLNode* node) {\n",
    "\t\tif (node==NULL) return false;\n",
    "\t\telse if (node->value==x) return true;\n",
    "\t\telse if (x < node->value) return contains(x, node->left);\n",
    "\t\telse return contains(x, node->right);\n",
    "\t}\n",
    "\n",
    "    // dopolnjeno kasneje z uravnotezevanjem\n",
    "\tvoid insert(int x) { root = insert(x, root); }\n",
    "\tAVLNode* insert(int x, AVLNode* node) {\n",
    "\t\tif (node==NULL) { return new AVLNode(x); }\n",
    "\t\tif (x <= node->value) node->left = insert(x, node->left);\n",
    "\t\telse node->right = insert(x, node->right);\n",
    "        update(node);\n",
    "\t\treturn node;\n",
    "\t}\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "29335478-ee64-469d-bd07-d580964f9785",
   "metadata": {},
   "source": [
    "Če v tako drevo vstavljamo naraščajoče vrednosti, bomo dobili izrojeno drevo. Če preverjamo še vsebovanost elementov, dobimo kvadratno število operacij."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "314c6176-fafa-45de-8b4c-32c8449c607a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1000\n"
     ]
    }
   ],
   "source": [
    "default_random_engine rnd(123);\n",
    "AVLTree avl;\n",
    "int n=1000;\n",
    "for (int i=0;i<n;i++) {\n",
    "    avl.insert(i);\n",
    "    assert(avl.contains(i) && !avl.contains(i+1));\n",
    "}\n",
    "cout << avl.height() << endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7860c925-2ac9-4869-b678-b3dcd1827421",
   "metadata": {},
   "source": [
    "Osnovna operacija, s katero bomo popravljali strukturo drevesa, je rotacija. Poznamo levo in desno rotacijo. Če naredimo levo rotacijo na drevesu s korenom A, ga zamenjamo z njegovim desnim otrokom B in primerno prevežemo njuna poddrevesa X (levi otrok A-ja), Y (levi otrok B-ja) in Z (desni otrok B-ja). Pri tem vozlišči A in B zamenjata svoj nivo. Poddrevo X se spusti za en nivo, nivo Y-a se ne spremeni, nivo Z-ja pa dvigne za en nivo. Po prevezavah moramo posodobiti višine dreves s koreni A in B, višine ostalih pa se ne spremenijo.\n",
    "\n",
    "<img alt=\"rotacija - University of Wisconsin-Madison\" src=\"https://pages.cs.wisc.edu/~ealexand/cs367/NOTES/AVL-Trees/avl4.png\" width=\"350px\"/>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "9d2669e1-b797-43ca-8886-eaa013edd6f6",
   "metadata": {},
   "outputs": [],
   "source": [
    "AVLNode* AVLTree::rotateLeft(AVLNode* node) {\n",
    "    AVLNode *R=node->right;\n",
    "    node->right=R->left; R->left=node;\n",
    "    update(node); update(R);\n",
    "    return R;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "b0275b2f-eb8c-4ac2-93cd-bb60d0d8e69e",
   "metadata": {},
   "outputs": [],
   "source": [
    "AVLNode* AVLTree::rotateRight(AVLNode* node) {\n",
    "    AVLNode *L=node->left;\n",
    "    node->left=L->right; L->right=node;\n",
    "    update(node); update(L);\n",
    "    return L;\n",
    "}"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "cfb03777-8260-45fe-99fb-cda776dd108c",
   "metadata": {},
   "source": [
    "Sedaj moramo vstavljanju dodati še logiko uravnoteževanja, ki bo poskrbela, da bodo tudi po vstavljanju novega vozlišča ostala vsa vozlišča uravnotežena (torej velikosti njihovih poddreves). Novo vozlišče bomo vstavili kot običajno, nato pa bomo ob vračanju proti korenu po potrebi popravljali strukturo z rotacijami. Pri tem lahko naletimo na več situacij, ki jih bomo obravnavali v nadaljevanju.\n",
    "\n",
    "Naj bo X najgloblje vozlišče, ki ima zaradi novo vstavljenega vozlišča (minimalno) neprimeren faktor uravnoteženosti, ki je lahko -2 ali 2 (primera sta simetrična). Omejimo se na faktor 2, kjer je desno poddrevo vozlišča X previsoko glede na levo poddrevo. To se je zgodilo, ker smo novo vozlišče vstavili na desno stran v poddrevo s korenom Z, ali pa ker smo popravljali enega od X-ovih poddreves. Poddrevo Z ne vsebuje samo enega vozlišča, sicer ne bi moglo priti do take neuravnoteženosti. Poleg tega vemo, da je vozlišče Z že uravnoteženo.\n",
    "\n",
    "Najprej obravnavajmo primer (ilustriran levo), ko ima vozlišče Z faktor 1 ali 0. Izvedemo enojno levo rotacijo na vozlišču X, s čimer poskrbimo za uravnoteženost v vozliščih X in Z. Višina drevesa je ostala enaka, ali pa se je znižala za 1.\n",
    "\n",
    "V drugem primeru (ilustriran desno) ima vozlišče Z faktor -1. Njegov levi otrok Y je torej višji od desnega.  Samo z levo rotacijo na korenu ne bi spremenili globine poddrevesa Y, ki seže najgloblje. Pred tem ga bomo morali dvigniti. Zato izvedemo dvojno rotacijo, ki bo spravila Y v koren. Najprej naredimo desno rotacijo na vozlišču Z, nato sledi še leva rotacijo na vozlišču X. Tudi v tem primeru so vozlišča X, Y in Z uravnotežena, višina drevesa pa se zniža za 1.\n",
    "\n",
    "V obeh primerih smo razrešili neuravnoteženost, vendar se je pri tem višina drevesa lahko znižala za 1, kar lahko povzroči novo neuravnoteženost, ki pa je bližje korenu in jo razrešimo kasneje. V primeru vstavljanja elementa se sicer izkaže, da do tega ne more priti, ker rotacija oz. par rotacij vzpostavi višino neuravnoteženega poddrevesa na vrednost, kot je bila pred novo vstavljenim elementom (takrat pa je bilo celo drevo uravnoteženo). Po vstavljanju torej z največ enim parom rotacij ponovno vzpostavimo uravnoteženost. Pri brisanju vozlišč pa nimamo take sreče in se ta neuravnoteženost lahko propagira proti korenu.\n",
    "\n",
    "<table>\n",
    "<tr>\n",
    "    <td><img alt=\"enojna rotacija - Wikipedija\" src=\"https://upload.wikimedia.org/wikipedia/commons/thumb/7/76/AVL-simple-left_K.svg/292px-AVL-simple-left_K.svg.png\" width=\"200px\"></td>\n",
    "    <td width=\"200px\"></td>\n",
    "    <td><img alt=\"dvojna rotacija - Wikipedija\" src=\"https://upload.wikimedia.org/wikipedia/commons/thumb/f/f9/AVL-double-rl_K.svg/302px-AVL-double-rl_K.svg.png\" width=250px\"></td>\n",
    "</tr>   \n",
    "</table>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "055f2e7f-e647-4dd2-a5e0-1b830c96171d",
   "metadata": {},
   "outputs": [],
   "source": [
    "class AVLNode {\n",
    "public:\n",
    "\tint value;\n",
    "\tAVLNode *left, *right;\n",
    "\tint height;\n",
    "\tAVLNode(int v) : value(v), left(NULL), right(NULL), height(1) { }\n",
    "};\n",
    "\n",
    "class AVLTree {\n",
    "public:\n",
    "\tAVLNode *root = NULL;\n",
    "\n",
    "\tint height() { return height(root); }\n",
    "\tint height(AVLNode* node) { return (node!=NULL)?node->height:0; }\n",
    "\tint balance(AVLNode* node) { return height(node->right) - height(node->left); }\n",
    "\tvoid update(AVLNode* node) { node->height = 1 + max(height(node->left), height(node->right)); }\n",
    "\n",
    "\tAVLNode* rotateLeft(AVLNode* node) {\n",
    "\t\tAVLNode *R=node->right;\n",
    "\t\tnode->right=R->left; R->left=node;\n",
    "\t\tupdate(node); update(R);\n",
    "\t\treturn R;\n",
    "\t}\n",
    "\n",
    "\tAVLNode* rotateRight(AVLNode* node) {\n",
    "\t\tAVLNode *L=node->left;\n",
    "\t\tnode->left=L->right; L->right=node;\n",
    "\t\tupdate(node); update(L);\n",
    "\t\treturn L;\n",
    "\t}\n",
    "\n",
    "\tbool contains(int x) { return contains(x, root); }\n",
    "\tbool contains(int x, AVLNode* node) {\n",
    "\t\tif (node==NULL) return false;\n",
    "\t\telse if (node->value==x) return true;\n",
    "\t\telse if (x < node->value) return contains(x, node->left);\n",
    "\t\telse return contains(x, node->right);\n",
    "\t}\n",
    "\n",
    "\tvoid insert(int x) { root = insert(x, root); }\n",
    "\tAVLNode* insert(int x, AVLNode* node) {\n",
    "\t\t// navadno vstavljanje\n",
    "\t\tif (node==NULL) { return new AVLNode(x); }\n",
    "\t\tif (x <= node->value) node->left = insert(x, node->left);\n",
    "\t\telse node->right = insert(x, node->right);\n",
    "\t\tupdate(node);\n",
    "\t\t// uravnotezi po potrebi\n",
    "\t\tint b=balance(node);\n",
    "\t\tif (b==2) {  // prevelik desni\n",
    "\t\t\tint bR=balance(node->right);\n",
    "\t\t\tif (bR==1 || bR==0) return rotateLeft(node);\n",
    "\t\t\telse { node->right=rotateRight(node->right); return rotateLeft(node); }\n",
    "\t\t} else if (b==-2) {  // prevelik levi\n",
    "\t\t\tint bL=balance(node->left);\n",
    "\t\t\tif (bL==-1 || bL==0) return rotateRight(node);\n",
    "\t\t\telse { node->left=rotateLeft(node->left); return rotateRight(node); }\n",
    "\t\t}\n",
    "\t\treturn node;\n",
    "\t}\n",
    "\n",
    "    // pomozna funkcija za preverjanje pravilnosti\n",
    "    bool check(AVLNode *node) {\n",
    "\t\tif (node==NULL) return true;\n",
    "        int b=balance(node);\n",
    "        if (b<-1 || 1<b) return false;\n",
    "        return check(node->left) && check(node->right);\n",
    "\t}\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b6e5252a-a432-4d51-9eb9-cd0bbfc8a2e5",
   "metadata": {},
   "source": [
    "Preverimo, da pri vstavljanju sedaj res nastane nizko uravnoteženo drevo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "4ff81129-d8e6-4150-a2f5-8b18eb255ded",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "17\n",
      "balanced\n"
     ]
    }
   ],
   "source": [
    "default_random_engine rnd(123);\n",
    "AVLTree avl;\n",
    "int n=100'000;\n",
    "for (int i=0;i<n;i++) {\n",
    "    avl.insert(i);\n",
    "    assert(avl.contains(i) && !avl.contains(i+1));\n",
    "}\n",
    "cout << avl.height() << endl;\n",
    "if (avl.check(avl.root)) cout << \"balanced\" << endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "16b1ea99-f50c-47cf-8831-d566dede8f5f",
   "metadata": {},
   "source": [
    "### Druga uravnotežena drevesa\n",
    "\n",
    "Obstajajo še številna druga uravnotežena drevesa, ki dosegajo uravnoteženost na različne načine in ponujajo logaritemsko časovno zahtevnost operacij. Na kratko predstavimo nekatera najbolj znana med njimi."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "19e561d1-e4d5-4cac-98a0-5538bf55e133",
   "metadata": {},
   "source": [
    "#### Rdeče-črno drevo (*red-black tree*) \n",
    "\n",
    "Uporablja barvanje vozlišč z rdečo in črno barvo v kombinaciji s pravili o barvah, ki zagotavljajo uravnoteženost drevesa: prazna vozlišča so črna, rdeče vozlišče nima rdečega otroka, poti od vsakega vozlišča do praznih potomcev vključujejo enako število črnih vozlišč. Te lastnosti implicirajo logaritemsko višino drevesa. Spremembe drevesa, ki imajo za posledico tudi spremembe barv, se lahko izvede v logaritemskem času. Novo vstavljeno vozlišče je najprej rdeče (da se ohranja lastnost z enakim številom črnih vozlišč na vseh poteh), čemur lahko sledi več popravkov v obliki rotacij in menjav barv.\n",
    "\n",
    "<img alt=\"Rdeče-črno drevo - Wikipedija\" src=\"https://upload.wikimedia.org/wikipedia/commons/4/41/Red-black_tree_example_with_NIL.svg\" width=\"400px\"/>\n",
    "<br>\n",
    "\n",
    "V zgornje rdeče-črno drevo lahko vstavimo število 16 precej enostavno - pustimo ga rdečega. Malo težje je vstavljanje števila 7, ki ne more biti rdeče, saj ima rdečega starša. Tega starša z levo rotacijo spravimo nivo višje, ga pobarvamo črno, otroka pa rdeče. Obstaja pa še precej kompleksnejših primerov, npr. kako bi vstavili 28? (Gre samo s spremembami barv vozlišč 8,17,22,25,27)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "28358736-b521-4fb8-87c7-fa395b5ee183",
   "metadata": {},
   "source": [
    "#### 2-3 drevo (*2-3 tree*) \n",
    "\n",
    "Uporablja različno velikost vozlišč za doseganje uravnoteženosti. Vsako vozlišče ima namreč dva ali tri otroke (in en ali dva ključa). Poleg tega se vsi listi nahajajo na enaki globini. Obstaja povezava med 2-3 drevesi in rdeče-črnimi drevesi.\n",
    "\n",
    "<img alt=\"2-3 drevo - Wikipedija\" src=\"https://upload.wikimedia.org/wikipedia/commons/4/44/2-3_insertion.svg\" width=\"600px\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b64c3b35-e72f-48a0-991a-ee2f41847a9b",
   "metadata": {},
   "source": [
    "#### B-drevo (*B-tree*) \n",
    "\n",
    "Gre za posplošitev 2-3 drevesa (B-drevo reda 3). V B-drevesu reda $m$ imajo vozlišča največ $m$ otrok, notranja vozlišča pa vsaj $m/2$. Vsi listi se nahajajo na enaki globini. Vozlišče z $o$ otroki torej hrani $o-1$ urejenih ključev, ki predstavljajo meje. Če je teh ključev znotraj vozlišča veliko, lahko po njih učinkovito iščemo z bisekcijo. Uporablja se v podatkovnih bazah, saj dostopa do večjih blokov podatkov hkrati in ne dela povsem naključnih dostopov v pomnilnik, ki niso tako učinkoviti (še posebej na diskih).\n",
    "\n",
    "<img alt=\"B-drevo reda 5 - Wikipedija\" src=\"https://upload.wikimedia.org/wikipedia/commons/6/65/B-tree.svg\" width=\"300px\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f815c3b3-4670-4075-b63f-7bc2284e1fd1",
   "metadata": {},
   "source": [
    "#### Lomljeno drevo (*splay tree*)\n",
    "\n",
    "Zagotavlja zgolj amortizirano logaritemsko časovno zahtevnost. Dostopane elemente namreč premika h korenu s pametno uporabo dvojnih rotacij in s tem tudi popravlja strukturo drevesa. Enojne rotacije s staršem namreč niso dovolj, ker ostane drevo zelo neuravnoteženo. Če smo potrebovali veliko časa za dostop do nekega vozlišča, se to v zaporedju operacij ne bo zgodilo večkrat, ker ga bomo po prvem dostopu premaknili bližje in pri tem malo uravnotežili drevo.\n",
    "\n",
    "<img alt=\"Lomljeno drevo - Loyola Marymount University\" src=\"https://cs.lmu.edu/~ray/images/splay.png\" width=\"400px\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "096c9462-998a-4bd2-8488-330a9ee2203d",
   "metadata": {},
   "source": [
    "#### Naključno uravnoteženo drevo (*treap*) \n",
    "\n",
    "Uporablja naključne prioritete vozlišč in vzdržuje iskalno drevo, ki je hkrati urejeno v kopico glede na prioriteto elementov. Vozlišče z največjo prioriteto torej postane koren drevesa. Vozlišča pa so po vrednostih še vedno urejena kot v iskalnem drevesu.  Zaradi naključnosti ponuja pričakovano logaritemsko časovno zahtevnost.\n",
    "\n",
    "<img alt=\"Naključno uravnoteženo drevo - Wikipedija\" src=\"https://upload.wikimedia.org/wikipedia/commons/4/4b/TreapAlphaKey.svg\" width=\"150px\"/>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}