Binary Tree

Assalamualaikum wr.wb

Hy eman- teman kali ini saya akan membahas tentang “TREE”.

Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hierarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan elemen khusus yang disebut Root. 

Untuk jelasnya, di bawah akan diuraikan istilah-istilah umum dalam Tree :

a) Prodecessor              : node yang berada diatas node tertentu.

      b) Successor                 : node yang berada di bawah node tertentu.

c) Ancestor                   : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur

                                                                yang sama

d) Descendant              : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur

                                                                           yang sama.

e) Parent                      : predecssor satu level di atas suatu node.

f) Child                        : successor satu level di bawah suatu node.

g) Sibling                     : node-node yang memiliki parent yang sama dengan suatu node.

h) Subtree                    : bagian dari tree yang berupa suatu node beserta descendantnya

 dan memiliki semua karakteristik dari tree tersebut.

i) Size                          : banyaknya node dalam suatu tree.

j) Height                      : banyaknya tingkatan/level dalam suatu tree.

k) Root                        : satu-satunya node khusus dalam tree yang tak punya predecssor.

l) Leaf                         : node-node dalam tree yang tak memiliki seccessor.

m) Degree                   : banyaknya child yang dimiliki suatu node.

Jenis- jenis  Tree

1.      Binary Tree

Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah.

-          Representasi Binary Tree Pada Array

·         Index dari Array mempresentasikan atau menunjukkan nomor node.

·         Index ke-0 merupakan root.

·         Index dari Left Child  adalah 2p + 1, dimana p = index dari parent

·         Index dari Right Child adalah 2p + 2, dimana p = indekx dari parent

·         Index dari Parent adalah (p-1)/2

Catatan : Lihat arah tanda panah jika ke kanan rumusnya adalah (2p + 2) dan jika ke kiri (2p + 1)

Cara Penyelesaian :

                                    B = 2p + 1

                                        = 2(0) + 1 = 1

                                    C = 2p + 2

                                        = 2(0) + 2 = 2

                                    D = 2p + 1

                                        = 2(1) + 1 = 3

                                    E = 2p + 1

                                       = 2(2) + 1 = 5

                                    F = 2p + 2

                                       = 2(2) + 2 = 6

                                    G = 2p + 1

                                        = 2(3) + 1 = 7

                                    H = 2p + 1

                                        = 2(5) + 1 = 11

                                    I = 2p + 2

                                       = 2(5) + 2 = 12

                                    J = 2p + 2

                                       = 2(6) + 2 = 14

                                    K = 2p + 2

                                        = 2(11) + 2 = 24  

                        9 = 2p+1

                              2(0) + 1 = 1

                       

                        88 = 2p+2

                             = 2(0) + 2 =2

8 = 2p + 1

                            = 2(1) + 1 = 3

                        10 = 2p + 2

                            = 2(01 + 2 = 4

                        51 = 2p + 1

                            = 2(2) + 1 = 5

                        89 = 2p + 2

                            = 2(2) + 2 = 6

                        2 = 2p + 1

                           = 2(3) + 1 = 7

                        15 = 2p + 2

     = 2(4) + 2 = 10

                        22  = 2p + 1

                             = 2(5) + 1 = 11 

Demikian yg dapat saya jelaskan semoga bermanfaat Wassalamualaikum wr.wbJ  

Graph Berarah dan Tidak Berarah

Assalamualaikum wr.wb 

Hai teman-teman, kali ini saya akan membahas tentang GRAPH. Apa sih Graph itu ? .

GRAPH adalah kumpulan dari simpul dan busur yang secara matematis dinyatakan sebagai :

G = (V, E). Graf juga didefinisikan sebagai himpunan benda-benda yang disebut verteks (node) yang terhubung oleh sisi (atau edge ata u arc). Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan verteks) yang dihubungkan oleh garis-garis (melambangkan sisi).

Dimana

            G = Graph

            V = Simpul atau Vertex , atau Node, atau Titik

            E = Busur atau Edge , atau Arc

Graph dibagi menjadi dua yaitu :

DIREKTED (Berarah)

