{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "dried-accordance",
   "metadata": {},
   "source": [
    "# Vaje 6: Induktivni podatkovni tipi — AVL drevesa\n",
    "\n",
    "Implementirali bomo [AVL drevesa](https://en.wikipedia.org/wiki/AVL_tree) v jeziku OCaml. AVL drevo je dvojiško iskalno drevo, v katerem se za vsako vozlišče višini levega in desnega poddrevesa razlikujeta za največ 1.\n",
    "\n",
    "## Podatkovni tip AVL drevo\n",
    "\n",
    "V splošnem bi želeli v iskalnih drevesih hraniti poljubne podatke, ki jih lahko primerjamo po velikosti. Tu bomo nalogo poenostavili tako, da bomo v drevesih hranili le cela števila (`int`).\n",
    "\n",
    "AVL drevo je:\n",
    "\n",
    "* bodisi prazno\n",
    "* bodisi vozlišče, sestavljeno iz:\n",
    "    * vsebine (števila),\n",
    "    * višine drevesa in\n",
    "    * levega ter desnega AVL poddrevesa."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "wired-commerce",
   "metadata": {},
   "source": [
    "**Naloga:** definirajte podatkovni tip `avltree`, ki opisuje AVL drevesa."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "japanese-stable",
   "metadata": {},
   "outputs": [],
   "source": [
    "(* rešitev *)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "hybrid-stand",
   "metadata": {},
   "source": [
    "Spodnja funkcja `showTreeHorizontally : avltree -> unit` grafično prikaže vhodno drevo `t` po nivojih."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "relative-planner",
   "metadata": {},
   "outputs": [],
   "source": [
    "let showTreeHorizontally t = \n",
    "    let rec strign_of_avltree_level lvl = function \n",
    "        | Empty -> if lvl = 0 then \"nil\" else \"   \" \n",
    "        | Node (n, h, l, r) ->\n",
    "              let make_space = String.map (fun _ -> ' ') in\n",
    "              let sn = string_of_int n in\n",
    "              let sl = strign_of_avltree_level lvl l in\n",
    "              let sr = strign_of_avltree_level lvl r in\n",
    "                  if h = lvl\n",
    "                  then make_space sl ^ sn ^ make_space sr\n",
    "                  else sl ^ make_space sn ^ sr\n",
    "    in\n",
    "    let rec print_levels lvl =\n",
    "        if lvl >= 0\n",
    "        then (print_string (string_of_int lvl ^ \": \" ^ strign_of_avltree_level lvl t ^ \"\\n\");\n",
    "            print_levels (lvl-1))\n",
    "        else ()\n",
    "    in\n",
    "    let height = function\n",
    "        | Node (_, y, _, _) -> y\n",
    "        | Empty -> 0\n",
    "    in\n",
    "    print_levels (height t) ; flush stdout"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "brave-cisco",
   "metadata": {},
   "source": [
    "**Naloga:** definirajte AVL drevo `t`:\n",
    "\n",
    "        5\n",
    "       / \\\n",
    "      3   8\n",
    "     / \\\n",
    "    1   4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "incredible-rogers",
   "metadata": {},
   "outputs": [],
   "source": [
    "(* rešitev *)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "electronic-compiler",
   "metadata": {},
   "source": [
    "## Pametni konstruktor\n",
    "\n",
    "**Naloga:** definirajte funkcijo `height : avltree -> int`, ki vrne višino drevesa.\n",
    "Primera:\n",
    "    \n",
    "    # height Empty ;;\n",
    "    - : int = 0\n",
    "    # height t ;;\n",
    "    - : int = 3\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "engaging-north",
   "metadata": {},
   "outputs": [],
   "source": [
    "(* rešitev *)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "received-chick",
   "metadata": {},
   "source": [
    "**Naloga:** definirajte \"pametna\" konstruktorja `leaf: int -> avltree` in `node: int * avltree * avltree -> avltree`, ki sama poskrbita za višino. Prav vam bo prišla funkcija `max: int -> int -> int`, ki vrne večjega od dveh števil. Primer uporabe:\n",
    "\n",
    "    # let six = leaf 6 ;;\n",
    "    val six : avltree = Node (6, 1, Empty, Empty)\n",
    "    # let seven = leaf 7 ;;\n",
    "    val seven : avltree = Node (7, 1, Empty, Empty)\n",
    "    # let answer = node (42, six, seven) ;;\n",
    "    val answer : avltree =\n",
    "       Node (42, 2, Node (6, 1, Empty, Empty), Node (7, 1, Empty, Empty))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "wooden-tourist",
   "metadata": {},
   "outputs": [],
   "source": [
    "(* rešitev *)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "sharp-contamination",
   "metadata": {},
   "source": [
    "**Naloga:** s pametnimi konstruktorji definirajte AVL drevo, enako drevesu `t` iz prejšnje naloge."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "tight-anatomy",
   "metadata": {},
   "outputs": [],
   "source": [
    "(* rešitev *)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "convinced-humor",
   "metadata": {},
   "source": [
    "## Drevo ⇒ seznam\n",
    "\n",
    "**Naloga:** definirajte funkcijo `toList: avltree -> int list`, ki elemente drevesa vrne kot urejen seznam števil. Za združevanje seznamov ima OCaml operator `@`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "hybrid-species",
   "metadata": {},
   "outputs": [],
   "source": [
    "(* rešitev *)\n",
    "\n",
    "(* ena izmed neučinkovitih implementacij stikanja seznamov *)\n",
    "let rec join_list xs ys = match xs with\n",
    "    | [] -> ys\n",
    "    | glava :: rep -> glava :: join_list rep ys"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cosmetic-raising",
   "metadata": {},
   "source": [
    "## Iskanje\n",
    "\n",
    "Algoritem, ki ugotovi, ali je dani `x` v drevesu `t`:\n",
    "\n",
    "* če je `t` prazno drevo, se `x` ne pojavi;\n",
    "* če je `t` vozlišče z vsebino `y` in poddrevesoma `l` ter `r`:\n",
    "    * če je `x = y`, se `x` pojavi;\n",
    "    * če je `x < y`, iščemo v poddrevesu `l`;\n",
    "    * če je `x > y`, iščemo v poddrevesu `r`.\n",
    "\n",
    "Iskanje bomo implementirali s funkcijo `search`, ki naj deluje tako:\n",
    "\n",
    "    # search 5 t ;;\n",
    "    - : bool = true\n",
    "\n",
    "**Naloga** zapišite *tip* funkcije `search`, ki ugotovi, ali drevo `t` vsebuje vrednost `x`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "potential-external",
   "metadata": {},
   "outputs": [],
   "source": [
    "(* rešitev *)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "strong-portuguese",
   "metadata": {},
   "source": [
    "**Naloga** definirajte funkcijo `search`. Za primerjanje dveh števil uporabite funkcijo `cmp` s predavanj, ki vrne vrednost tipa `order`:   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "congressional-doctor",
   "metadata": {},
   "outputs": [],
   "source": [
    "type order = Less | Equal | Greater\n",
    "\n",
    "let cmp x y =\n",
    "    match compare x y with\n",
    "    | 0 -> Equal\n",
    "    | r when r < 0 -> Less\n",
    "    | _ -> Greater"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "constitutional-conference",
   "metadata": {},
   "outputs": [],
   "source": [
    "(* rešitev *)\n",
    "\n",
    "(* počasna rešitev *)\n",
    "let search_slow e t = List.mem e (toList t)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "detailed-agenda",
   "metadata": {},
   "source": [
    "**Naloga:** preizkusite, ali `search` deluje."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "varied-pitch",
   "metadata": {},
   "outputs": [],
   "source": [
    "(* rešitev *)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "incorrect-option",
   "metadata": {},
   "source": [
    "## Vrtenje in uravnoteženje\n",
    "\n",
    "Pri vstavljanju ali brisanju elementov se lahko AVL drevo \"pokvari\": višina levega in desnega poddrevesa nekega poddrevesa se razlikujeta za več kot 1. To popravimo z vrtenjem (rotacijo) drevesa okrog korena.\n",
    "\n",
    "**Naloga:** definirajte funkcijo `imbalance: avltree -> int`, ki vrne stopnjo neuravnoteženosti drevesa, tj. razliko med višinama levega in desnega poddrevesa.\n",
    "\n",
    "    # imbalance t ;;\n",
    "    - : int = 1\n",
    "    # imbalance Empty ;;\n",
    "    - : int = 0       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "moved-atlantic",
   "metadata": {},
   "outputs": [],
   "source": [
    "(* rešitev *)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "entitled-segment",
   "metadata": {},
   "source": [
    "V AVL drevesu je lahko neuravnoteženost kateregakoli vozlišča največ 1. Bolj neuravnotežena poddrevesa lahko popravimo z vrtenjem v levo oziroma desno. Vrtenje v levo oziroma desno ponazorimo z diagramom\n",
    "\n",
    "         x                      y\n",
    "       /   \\       levo       /   \\\n",
    "      +     y       ==>      x     +\n",
    "     /a\\   / \\              / \\   /c\\\n",
    "     ---  +   +     <==    +   +  ---\n",
    "         /b\\ /c\\   desno  /a\\ /b\\\n",
    "         --- ---          --- ---\n",
    "         \n",
    "**Naloga:** definirajte funkciji `rotateLeft` in `rotateRight`, ki dano drevo zavrtita na prikazan način. Če to ni mogoče (ker je drevo npr. prazno ali list), naj funkciji vrneta nespremenjeno drevo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "smoking-designation",
   "metadata": {},
   "outputs": [],
   "source": [
    "(* rešitev *)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "allied-discharge",
   "metadata": {},
   "source": [
    "Funkciji `rotateLeft` in `rotateRight` uporabimo za uravnoteženje drevesa. Ker bomo drevo uravnotežili po vsakem vstavljanju in brisanju elementa, lahko predpostavimo, da bo neuravnoteženost drevesa kvečjemu 2. Če je neuravnoteženost enaka 0, 1 ali -1, ni treba storiti ničesar. Sicer je neuravnoteženost 2 oziroma -2. V prvem primeru imamo drevo oblike\n",
    "\n",
    "            x\n",
    "          /   \\\n",
    "         /     \\\n",
    "        y       +\n",
    "       / \\     / \\\n",
    "      /   \\   / h \\\n",
    "     / h+2 \\  -----\n",
    "    /       \\\n",
    "    ---------\n",
    "\n",
    "Glede na višini poddreves vozlišča `y` lahko to drevo uravnotežimo z enim ali dvema vrtenjema. V prvem primeru imamo drevo oblike\n",
    "\n",
    "             x                       y\n",
    "           /   \\                   /   \\\n",
    "          /     \\                 /     \\\n",
    "         y       +               +        x\n",
    "       /   \\    /h\\     ==>     / \\     /   \\\n",
    "      +     +   ---            /h+1\\   +     +\n",
    "     / \\   / \\   c             -----  / \\   /h\\\n",
    "    /h+1\\ /h+1\\*                 a   /h+1\\  ---\n",
    "    ----- -----                      -----   c\n",
    "      a     b (lahko ima višino h)     b\n",
    "\n",
    "ki ga popravimo z enim vrtenjem v desno, kot je prikazano zgoraj.\n",
    "\n",
    "V drugem primeru imamo drevo oblike\n",
    "\n",
    "            x                       x                       z\n",
    "          /   \\                   /   \\                   /   \\\n",
    "         /     \\                 /     \\                 /     \\\n",
    "        y       +               z       +               y       x\n",
    "      /   \\    /h\\    ==>     /   \\     /h\\    ==>     / \\     / \\\n",
    "     +     z   ---           y     +    ---           +   +   +   +\n",
    "    /h\\   / \\   c           / \\   /h\\    c           /h\\ /h\\ /h\\ /h\\\n",
    "    ---  +   +             +   +  ---                --- --- --- ---\n",
    "     a  /h\\ /h\\           /h\\ /h\\  b''                a   b'  b'' c\n",
    "        --- ---           --- ---\n",
    "         b'  b''           a   b'\n",
    "     \n",
    "    (b' ali b'' lahko ima višino h-1)\n",
    "\n",
    "ki ga popravimo tako, da najprej levo poddrevo (s korenom `y`) zavrtimo v levo, nato pa celotno drevo zavrtimo v desno.\n",
    "\n",
    "Če je neuravnoteženost drevesa enaka -2, postopamo simetrično.\n",
    "\n",
    "**Naloga:** definirajte funkcijo `balance: avltree -> avltree`, ki uravnoteži AVL drevo na podlagi opisanih primerov."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "disciplinary-catalog",
   "metadata": {},
   "outputs": [],
   "source": [
    "(* rešitev *)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "revised-fever",
   "metadata": {},
   "source": [
    "## Vstavljanje\n",
    "\n",
    "Nov element `x` vstavimo v AVL drevo `t` po naslednjem postopku:\n",
    "\n",
    "* če je drevo prazno, vrni list z vsebino `x`;\n",
    "* če je `t` vozlišče z vsebino `y` in poddrevesoma `l` ter `r`:\n",
    "    * če je `x = y`, vrni `t`;\n",
    "    * če je `x < y`, vstavi `x` v `l` in rezultat uravnoteži;\n",
    "    * če je `x > y`, vstavi `x` v `r` in rezultat uravnoteži.\n",
    "\n",
    "**Naloga:** definirajte funkcijo `add: int -> avltree -> avltree`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "parental-scholarship",
   "metadata": {},
   "outputs": [],
   "source": [
    "(* rešitev *)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "angry-norfolk",
   "metadata": {},
   "source": [
    "## Brisanje\n",
    "\n",
    "Element `x` iz AVL drevesa izbrišemo tako, da ga zamenjamo z njegovim naslednikom iz poddrevesa v vozlišču `x`. Pri tem bomo uporabili pomožno funkcijo `removeSuccessor`, ki vrne novo drevo in naslednika, deluje pa tako:\n",
    "\n",
    "* če je `t`prazno drevo, sproži izjemo;\n",
    "* če je `t` vozlišče z vsebino `x` in poddrevesoma `l` ter `r`:\n",
    "    * če je `l` prazno drevo, vrni `(r, x)`;\n",
    "    * sicer izbriši naslednika iz `l`, da dobiš `(l', y)`, nato pa sestavi in uravnoteži novo drevo s korenom `x` ter poddrevesoma `l'` in `r`.\n",
    "\n",
    "**Naloga:** definirajte funkcijo `removeSuccessor: avltree -> avltree * int`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dedicated-avenue",
   "metadata": {},
   "outputs": [],
   "source": [
    "(* rešitev *)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "worldwide-detroit",
   "metadata": {},
   "source": [
    "Element `x` lahko potem izbrišemo iz AVL drevesa `t` po naslednjem postopku:\n",
    "\n",
    "* če je `t` prazno drevo, vrni `t`;\n",
    "* če je `t` vozlišče z vsebino `y` in poddrevesoma `l` in `r`:\n",
    "    * če je `x < y`, izbriši `x` iz levega poddrevesa `l` in rezultat uravnoteži;\n",
    "    * če je `x > y`, izbriši `x` iz desnega poddrevesa `r` in rezultat uravnoteži;\n",
    "    * če je `x = y`:\n",
    "        * če je desno poddrevo prazno, vrni `l`;\n",
    "        * če je levo poddrevo prazno, vrni `r`;\n",
    "        * sicer iz `r` izbriši naslednika, da dobiš `(r', y')`, nato pa sestavi in uravnoteži novo drevo s korenom `y'` ter poddrevesoma `l` in `r'`.\n",
    "        \n",
    "**Naloga:** definirajte funkcijo `remove: int -> avltree -> avltree`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "understanding-width",
   "metadata": {},
   "outputs": [],
   "source": [
    "(* rešitev *)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "minimal-claim",
   "metadata": {},
   "outputs": [],
   "source": [
    "(* testi *)\n",
    "let tr = Empty;;\n",
    "let _ = showTreeHorizontally tr;;\n",
    "\n",
    "let tr = add 1 tr;;\n",
    "let test1 = tr = Node (1, 1, Empty, Empty) ;;\n",
    "let _ = showTreeHorizontally tr;;\n",
    "\n",
    "\n",
    "let tr = add 2 tr;;\n",
    "let test2 = tr = Node (1, 2, Empty, Node (2, 1, Empty, Empty))\n",
    "let _ = showTreeHorizontally tr;;\n",
    "\n",
    "let tr = add 3 tr;;\n",
    "let test3 = tr = Node (2, 2, Node (1, 1, Empty, Empty), Node (3, 1, Empty, Empty))\n",
    "let _ = showTreeHorizontally tr;;\n",
    "\n",
    "let tr = add 4 tr;;\n",
    "let test4 = tr = Node (2, 3, Node (1, 1, Empty, Empty),\n",
    "   Node (3, 2, Empty, Node (4, 1, Empty, Empty)))\n",
    "let _ = showTreeHorizontally tr;;\n",
    "\n",
    "let tr = add 5 tr;;\n",
    "let test5 = tr = Node (2, 3, Node (1, 1, Empty, Empty),\n",
    "   Node (4, 2, Node (3, 1, Empty, Empty), Node (5, 1, Empty, Empty)))\n",
    "let _ = showTreeHorizontally tr;;\n",
    "\n",
    "let tr = add 6 tr;;\n",
    "let test6 = tr =  Node (4, 3,\n",
    "   Node (2, 2, Node (1, 1, Empty, Empty), Node (3, 1, Empty, Empty)),\n",
    "   Node (5, 2, Empty, Node (6, 1, Empty, Empty)))\n",
    "let _ = showTreeHorizontally tr;;\n",
    "\n",
    "let tr = add 7 tr;;\n",
    "let test7 = tr = Node (4, 3,\n",
    "   Node (2, 2, Node (1, 1, Empty, Empty), Node (3, 1, Empty, Empty)),\n",
    "   Node (6, 2, Node (5, 1, Empty, Empty), Node (7, 1, Empty, Empty)))\n",
    "let _ = showTreeHorizontally tr;;\n",
    "\n",
    "\n",
    "let tr = remove 1 tr;;\n",
    "let test_remove1 = tr = Node (4, 3, Node (2, 2, Empty, Node (3, 1, Empty, Empty)),\n",
    "   Node (6, 2, Node (5, 1, Empty, Empty), Node (7, 1, Empty, Empty)))\n",
    "let _ = showTreeHorizontally tr;;\n",
    "\n",
    "let tr = remove 2 tr;;\n",
    "let test_remove1 = tr = Node (4, 3, Node (3, 1, Empty, Empty),\n",
    "   Node (6, 2, Node (5, 1, Empty, Empty), Node (7, 1, Empty, Empty)))\n",
    "let _ = showTreeHorizontally tr;;\n",
    "\n",
    "let tr = remove 3 tr;;\n",
    "let test_remove1 = tr = Node (6, 3, Node (4, 2, Empty, Node (5, 1, Empty, Empty)),\n",
    "   Node (7, 1, Empty, Empty))\n",
    "let _ = showTreeHorizontally tr;;\n",
    "\n",
    "let tr = remove 4 tr;;\n",
    "let test_remove1 = tr = Node (6, 2, Node (5, 1, Empty, Empty), Node (7, 1, Empty, Empty))\n",
    "let _ = showTreeHorizontally tr;;\n",
    "\n",
    "let tr = remove 5 tr;;\n",
    "let test_remove1 = tr = Node (6, 2, Empty, Node (7, 1, Empty, Empty))\n",
    "let _ = showTreeHorizontally tr;;\n",
    "\n",
    "let tr = remove 6 tr;;\n",
    "let test_remove1 = tr = Node (7, 1, Empty, Empty)\n",
    "let _ = showTreeHorizontally tr;;\n",
    "\n",
    "let tr = remove 7 tr;;\n",
    "let test_remove1 = tr = Empty\n",
    "let _ = showTreeHorizontally tr;;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "awful-federation",
   "metadata": {},
   "source": [
    "[Vir](https://www.cs.cornell.edu/courses/cs312/2007fa/lectures/lec14.html)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "OCaml default",
   "language": "OCaml",
   "name": "ocaml-jupyter"
  },
  "language_info": {
   "codemirror_mode": "text/x-ocaml",
   "file_extension": ".ml",
   "mimetype": "text/x-ocaml",
   "name": "OCaml",
   "nbconverter_exporter": null,
   "pygments_lexer": "OCaml",
   "version": "4.08.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}