Pertemuan ke-3 Data Structure

Nama   : Muhammad Raul Taqi Athallah

NIM     : 2301893013

Hashing, Hash Tables, and Binary Tree

1.     Hashing

Hashing adalah Teknik untuk menyimpan dan mengambil keys dengan cepat. Dalam hashing, string dari karakter di ubah menjadi value pendek atau key yang mewakili string aslinya.

Hasing juga bisa dikenal sebagai konsep pendistribusian kunci/key di dalam array yang disebut hash table menggunakan fungsi hash fuction.

2.     Hash Table

Hash Table adalah sebuah struktur data yang terdiri atas sebuah table dan fungsi bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah table.

·       Operasi pada Hash Table

a.      insert         : menginput nilai dalam table

b.     find           : temukan nilai yang berhubungan dengan key

c.      remove      : temukan nilai yang berhubungan dengan key, kemudian     hapus nilai tersebut

d.     getIterator : mengembalikan iterator, yang memeriksa nilai satu demi satu

·       Struktur dan Fungsi pada Hast Tabel

Hash table menggunakan struktur data array asosiatif yang mengasosiasikan record dengan sebuah field kunci unik berupa bilangan (hash) yang merupakan representasi dari record tersebut. Misalnya, terdapat data berupa string yang hendak disimpan dalam sebuah hash table. String tersebut direpresentasikan dalam sebuah field kunci k.

Cara untuk mendapatkan field kunci ini sangatlah beragam, namun hasil akhirnya adalah sebuah bilangan hash yang digunakan untuk menentukan lokasi record. Bilangan hash ini dimasukan ke dalam hash function dan menghasilkan indeks lokasi record dalam tabel.

a.      k(x) = fungsi pembangkit field kunci (1)

b.     h(x) = hash function (2)

3.     Tree

Tree adalah data struktur non-linear yang mewakili relasi hirarki dari setiap objek data. Sebagian dari relasi tree bisa dilihat di directory structures atau hirarki organisasi.

Tree adalah kumpulan dari satu node atau lebih

 

DEGREE of TREE = 3

DEGREE of C = 2

HEIGHT = 3

PARENT of C = A

CHILDREN of  A = B, C, D

SIBILING of F = G

ANCESTOR of F = A, C

DESCENDANT of C = F, G

• Node paling atas adalah root.
• Garis yang menyambungkan node parent ke node child disebut edge.
• Node yang tidak mempunyai child disebut leaf.
•  Node yang mempunyai parent yang sama disebut sibling.
•  Degree adalah total sub tree dari node tersebut
•  Height/Depth adalah maksimum degree dari node dalam tree.
• Jika ada garis yang menyambungkan P ke Q, maka P itu disebut ancestor dari Q, dan Q adalah descendant dari P

4.     Binary Tree

Binary tree adalah rooted tree data structure dimana setiap node memiliki maksimal 2 children.

2 children itu biasanya disebut left child dan right child. Node yang tidak mempunyai child disebut leaf.

Ini adalah contoh dari Binary Tree 9 nodes. Rootnya adalah node yang berisi 18. Leaves adalah node yang berisi 9, 12, 10, dan 23

Ada beberapa tipe dari Binary Tree, yaitu :

• PERFECT Binary Tree, memiliki depth yang sama.

• COMPLETE Binary Tree 

• SKEWED Binary Tree, setiap node hanya bisa memiliki 1 anak.

 

• BALANCED Binary Tree is a binary tree in which no leaf is much farther away from the root than any other leaf (different balancing scheme allows different definitions of “much farther