Science Booth

Konsep struktur data Tree telah dipelajari pada kuliah struktur data dan algoritma. Soal-soal pada latihan tutorial kali ini adalah soal-soal yang relatif pernah dikerjakan secara imperatif. Peserta diharapkan memahami bagaimana algoritma tree direpresentasi dalam pemrograman fungsional. Peserta juga diharapkan dapat membandingkan penyelesaian imperatif dengan fungsional pada setial soal yang diberikan. Tuliskan analisa perbandingan dalam komentar program. Analisa perbandingan dapat meliputi: kompleksitas running time dan alokasi memory, kemudahan pembuatan/perbaikan/modifikasi program, dan kemudahan membaca program. Gunakan sebisa mungkin higher order function pada setiap soal. Bila ada yang kurang jelas pada soal, silahkan tambahkan asumsi anda.

1. Buatlah sebuah fungsi bernama “soal1”. Fungsi tersebut menerima sebuah string, dan menghasilkan list of pair, yang tiap pairnya menyatakan karakter dan jumlah kemunculan karakter tersebut pada string input. Urutan pada pair output tidak penting.

soal1 :  string → (char * int) list

Contoh:

– soal1 “saya makan”

> val it = [(#”s”, 1), (#”a”,4), (#”y”,1), (#”m”,1), (#”k”,1), (#”n”,1)]

(Catatan: soal ini terkait dengan penerapan huffman code untuk kompresi,  harap melanjutkan lagi pengerjaannya hingga sampai encoding dan decoding, tidak perlu  dikumpulkan pada tutorial, tapi sebagai bagian persiapan ujian)

2. Buatlah sebuah fungsi bernama “soal2”. Fungsi tersebut membaca sebuah input dengan struktur data tree dan memeriksa apakah input tree tersebut merupakan binary search tree atau tidak. Struktur data tree didefinisikan dengan:

datatype bst = Leaf | Node of int * bst * bst

soal2 : bst → bool

Contoh:

– val t1 = Node(6, Node(4,Leaf,Leaf),
Node(15, Node(11,Leaf,Leaf), Node(24,Leaf,Leaf)));
– soal2 t1;
> val it = true : bool

3. Buatlah sebuah fungsi bernama “soal3” yang menerima satu argument tree. Fungsi ini akan mencetak isi tree yang diberikan secara inorder. (hint: gunakan perintah “print”);

soal3 : bst → unit

4. Buatlah sebuah fungsi bernama “soal4” yang memiliki dua argumen. Argumen pertama adalah sebuah list bilangan dan argumen kedua adalah sebuah tree. Fungsi ini akan memasukan argumen pertama kedalam tree satu persatu mulai dari elemen pertama pada list, dengan tetap mempertahankan struktur binary search tree namun tidak perlu balance.

soal4 : int list → bst → bst

5. Buatlah sebuah fungsi bernama “soal5”. Fungsi ini serupa dengan “soal4” namun dengan mengimplementasikan AVL Tree. Input tree yang diberikan bila bukan merupakan AVL Tree maka soal5 memberikan output berupa exception “Input bukan AVL Tree”. (hint: gunakan
“raise”)
soal5 : int → bst → bst

JAWABAN:

load "List";
load "Int";

datatype bst = Leaf | Node of int * bst * bst;

val tr = Node (4,
Node (2,
Node (1, Leaf, Leaf),
Node (3, Leaf, Leaf)
),
Node (6,
Node (5, Leaf, Leaf),
Node (7, Leaf, Leaf)
)
);

val ntr = Node (4,
Node (2,
Node (3, Leaf, Leaf),
Node (1, Leaf, Leaf)
),
Node (6,
Node (5, Leaf, Leaf),
Node (7, Leaf, Leaf)
)
);

val soal1 = let
fun calc [] = []
| calc (c::cs)= let
val next = List.filter (fn x => x <> c) cs
in (c,length cs - length next + 1) :: (calc next) end
in calc o explode end;

fun inorder Leaf = []
| inorder (Node (k,l,r)) = inorder l @ [k] @ inorder r;

val soal2 = let
fun sorted [] = true
| sorted [_] = true
| sorted (x1::x2::xs) = x1 <= x2 andalso sorted (x2::xs)
in sorted o inorder end;

val soal3 = (map (print o Int.toString)) o inorder

fun insert (k,Leaf) = Node (k, Leaf, Leaf)
| insert (k, Node (x,l,r))= if k < x
then Node (x, insert (k,l), r)
else Node (x, l, insert (k,r))

exception NotBST;
fun soal4 ls tree = if soal2 tree
then foldl insert tree ls;
else raise NotBST

fun rotateR Leaf = Leaf
| rotateR (Node (k,Leaf,r)) = Node (k,Leaf,r)
| rotateR (Node (k,Node (l,ll,lr),r)) = Node (l,ll,Node (k,lr,r));

fun rotateL Leaf = Leaf
| rotateL (Node (k,l,Leaf)) = Node (k,l,Leaf)
| rotateL (Node (k,l,(Node (r,rl,rr)))) = Node (r,Node (k,l,rl),rr);

fun height Leaf = 0
| height (Node (_,l,r)) = Int.max (height l, height r) + 1

fun balance Leaf = Leaf
| balance (Node (k,l,r)) = if height l > height r
then let
fun rotate' tree = case tree of Leaf => Leaf
| (Node (x,xl,xr)) => if height xr > height xl
then rotateL tree
else tree
val subtree = (k,rotate' l,r)
in rotateR (Node subtree) end
else let
fun rotate' tree = case tree of Leaf => Leaf
| (Node (x,xl,xr)) => if height xl > height xr
then rotateR tree
else tree
val subtree = (k,l,rotate' r)
in rotateL (Node subtree) end;

fun isBalanced Leaf = true
| isBalanced (Node (k,l,r)) = Int.abs (height l - height r) <= 1
andalso isBalanced l
andalso isBalanced r;

fun rebalance Leaf = Leaf
| rebalance (Node (k,l,r)) = let
val tree = Node (k,rebalance l, rebalance r)
in if isBalanced tree
then tree
else balance tree
end;

exception NotAVL;
fun soal5 k tree = if soal2 tree andalso isBalanced tree
then rebalance (insert (k,tree))
else raise NotAVL;

Tags: AVL tree, strukur data, Trees