Pengertian Binary Tree, Binary Search Tree Dan Hash

Kamis, 27 Desember 2018

Binary Tree

Binary Tree atau Pohon Biner yaitu sebuah pohon dalam struktur data yang bersifat hirarkis (hubungan one to many). Tree sanggup didefenisikan sebagai kumpulan simpul dengan setiap simpul mempunyai paling banyak dua anak. Secara khusus, anaknya dinamakan kiri dan kanan. Binary tree tidak mempunyai lebih dari tiga level dari Root.
Binary tree yaitu suatu tree dengan syarat bahawa tiap node (simpul) hanya boleh mempunyai maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binary treee boleh mempunyai paling banyak dua child (anak simpul), secara khusus anaknya  dinamakan kiri dan kanan.
Pohon biner sanggup juga disimpan sebagai struktur data implisit dalam array, dan bila pohon tersebut merupakan sebuah pohon biner lengkap, metode ini tidak boros tempat. Dalam penyusunan yang rapat ini, bila sebuah simpul mempunyai indeks i, anaknya sanggup ditemukan pada indeks ke-2i+1 dan 2i+2, meskipun ayahnya (jika ada) ditemukan pada indeks lantai ((i-1)/2) (asumsikan akarnya mempunyai indeks kosong).

Binary Search Tree

Binary Search Tree yaitu tree yang terurut (ordered Binary Tree). Binary Search Tree juga sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan warta nama atau bilangan yang disimpan di dalam memory. Dengan ini data dibagi menjadi dua dengan mencari titik tengah seagai patokannya. Binary tree terdiri dari simpul utama yang disebut dengan istilah root. Kemudian dari root tersebut terdapat bab kiri dan bab kanan. Data disimpan sesudah root disimpan menurut nilai perbandingan dengan root tersebut. Pengurutan sanggup dilakukan bila BST ditelusuri (traversed) memakai metode in-order. Detail dari proses penelusuran ini akan dibahas pada pertemuan selanjutnya. Data yang telah tersusun dalam struktur data BST juga sanggup dicari dengan gampang dan mempunyai rata-rata kompleksitas sebesar O(log n), namun membutuhkan waktu sebesar O(n) pada kondisi terjelek dimana BST tidak berimbang dan membentuk menyerupai linked list
Binary search tree memungkinkan pencarian dengan cepat, penambahan, juga menghapus data yang ada di dalamnya, sanggup juga dipakai sebagai implementasi sejumlah data dinamis, atau pencarian table data dengan memakai warta kunci atau key.
Agar data benar-benar tersusun dalam struktur data BST, dua hukum yang harus dipenuhi pada dikala data diatur dalam BST yaitu sebagai berikut:

• Semua data dibagian kiri sub-tree dari node t selalu lebih kecil dari data dalam node t itu sendiri.
• Semua data dibagian kanan sub-tree dari node t selalu lebih besar atausama dengan data dalam node t.

Hash

Hash atau Hashing berarti memenggal dan kemudian menggabungkan. Hash memakai memori penyimpanan utama berbentuk array dengan perhiasan algoritma untuk mempercepat pemrosesan data. Hash merupakan suatu metode yang secara pribadi mengakses record-record dalam suatu tabel dengan melaksanakan transformasi aritmatik pada key yang menjadi alamat dalam tabel tersebut.
Hashing dipakai sebagai metode untuk menyimpan data dalam sebuah array semoga penyimpanan data, pencarian data, penambahan  data dan pembatalan data sanggup dilakukan dengan cepat.
Fungsi hash haruslah stabil (referential transparent), artinya, bila ia dipanggil dua kali oleh masukan yang benar-benar sama(sebagai misal,string yang mengandung sekuen abjad yang sama), maka ia haruslah memberi hasil yang sama pula.
Pelacakan dengan memakai Hash terdiri dari dua langkah utama, yaitu:

Menghitung Fungsi Hash

Fungsi Hash yaitu suatu fungsi yang mengubah key menjadi alamat dalam tabel. Fungsi Hash memetakan sebuah key ke suatu alamat dalam tabel. Idealnya, key-key yang berbeda seharusnya dipetakan ke alamat-alamat yang berbeda juga. Pada kenyataannya, tidak ada fungsi Hash yang sempurna. Kemungkinan besar yang terjadi yaitu dua atau lebih key yang berbeda dipetakan ke alamat yang sama dalam tabel. Peristiwa ini disebut dengan collision (tabrakan). Karena itulah dibutuhkan langkah berikutnya, yaitu collision resolution (pemecahan tabrakan).

Collision Resolution

Collision resolution merupakan proses untuk menangani kejadian dua atau lebih key di-hash ke alamat yang sama. Cara yang dilakukan bila terjadi collision yaitu mencari lokasi yang kosong dalam tabel Hash secara terurut. Cara lainnya yaitu dengan memakai fungsi Hash yang lain untuk mencari lokasi kosong tersebut.

Sumber https://sourcecodegeneration.blogspot.com/

Share This :