Makalah Struktur Data Pohon Biner dalam Pemprograman Phyton

Baca Juga

Slamat sore sahabat blogger.. 😊😊😊😊😊jumpa lagi dengan sayaa.. sore ini saya akan membagikan kepada teman-teman artikel yang membahas tentang struktur data Pohon byner dalam Pemprogrman phyton... 

BAB I

PENDAHULUAN  

     A.    Latar Belakang

Salah satu penerapan teori pohon yang paling berguna dan dipakai yaitu konsep binary search tree dimana konsep ini memberikan struktur data yang memudahkan operasi pencarian, penambahan, dan penghapusan terhadap data. Operasi tersebut lebih efisien dan jauh lebih baik pada konsep ini dibanding sequential search pada senarai berkait dalam waktu eksekusi / run-time.

Dari konsep binary search tree ini dikembangkan lagi suatu struktur penyimpanan data yang merupakan modifikasi dari binary search tree tersebut yaitu AVL-Tree dan Splay Tree yang masing-masing mempunyai keunggulan pada kasus tertentu yang sekarang ini sering dijumpai.

AVL-Tree merupakan modifikasi binary search tree yang tinggi setiap upapohon kiri dan upapohon kanan sama atau setidaknya selisih antara keduanya tidak lebih dari 1. Keunggulan dari AVL-Tree antara lain untuk mengoptimasi pencarian data terutama untuk kasus pohon yang condong ke kiri atau ke kanan sehingga pencarian akan jauh lebih mudah apabila pohon tersebut seimbang. Kasus pohon yang condong ke kiri atau kanan itu mungkin saja terjadi terutama apabila penambahan elemen dan penghapusan elemen dilakukan terus-menerus dan tidak dapat diketahui urutannya.

Sedangkan Splay-Tree justru kebalikan dari AVL-Tree yang tidak mempermasalahkan kecondongan upapohonnya namun setiap kali data diakses maka simpul dari data yang diakses tersebut akan dinaikkan keatas mendekati akar pohon. Data yang sering diakses / aktif akan berada dekat pada akar pohon sehingga data tersebut mudah Dengan demikian dapat disimpulkan bahwa penerapan teori pohon sangatlah bermanfaat dalam kajian struktur data.

     B.     Rumusan Masalah

Bayangkan apabila kita ingin mencari sebuah data pada sebuah senarai berkait, tentunya tidak ada cara selain mencarinya secara sekuensial dari pointer elemen pertama senarai. Bandingkan jika kita melakukan pencarian di tabel kontigu dan dengan pencarian biner (binary search), tentunya pencarian akan lebih cepat. Dan sekarang bayangkan jika kita ingin melakukan operasi penambahan dan penghapusan elemen senarai.  Operasi tersebut akan lebih lambat pada table kontigu daripada senarai berkait. Hal ini disebabkan karena operasi penambahan dan penghapusan pada tabel kontigu memerlukan pemindahan banyak entri data setiap saat, dibandingkan dengan senarai berkait yang hanya membutuhkan sedikit permainan pointer. 3

Dari permasalahan diatas tentunya dapat kita simpulkan bahwa alangkah baiknya jika kita dapat melakukan operasi pencarian dengan kecepatan eksekusi tinggi (seperti pada table kontigu dan pencarian biner) dan operasi penambahan dan penghapusan dengan kecepatan eksekusi tinggi (seperti pada senarai berkait).

     C.    Tujuan

• Mempelajari variasi bagian-bagian dari tree sebagai suatu bentuk struktur tak linier
• Mempelajari beberapa hubungan fakta yang direpresentasikan dalam sebuah tree, sehingga mampu merepresentasikan tree dalam permasalahan aslinya
• Memahami bagaimana menulis program untuk tree, dan bagaimana mengartikannya kembali dalam bentuk permasalahan aslinya.

     D.    Manfaat

Keunggulan Binary Search Tree akan sangat berguna, dimana Binary Search Tree dapat menjadi solusi permasalahan tersebut karena pencarian serta penambahan dan penghapusan elemennya memiliki kecepatan eksekusi yang tinggi. Operasi pencarian, penambahan, dan penghapusan pada Binary Search Tree memiliki run-time O (log n). 

BAB II

ISI

A.   Konsep Pohon Biner

Merupakan salat Satu bentuk Struktur Data tidak linier Yang menggambarkan hubungan Yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree Bisa didefinisikan sebagai kumpulan Simpul / node dengan Satu elemen KHUSUS Yang disebut root Dan Node lainnya terbagi menjadi Himpunan-Himpunan Yang tak saling berhubungan Satu sama lainnya (disebut subtree). Untuk jelasnya, di Bawah Akan diuraikan istilah-istilah umum dalam tree.

1)      A merupakan ROOT :

           Root Atau akar adalah elemen/node paling atas, merupakan pintu atau pointer untuk meng-akses elemen lain dalam pohon. Akar adalah satu-satunya node yang tidak memiliki ‘atasan’ atau parent.ketika suatu pohon mulai dibentuk maka node pertama yang harus diciptakan adalah akar/root ini.

2)      B, C, E, F disebut parent atau simpul dalam :

Parent atau atasan,induk merupakan node yang berada diatas suatu node tertentu.

3)      D, E disebut children