Urutan pasangan simpul disini sangat diperhatikan karena dapat menyatakan hal yang berbeda. Urutan simpul mempunyai arti. Misal busur RI adalah e1 sedangkan busur IR adalah e8.

Keterangan Simpul atau Node:

                      R = v1            

                      I   = v2

                      D  = v3

                      H  = v4

                      O = v5

            Keterangan Busur :

                      R1  = e1

                      IR  = e8

                      RO = e2

                      OH = e6

                      OD = e5

                      DH = e7

                      ID  =  e3

                      IH  =  e4

                      DI  = e9

                      DO = e10

           

UNDIREKTED (Tidak Berarah )

Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak berarah. Pada graf tak-berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. Urutan simpul dalam sebuah busur tidak dipentingkan. Misal busur e1 dapat disebut busur MU atau UM.

Keterangan Busur : Busur e1 dapat disebut Busur  MU atau UM

                                Busur e2 dapat disebut Busur  MA atau AM

                                Busur e3 dapat disebut Busur  UN atau NU

                                Busur e4 dapat disebut Busur  UF atau FU

                                Busur e5 dapat disebut Busur  AN atau NA
                                Busur e6 dapat disebut Busur  AF atau FA

                                Busur e7 dapat disebut Busur  NF atau FN      

Secara umum terdapat dua macam representasi dari struktur data graf yang dapat diimplementasi. 

- Pertama, disebut Adjacency List( diimplementasi dengan menampilkan masing-masing simpul sebagai sebuah struktur data yang mengandung semua simpul yang saling berhubungan). 

- Kedua adalah representasi berupa Adjacency Matrix dimana baris dan kolom dari matriks (jika dalam konteks implementasi berupa senarai dua dimensi) tersebut merepresentasikan simpul awal dan simpul tujuan dan sebuah entri di dalam  menyatakan apakah terdapat sisi di antara kedua simpul tersebut.

* Adjacency List

Dalam teori graf, adjacency list merupakan bentuk representasi dari seluruh sisi atau busur dalam suatu graf sebagai suatu senarai. Simpul-simpul yang dihubungkan sisi atau busur tersebut dinyatakan sebagai simpul yang saling terkait. Dalam implementasinya, hash table digunakan untuk menghubungkan sebuah simpul dengan senarai berisi simpul-simpul yang saling terkait tersebut..

Graf pada gambar diatas dapat dideskripsikan sebagai senarai {a,b},{a,c},{b,c}. Dan representasi adjacency list dapat digambarkan melalui tabel di bawah ini.

Tabel 1. Representasi Adjacency List 

Vertex	Adjacency	Array of Adjacent
A	Adjacent to	B,c
B	Adjacent to	A,c
C	Adjacent to	A,b

Salah satu kekurangan dari teknik representasi ini adalah tidak adanya tempat untuk menyimpan nilai yang melekat pada sisi. Contoh nilai ini antara lain berupa jarak simpul, atau beban simpul.

Adjacency Matrix
Adjacency Matrix merupakan representasi matriks yang menyatakan hubungan antar simpul dalam suatu graf. Kolom dan baris dari matriks ini merepresentasikan simpul-simpul, dan nilai entri dalam matriks ini menyatakan hubungan antar simpul.

Gambar diatas merupakan adjacency matrix yang berkorelasi dengan graf tak berarah. Kolom dan baris pada matriks merupakan simpul- simpul berlabel 1-6. Kelebihan dari adjacency matrix ini adalah elemen matriksnya dapat diakses langsung melalui indeks, dengan begitu hubungan ketetanggan antara kedua simpul dapat ditentukan dengan langsung. Sedangkan kekurangan pada representasi ini adalah bila graf memiliki jumlah sisi atau busur yang relative sedikit.

Sekian penjelasan dari saya , mohon maaf jika ada kesalahan J .Wassalamualaikum wr.wb

Stack dan Queue

Assalamualaikum wr.wb

Kali ini saya akan membahas tentang Stack dan Queue.

