DATA STRUCTURE AVL TREE

DATA STRUCTURE AVL TREE

AVL TREE adalah Binary search tree yang memiliki perbedaan Node / Jumlah tingkatan atau level pada  Subtree kanan/kirinya sebanyak 1. AVL Tree ditemukan oleh Georgy Adelson Velski dan Evgenii Landis pada tahun 1962.

Contoh dari AVL TREE =

Data yang tidak seimbang akan diseimbangkan dengan proses penyeimbangan yang disebut dengan Single rotation dan Double rotation.

SINGLE ROTATION

Rotasi penyeimbangan yang dilakukan sekali untuk menyeimbangkan AVL tree agar menjadi bentuk yang seimbang.

CONTOH = 

Sumber = https://raw.githubusercontent.com/HebleV/valet_parking/master/images/avl_left_rotation.jpg

Bisa dilihat pada gambar di atas terdapat data AVL tree yang tidak balance karena di bagian kiri dan kanannya tidak stabil. Di sini Proses single rotation dilakukan dengan Memutar data yang tidak balance tersebut yang pada kasus di atas adalah B sehingga data menjadi balance dan tidak ada lagi yang jumlah yang lebih baik di kiri atau kanannya.

DOUBLE ROTATION 

Rotasi penyeimbangan yang dilakukan 2 kali untuk menyeimbangkan AVL tree agar menjadi bentuk yang simbang. 

CONTOH = 

SUMBER = https://image.slidesharecdn.com/l3-140202101439-phpapp01/95/binary-search-trees-avl-and-red-black-26-638.jpg?cb=1391344462

Pada gambar di atas Terdapat data yang tidak balance dan harus di selesaikan dengan Double rotation.

AVL TREE DELETE

Delete dalam AVL tree adalah Operasi penghapusan Node dalam binary search tree. Node yang dihapus akan digantikan oleh NODE terbesar pada subtree di kiri / NODE terkecil pada Subtree di kanan.

Hash dan Binary table

HASHING

Hashing adalah Suatu teknik dalam pemograman untuk mengubah string menjadi sebuah fungsi agar agar lebih cepat mendapatkan info di dartabase. Fungsi diambil menggunakan funsi ini disebut Hash function. Ada juga hash table yang menampung data data tersebut.

sumber gambar :https://www.gatevidyalay.com/wp-content/uploads/2018/06/Hashing-Diagram.png

Hashing bisa di terapkan dengan 2 langkah:

1. data diubah ke dalam bentuk integer menggunakan fungsi hash. data digunakan sebagai indeks untuk menyimpan data yang terdapat pada tabel hash.

2. Data yang di simpan di hash table akan Diambil dengan cepat oleh kunci hash.

BINARY TREE

Binary tree adalah sebuah hubungan antar data dimana setiap data memiliki 2 buah dan bersifat hirarki. 2 data yang di kira dan di kanan dinamakan data kiri dan data kanan sesuai dengan lokasi data tersebut.

Sumber gambar : https://www.tutorialspoint.com/data_structures_algorithms/images/binary_search_tree.jpg

Concept :

- Data yang paling pertama atau yang paling atas disebut Node

- Penghubung antar data yang berbentuk garis pada gambar disebut sebagai edge 

- Node paling akhir / tidak mempunyai node anak disebut leaf

- jumlah total sub dari node disebut degree

- maximum level dari node disebut height

Data Structure 2301875521

DATA STRUCTURE

Linked List

Linked List adalah  tipe struktur data yang terdiri dari urutan record pada data dimana setiap Data memliki field yang menyimpan alamat  dan di gunakan untuk melanjutkan memori ke data yang berikutnya. 
Data yg dihubungkan di sebut node.

Source : https://encrypted-tbn0.gstatic.com/images?q=tbn%3AANd9GcTo_rneB5EI28LDqmV9d9WBeJuGuzTrChpJbDMzSaO1zsZSr6t9

Pada kesempatan kali Ini saya akan menjelaskan tentang single linked list dan double link list

1. Single linked list


Single Linked List adalah sekumpulan dari node yang diawali dari Head dan diakhiri dengan node yang berarah pada Null.

https://miro.medium.com/max/953/1*elJncKhH_P9oQglfI1aVQA.png


Setiap node mempunyai field yang berisi pointer ke node berikutnya yang juga mempunyai field yang mengisikan data. Node yang paling terakhir akan menunjuk ke node yang paling depan sehingga linked list tersebut akan berputar. 

2. DOUBLE LINKED LIST

Setiap Node pada Double link list terdiri dari 3 field dan menunjuk pada 2 arah. 

https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcTWND8l636JzerhRmCxhaWUhP8hQvctok2a5hSP7Dioo6HA88Vl7f3Ifz2Fpw&s=10