Implementirali bomo AVL drevesa 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.

Podatkovni tip AVL drevo

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).

AVL drevo je:

  • bodisi prazno
  • bodisi vozlišče, sestavljeno iz:
    • vsebine (števila),
    • višine drevesa in
    • levega ter desnega AVL poddrevesa.

Naloga: definirajte podatkovni tip avltree, ki opisuje AVL drevesa.

Naloga: definirajte AVL drevo t:

    5
   / \
  3   8
 / \
1   4

Pametni konstruktor

Naloga: definirajte funkcijo height, ki vrne višino drevesa.

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:

# let six = leaf 6 ;;
val six : avltree = Node (6, 1, Empty, Empty)
# let seven = leaf 7 ;;
val seven : avltree = Node (7, 1, Empty, Empty)
# let answer = node (42, six, seven) ;;
val answer : avltree =
   Node (42, 2, Node (6, 1, Empty, Empty), Node (7, 1, Empty, Empty))

Naloga: s pametnimi konstruktorji definirajte AVL drevo, enako drevesu t iz prejšnje naloge.

Drevo ⇒ seznam

Naloga: definirajte funkcijo toList: avltree -> int list, ki elemente drevesa vrne kot urejen seznam števil. Za združevanje seznamov ima OCaml operator @.

Iskanje

Algoritem, ki ugotovi, ali je dani x v drevesu t:

  • če je t prazno drevo, se x ne pojavi;
  • če je t vozlišče z vsebino y in poddrevesoma l ter r:
    • če je x = y, se x pojavi;
    • če je x < y, iščemo v poddrevesu l;
    • če je x > y, iščemo v poddrevesu r.

Iskanje bomo implementirali s funkcijo search, ki naj deluje tako:

# search 5 t ;;
- : bool = true

Naloga zapišite tip funkcije search, ki ugotovi, ali drevo t vsebuje vrednost x.

Naloga definirajte funkcijo search. Za primerjanje dveh števil uporabite funkcijo cmp s predavanj, ki vrne vrednost tipa order:

type order = Less | Equal | Greater

let cmp x y =
  match compare x y with
  | 0 -> Equal
  | r when r < 0 -> Less
  | _ -> Greater

Naloga: preizkusite, ali search deluje.

Vrtenje in uravnoteženje

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.

Naloga: definirajte funkcijo imbalance: avltree -> int, ki vrne stopnjo neuravnoteženosti drevesa, tj. razliko med višinama levega in desnega poddrevesa.

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

     x                      y
   /   \       levo       /   \
  +     y       ==>      x     +
 /a\   / \              / \   /c\
 ---  +   +     <==    +   +  ---
     /b\ /c\   desno  /a\ /b\
     --- ---          --- ---

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.

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

        x
      /   \
     /     \
    y       +
   / \     / \
  /   \   / h \
 / h+2 \  -----
/       \
---------

Glede na višini poddreves vozlišča y lahko to drevo uravnotežimo z enim ali dvema vrtenjema. V prvem primeru imamo drevo oblike

         x                       y
       /   \                   /   \
      /     \                 /     \
     y       +               +        x
   /   \    /h\     ==>     / \     /   \
  +     +   ---            /h+1\   +     +
 / \   / \   c             -----  / \   /h\
/h+1\ /h+1\*                 a   /h+1\  ---
----- -----                      -----   c
  a     b (lahko ima višino h)     b

ki ga popravimo z enim vrtenjem v desno, kot je prikazano zgoraj.

V drugem primeru imamo drevo oblike

        x                       x                       z
      /   \                   /   \                   /   \
     /     \                 /     \                 /     \
    y       +               z       +               y       x
  /   \    /h\    ==>     /   \     /h\    ==>     / \     / \
 +     z   ---           y     +    ---           +   +   +   +
/h\   / \   c           / \   /h\    c           /h\ /h\ /h\ /h\
---  +   +             +   +  ---                --- --- --- ---
 a  /h\ /h\           /h\ /h\  b''                a   b'  b'' c
    --- ---           --- ---
     b'  b''           a   b'

(b' ali b'' lahko ima višino h-1)

ki ga popravimo tako, da najprej levo poddrevo (s korenom y) zavrtimo v levo, nato pa celotno drevo zavrtimo v desno.

Če je neuravnoteženost drevesa enaka -2, postopamo simetrično.

Naloga: definirajte funkcijo balance: avltree -> avltree, ki uravnoteži AVL drevo na podlagi opisanih primerov.

Vstavljanje

Nov element x vstavimo v AVL drevo t po naslednjem postopku:

  • če je drevo prazno, vrni list z vsebino x;
  • če je t vozlišče z vsebino y in poddrevesoma l ter r:
    • če je x = y, vrni t;
    • če je x < y, vstavi x v l in rezultat uravnoteži;
    • če je x > y, vstavi x v r in rezultat uravnoteži.

Naloga: definirajte funkcijo add: int -> avltree -> avltree.

Brisanje

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:

  • če je tprazno drevo, sproži izjemo;
  • če je t vozlišče z vsebino x in poddrevesoma l ter r:
    • če je l prazno drevo, vrni (r, x);
    • 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.

Naloga: definirajte funkcijo removeSuccessor: avltree -> avltree * int.

Element x lahko potem izbrišemo iz AVL drevesa t po naslednjem postopku:

  • če je t prazno drevo, vrni t;
  • če je t vozlišče z vsebino y in poddrevesoma l in r:
    • če je x < y, izbriši x iz levega poddrevesa l in rezultat uravnoteži;
    • če je x > y, izbriši x iz desnega poddrevesa r in rezultat uravnoteži;
    • če je x = y:
      • če je desno poddrevo prazno, vrni l;
      • če je levo poddrevo prazno, vrni r;
      • 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'.

Naloga: definirajte funkcijo remove: int -> avltree -> avltree.

Vir.

Zadnja sprememba: petek, 7. april 2023, 23.39