v  Stack (tumpukan)

 kumpulan elemen-elemen data yang disimpan dalam satu lajur linier, merubah bilangan decimal ke bilangan oktal .Kumpulan elemen data hanya boleh diakses pada satu lokasi saja yaitu posisi atas (TOP) tumpukan. Tumpukan digunakan dalam algoritma pengimbas (parsing), algoritma penilaian (evaluation) dan algoritma penjajahan balik (backtrack). Konsep utamanya adalah “LIFO” yaitu LAST IN FIRST OUT artinya eleme yg terakhir masuk akan pertama dikeluarkan dari tumpukan (stack).

Operasi yang diterapkan Stack sebagai berikut :

1.      Push   : digunakan untuk menambah item pada stack tumpukan paling Atas.

2.      Stack :  record

3.      Isi      : array [1….n] of tipe data

4.      Atas  : integer

5.      Pop    : digunakan untuk mengambil item pada stack pada tumpukan paling Atas.

6.      Clear  : digunakan untuk mengosongkan stack.

7.      Create Stack : membuat tumpukan baru dengan jumlah elemen kosong.

Contoh  : hasil 11

2

5

2

2

2

1

Langkah pertama

 11/2 = 5 sisa 1

 5/2  = 2 sisa 1

 2/2  = 1 sisa 0

1

0

1

1

                       

               

Angka 1 yang paling atas disebut Top  dan angka 1 yg terakhir disebut bottom.

Hasil awal di letakkan di akhir tumpukan dan yang pertama dikeluarkan adalah yang tumpukan teratas

Contoh 2 : 21010  : X8

                   210 / 8          hasil  26           sisa 2¹

                   26 / 8            hasil 3³              sisa 2²

Push

3

2

2

Pop (keluaran) 3,2,2

Jadi bilangan oktalnya adalah 3 2 2 .

Sebelumnya sudah tahu apa itu palindrome?.
Palindrome adalah suatu kata atau kalimat yang bisa dibaca baik dari depan maupun belakang dengan bunyi yang sama. Misal :
– Malam
– Katak
– Macam
–Kakak

Kalimat tersebut di atas jika dibaca dari depan maupun belakang akan memiliki urutan huruf yang sama.
Hubungan palindrome dengan Stack kali ini adalah saya akan menulis sebuah kode program yang digunakan untuk mengecek apakah sebuah kata atau kalimat merupakan palindrome atau bukan dengan bantuan Stack.

<html>
<head>
    <title>Struktur Data Stack</title>
    <script language ="JavaScript">
        var stack = new Array();
        var hasil = 0;
      
function testarr() {
  this.stack = new Array();

  this.Push = function(obj) {
    this.stack[this.stack.length] = obj;
  }

  this.Pop = function() {
    if (this.stack.length > 0) {
      var obj = this.stack[this.stack.length - 1];
      this.stack.splice(this.stack.length - 1, 1);
      return obj;
    } else {
      alert("");

    }
  }
}

function palindrome(data) {
  var mystack = new testarr();
  var text1;
  var text2 = "";
  var i;
  var t;
  text1 = data;
  i = text1.length;
  t = text1.length;

  do {
    mystack.Push(text1.substr(t - i, 1));
    i--;
  } while (i > 0);

  do {
    text2 += mystack.Pop();
    t--
  } while (t > 0);
  if (text1 === text2) {
    document.getElementById("txtCEK").innerHTML = "ini Palindrome";
   
  } else {
    document.getElementById("txtCEK").innerHTML = "ini Tidak Palindrome";
    PushData(text1);
  }

}
        function PushData(data)
        {
            stack.push(data);
        }
      
        function PopData()
        {
            var data_dari_stack = stack.pop();
            if(data_dari_stack == undefined)
                return "Stack Sudah Kosong";
            else
                return data_dari_stack;
        }
      
        function TampilkanStack(list)
        {
            list.options.length = 0;
            for(var i=0; i<stack.length; i++)
            {
                var data = new Option(stack[i]);
                list.options[list.options.length] = data;
            }
            PeekData();
            document.getElementById("txtBanyak").innerHTML = stack.length;
        }
      
        function HapusData()
        {
            stack = [];
        }
      
        function PeekData()
        {
            var hasil = stack.length;
            if(hasil == 0 || hasil == undefined)
                document.getElementById("txtAtas").innerHTML = "Kosong";
            else
                document.getElementById("txtAtas").innerHTML = stack[hasil - 1];
        }
    </script>
