Binary Tree
Binary tree ialah 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 kalau pohon tersebut merupakan sebuah pohon biner lengkap, metode ini tidak boros tempat. Dalam penyusunan yang rapat ini, kalau 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
See Other Article
Binary Search Tree ialah tree yang terurut (ordered Binary Tree). Binary Search Tree juga sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan info 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 info kunci atau key.
Agar data benar-benar tersusun dalam struktur data BST, dua hukum yang harus dipenuhi pada ketika data diatur dalam BST ialah sebagai berikut:
Hash atau Hashing berarti memenggal dan kemudian menggabungkan. Hash memakai memori penyimpanan utama berbentuk array dengan komplemen algoritma untuk mempercepat pemrosesan data. Hash merupakan suatu metode yang secara eksklusif 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 biar penyimpanan data, pencarian data, penambahan data dan peniadaan data sanggup dilakukan dengan cepat.
Fungsi hash haruslah stabil (referential transparent), artinya, kalau ia dipanggil dua kali oleh masukan yang benar-benar sama(sebagai misal,string yang mengandung sekuen huruf yang sama), maka ia haruslah memberi hasil yang sama pula.
Pelacakan dengan memakai Hash terdiri dari dua langkah utama, yaitu:
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 info kunci atau key.
Agar data benar-benar tersusun dalam struktur data BST, dua hukum yang harus dipenuhi pada ketika data diatur dalam BST ialah 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
Hashing dipakai sebagai metode untuk menyimpan data dalam sebuah array biar penyimpanan data, pencarian data, penambahan data dan peniadaan data sanggup dilakukan dengan cepat.
Fungsi hash haruslah stabil (referential transparent), artinya, kalau ia dipanggil dua kali oleh masukan yang benar-benar sama(sebagai misal,string yang mengandung sekuen huruf 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 ialah 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 ialah dua atau lebih key yang berbeda dipetakan ke alamat yang sama dalam tabel. Peristiwa ini disebut dengan collision (tabrakan). Karena itulah diharapkan langkah berikutnya, yaitu collision resolution (pemecahan tabrakan).Collision Resolution
Collision resolution merupakan proses untuk menangani insiden dua atau lebih key di-hash ke alamat yang sama. Cara yang dilakukan kalau terjadi collision ialah mencari lokasi yang kosong dalam tabel Hash secara terurut. Cara lainnya ialah dengan memakai fungsi Hash yang lain untuk mencari lokasi kosong tersebut.
Share this Article