Anak atau bawahan, merupakan node yang berada dibawah satu node. Satu node bisa memiliki lebih dari satu bawahan.

4)      D, G, H, & I disebut simpul luar/DAUN

Yaitu node yang tidak memiliki anak.

5)      Node adalah elemen dari pohon.

6)      Subtree:

Suatu pohon bisa dibagi menjadi beberapa bagian-pohon(subtree), sehingga suatu node bisa merupakan root dari subtreenya.

7)      0, 1, 2, 3 merupakan level/tingkatan kedalaman setiap simpul

Level yang sama merupakan generasi yang sama

Edge/sisi merupakan garis yang menghubungkan simpul yang satu dengan yang lain.

8)      A – B – E – G atau A – C – F – I, disebut lintasan (PATH)

Atau jalur yang menghubungkan dari node asal ke suatu node tujuan melalui beberapa penggal penghubung.

Tinggi simpul : panjang lintasan dari simpul tersebut ke daun keturunannya yang paling jauh

Kedalaman (level) simpul : panjang lintasan dari simpul tersebut ke AKAR A B C D E F G H I 0 1 2 3 KLASIFIKASI TREE

B.     Binary Search Tree

Adalah Binary Tree dengan sifat bahwa semua left child harus lebih kecil daripada right child dan parentnya. Juga semua right child harus lebih besar dari left child serta parentnya. Binary seach tree dibuat untuk mengatasi kelemahan pada binary tree biasa, yaitu kesulitan dalam searching / pencarian node tertentu dalam binary tree. Contoh binary search tree umum :

          

Pada dasarnya operasi dalam binary search tree sama dengan Binary tree biasa, kecuali pada operasi insert, update, dan delete.

    1.      Insert : Pada Binary Search Tree, insert dilakukan setelah ditemukan lokasi yang tepat. (Lokasi tidak ditentukan oleh user sendiri).

                

                   

    2.      Delete : Seperti halnya update, delete dalam Binary Search Tree juga turut mempengaruhi struktur dari tree tersebut.

                             

                                     

Pada operasi di samping, delete dilakukan terhadap Node dengan 2 child. Maka untuk menggantikannya, diambil node paling kiri dari Right SubTree yaitu 13.

                                             

3.      Traverse : Mengunjungi seluruh node-node pada tree, masing-masing sekali. Hasilnya adalah urutan informasi secara linier yang tersimpan dalam tree. Ada tiga cara traverse : Pre Order, In Order, dan Post Order.

Metode pembacaan/kunjungan pada sebuah Tree dapat dilakukan dengan beberapa cara, yaitu :

·         PreOrder  : R       T1        T2

·         InOrder    : T1        R        T2

·         PostOrder  : T1        T2        R

Untuk lebih jelasnya perhatikan contoh dibawah :

a)      PREORDER
Mengunjungi suatu node, kemudian mengunjungi sisi kiri, kemudian sisi kanan.

Jadi PreOrder dari pohon biner diatas adalah :

A B D E C F G

b)     INORDER

Mengunjungi sisi kiri, kemudian node induk, lalu sisi kanan.

                                     Jadi InOrder dari pohon biner diatas adalah :

                                     D B E A F C G

c)      POSTORDER

Mengunjungi sisi kiri, sisi kanannya, lalu node induk.

Jadi PostOrder dari pohon biner diatas adalah :

D E B F G C A

BAB III

PENUTUP

A.       Kesimpulan

Tree adalah sebuah struktur linier, biasanya digunakan untuk menggambarkan hubungan yang bersifat hirarkis antara elemen-elemen yang ada. Ada beberapa istilah dalam tree ini, yang mana masing-masing istilah  mempunyai arti dalam kaitannya dengan hirarki antar elemen dalam tree tersebut, seperti sibling, descendant dsb.

Dalam ilmu komputer, tree adalah sebuah struktur data yang secara bentuk menyerupai sebuah pohon, yang terdiri dari serangkaian node (simpul) yang saling berhubungan. Node-node tersebut dihubungkan oleh sebuah vektor. Setiap node dapat memiliki 0 atau lebih node anak (child). Sebuah node yang memiliki node anak disebut node induk (parent). Sebuah node anak hanya memiliki satu node induk. Sesuai konvensi ilmu komputer, tree bertumbuh ke bawah, tidak seperti pohon di dunia nyata yang tumbuh ke atas. Dengan demikian node anak akan digambarkan berada di bawah node induknya.

B.     Saran

Penulis menyadari tentang penyusunan makalah, tentu masih banyak kesalahan dan kekurangannya, karena terbatasnya pengetahuan dan kurangnya rujukan atau referensi yang ada hubungannya dengan judul makalah ini.

Penulis banyak berharap para pembaca yang budiman sudi kiranya memberikan kritik dan saran yang membangun kepada penulis demi sempurnanya makalah ini dan penulisan makalah di kesempatan-kesempatan berikutnya. Semoga makalah ini berguna bagi penulis pada khususnya juga para pembaca yang budiman pada umumnya.

Demikian penulis menyusun mata kuliah ‘Jaringan Komputer” membahas Materi - materi mata kuliah tersebut. Sehingga mahasiswa dapat mengenal tentang Konsep komunikasi data, komponen-komponen komunikasi data, Komponen dasa perangkat jaringan computer.