</head>
<body>
    <form>
        <p><input type=text name=textSimpan>
        <input type=button value="Masukkan ke Stack"
            onClick='palindrome(textSimpan.value);textSimpan.value="";
        TampilkanStack(mediaList);'></p>
        <p>Data di dalam stack:<br/>
        <select name="mediaList" size="12">
            <option>Tampilan data.....
        </select></p>
        <p><input type=text name=textAmbil size=20>
        <input type=button value="Ambil dari Stack" onClick="textAmbil.value = PopData();
            TampilkanStack(mediaList);">
        <input type=button value="Hapus Data" onClick="HapusData();
            TampilkanStack(mediaList);"><br>
        <label>Palindrome Data:</label><label id="txtCEK"></label><br>
        <label>Banyak Data:</label><label id="txtBanyak"></label><br>
        <label>Data Terakhir:</label><label id="txtAtas"></label></p>
    </form>
</body>
</html>

Maka akan Tampil seperti ini

Data di dalam stack:
Tampilan data.....

Palindrome Data:
Banyak Data:
Data Terakhir:

v  Queue (antrian)

Konsepnya hampir sama dengan Stack , perbedaannya adalah operasi penambahan dan penghapusan pada ujung yang berbeda . Penghapusan dilakukan pada bagian depan(front) dan penambahan berlaku pada bagian belakang (rear).

Contoh : 1 2 3 4 5

                  1 = depan

                  5 = belakang

Antrian dengan larik

1

2

3

4

5

                     0          1          2         3         4

    

      1= depan

      5= belakang

Contoh Programnya : 
<html>
<head>
    <title>Queue Tugas 5</title>

<style>

header {
height: 100px;
background-color: grey;
text-align: center;
}

body {
background-color: aqua;
}


</style>
    </head>
        <script type="text/javascript">
            var queue = new Array();
            var ganjil = new Array()
            var genap = new Array();
            var x=0;
            var y=0;
                function td()
                    {
                        for (var i = 0 ;i<20;i++)
                            {
                                queue[i] = Math.floor(Math.random()*(50-1))+1;
                                document.getElementById("hasil").innerHTML +=queue[i]+"<br>";
                            }
                    }

            function dequeue()
                {
                    var dambil = queue.pop();
                    if(dambil==undefined)
                    {
                        return "queue udah habis"
                    }
                    else
                    {
                        hasil = dambil%2;
                        if(hasil==0)
                        {
                            genap.push(dambil);
                            document.getElementById("gen").innerHTML += dambil+"<br>";
                            x++;
                            return dambil;
                        }
                        else
                        {
                            ganjil.push(dambil);
                            document.getElementById("gan").innerHTML += dambil+"<br>";
                            x++;
                            return dambil;
                        }
                    }
                }

            function jum()
                {
                    if(ganjil[y]==undefined)
                    {
                        a = genap[y]+0;
                        y++;
                        document.getElementById("has").innerHTML += a+"<br>";
                    }
                    else if(genap[y]==undefined)
                    {
                        b = ganjil[y]+0;
                        y++;
                        document.getElementById("has").innerHTML += b+"<br>";
                    }
                    else
                    {
                        c=ganjil[y]+genap[y];
                        y++;
                        document.getElementById("has").innerHTML +=c+"<br>";
                    }
                }

        </script>
<body>
<header>
    <h1 align="center">Queue Random</h1>
</header>  
<label id="hasil"></label><br>
<input type="button" value="Queue Random" onclick="td()"><br>
<input type="text" id="simpan"></td>
<input type="button" value="Scan Queue" onClick="simpan.value=dequeue()"><br>
<label>Genap :</label>
<label id="gen"></label>
<label>Ganjil :</label>
<label id="gan"></label>
<input type="button" value="Jumlahkan" onclick="jum()"><br>
<label>Hasil :</label><br>
<label id="has"></label><br>
</body>
</html>

Maka akan tampil seperti dibawah ini :

Queue Random

Genap : Ganjil :
Hasil :

itulah penjelasan yang saya sampaikan ,semoga bermanfaat 😊, Wassalamualaikum wr.wb