# Drzewa Lewicowe

Nov 22nd, 2020 (edited)
154
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. (*przechowujemy kolejno: lewego syna, prawego syna, wartość (priorytet), npl (null path length)*)
2. type 'a queue = Node of ('a queue)*('a queue)*('a)*int | Null;;
3.
4. (*funkcje pomocnicze*)
5. let npl q =
6.   match q with
7.   | Null -> -1
8.   | Node (Null,_,_,_) -> 0
9.   | Node (_,Null,_,_) -> 0
10.   | Node (_,_,_,a) -> a
11. ;;
12.
13. let empty = Null;;
14.
15. let rec join queue1 queue2 =
16.   match (queue1, queue2) with
17.   | (Null, Null) -> Null
18.   | (Null,_) -> queue2
19.   | (_,Null) -> queue1
20.   | (Node (lewy1,prawy1,wartosc1,npl1), Node (lewy2,prawy2,wartosc2,npl2)) ->
21.     if (wartosc1<=wartosc2) then
22.       let d = join prawy1 queue2 in
23.       if (npl lewy1)<=(npl d) then Node (d,lewy1,wartosc1,(npl lewy1)+1)
24.       else Node (lewy1,d,wartosc1,(npl d)+1)
25.     else join queue2 queue1
26. ;;
27.
28. let add e q = join (Node (Null,Null,e,0)) q;;
29.
30. let is_empty q =
31.   match q with
32.   | Null -> true
33.   | _ -> false
34. ;;
35.
36. exception Empty;;
37. let delete_min q =
38.   match q with
39.   | Null -> raise (Empty)
40.   | Node (lewy,prawy,wartosc,npl) -> (wartosc,(join lewy prawy))
41. ;;
RAW Paste Data