// autor: Pawel Schmidt // Na tej liscie zajmiemy sie binarnymi drzewami poszukiwan (BST) // Drzewo BST, definiujemy nastepujaco: type Tree = | Leaf // lisc drzewa (puste drzewo, nie ma zadnych wartoci) | Node of Tree * int * Tree // wezel skladajacy sie z dwoch drzew oraz wartosci typu int // puste drzewo let empty = Leaf // drzewo zawierajace jeden element - liczbe 5 let oneElemTree = Node(Leaf, 5, Leaf) // drzewo dwuelementowe let twoElemsTree = Node(Leaf, 33, Node(Leaf, 993, Leaf)) // drzewo zawierajace trzy elementy, 5, 10 oraz 12 // (5) 10 (12) let threeElems = Node( Node(Leaf, 5, Leaf), 10, Node(Leaf, 12, Leaf) ) // Funkcja wypisujaca drzewo (obroc glowe o 90 stopni w lewo) let print (tree:Tree) : unit = let rec print2 (pref:string) (tree:Tree) : unit = match tree with | Leaf -> printfn "%s|" pref | Node (left, x, right) -> let spref = " " + pref print2 spref right printfn "%s%O" pref x print2 spref left print2 "" tree // Kolejnosc elementow w tym przykladzie nie jest przypadkowa. // Chcemy, zeby dla kazdego wezla Node(left, x, right) drzewa, // wartosc x byla wieksza od wszystkich wartosci w poddrzewie left // wartosc x byla mniejsza od wszystkich wartosci w poddrzewie right // Zakladamy tutaj, ze w drzewie nie wystepuja powtorzenia (dla uproszczenia) // Ponizsza funkcja oblicza liczbe elementow w drzewie: let rec count (tree:Tree) = match tree with | Leaf -> 0 // lisc (puste drzewo) ma 0 elementow | Node(left, x, right) -> // dla wezla o poddrzewach left i right let leftCnt = count left // oblicz ile elementow ma lewe poddrzewo let rightCnt = count right // oblicz ile elementow ma prawe poddrzewo 1 + leftCnt + rightCnt // dodaj elementy lewego i prawego poddrzewa oraz nie zapomnij o policzeniu elementu x let cntTest = count threeElems = 3 // Zadanie 1: // zdefiniuj funkcje depth, ktora obliczy glebokosc drzewa // tj. maksymalna odleglosc od korzenia do liscia let rec depth (tree:Tree) = failwith "Usun ten wiersz" // Zadanie 2: // Zdefiniuj funkcje find, ktora dla drzewa oraz pewnego elementu, sprawdzi, czy wystepuje on w drzewie // Wskazowka: porzadek BST mowi, gdzie powinnismy szukac elementu let rec find (tree:Tree) (elem:int) : bool = failwith "Usun ten wiersz" // find threeElems 5 = true // find threeElems 123433 = false // Zadanie 3: // zdefiniuj funkcje, ktora wstawi element elem do drzewa tree zachowujac porzadek BST // Wskazowka: // Jak wyglada wstawienie elementu do pustego drzewa? // Jesli drzewo jest niepuste, porownaj element przechowywany w wezle z tym, ktory wstawiamy let rec insert (tree:Tree) (elem:int) : Tree = failwith "Usun ten wiersz" // Zadanie 4: // Zdefiniuj funkcje flatten, ktora splaszczy drzewo do listy, // tzn stworzy liste wszystkich elementow drzewa zachowujac ich porzadek // na przyklad // flatten threeElems = [5; 10; 12] let rec flatten (tree:Tree) : int list = failwith "Usun ten wiersz" // Zadanie dodatkowe: // Powyzsza funkcja flatten tworzy liste dla lewego poddrzewa a nastepnie dokleja ja do prawej lisrty // Powoduje to dwa problemy: // 1. Lista dla lewego poddrzewa jest wyrzucana do smieci (dotyczy to kazdego lewego poddrzewa calego drzewa!) // 2. Czas dzialania appenda jest proporcjonalny do dlugosci lewej listy, wiec // caly flatten moze dzialac w czasie kwadratowym. // W tym zadaniu chcemy pozbyc sie obu problemow. // Zdefniuj funkcje flattenAppend, ktora przyjmie jako argument drzewo oraz liste, // a nastepnie zwroci liste wszystkich elementow drzewa doklejonych do listy // Wskazowka: najpierw doklej elementy prawego drzewa, a dopiero potem lewego let rec flattenAppend (tree:Tree) (lst:int list) = failwith "Usun ten wiersz" // Wykorzystaj funkcje flattenAppend do zdefiniowania funkcji flatten2, ktora splaszcza drzewo do listy let flatten2 tree = failwith "Usun ten wiersz" // Drzewo, dla ktorego flatten2 dziala istotnie szybciej niz flatten. // Wynik wlozenia odwrotnie posortowanego ciagu do drzewa. // Tutaj tworzone jest recznie, bo wszystkie inserty dzialalaby zbyt wolno. let comb = List.fold (fun s e -> Node(s, e, Leaf)) Leaf [1..20000] // Jesli poprawnie zdefiniowales wstawianie elemetu oraz splaszczanie // ponizsza funkcja powinna sortowac dowolna liste // Kazdy element jest wstawiony do poczatkowo pustego drzewa, a nastepnie otrzymane drzewo // jest splaszczane do listy let treeSort (lst : int list) = let tree = List.fold insert Leaf lst flatten tree // Zadanie 5: // Zdefiniuj pare funkcji rotateRight i rotateLeft, ktore obroca drzewo w prawo i lewo // https://upload.wikimedia.org/wikipedia/commons/2/23/Tree_rotation.png let rotateRight (tree:Tree) : Tree = failwith "Usun ten wiersz" // rotateRight threeElems = Node (Leaf, 5, Node (Leaf,10,Node (Leaf,12,Leaf))) let rotateLeft (tree:Tree) : Tree = failwith "Usun ten wiersz" // rotateLeft Node (Leaf, 5, Node (Leaf,10,Node (Leaf,12,Leaf))) = threeElems // Zadanie 5: // Zdefiniuj funkcje moveToRoot, ktora uzywajac rotacji przeniesie wskazany element do korzenia // Jesli elementu nie ma w drzewie, wynik nie musi byc taki sam jak poczatkowe drzewo let rec moveToRoot (tree: Tree) (elem:int) : Tree = failwith "Usun ten wiersz" // Zadanie 6: // Wykorzystaj funkcje moveToRoot do podzielenia drzewa na dwa poddrzewa, // w jednym sa elementy mniejsze, a w drugim wieksze od wskazanego elementu let split (tree:Tree) (elem:int) : Tree * Tree = failwith "Usun ten wiersz" // Zadanie 7: // Zdefiniuj funkcje removeRoot, ktora usunie korzen z drzewa // Wskazowka: // Jesli elem w drzewie ma tylko jednego syna (poddrzewo left lub right jest puste) // to umiemy prosto usunac elem z drzewa // Jesli elem w drzewie ma oba poddrzewa niepuste, mozemy obrocic drzewo spychacjac elem w strone lisci let rec removeRoot (tree:Tree) : Tree = failwith "Usun ten wiersz" // Zadanie 8: // Zdefiniuj funkcje, ktora usunie wskazany element z drzewa wykorzystujac funkcje removeRoot let rec remove (tree:Tree) (elem:int) : Tree = failwith "Usun ten wiersz"