AVL tree

AVL tree adalah salah satu cara rebalancing dari BST yang tidak seimbang antara node kanan dan node kiri .
BST memiliki kekurangan yaitu jika user memsasukkan input dengan angka yang terus bertambah maka salah satu cabang akan memiliki depth yang lebih dari yang lainnya. AVL tree bisa membantu meminimalisir hal ini.

BST yang mau di seimbangkan dapat dilakukan :
- Single rotation untuk menyeimbangkan tree yang dimana node yang menyebabkan masalah ada di bagian kanan dari node kanan dari node yang tidak seimbang atau bagian kiri dari bagian node kiri yang tidak seimbang
- double rotation untuk menyeimangkan tree dimana node yang menyebabkan masalah berada di bagian kiri dari node bagian kanan yang tidak seimbang atau node bagian kanan dari node kiri dari node yang tidak seimbang

Hashing and binary tree

Hashing

Hashing adalah merubah sebuat string ke dalam bentuk aritmatik yang merepresentasikan string tersebut. Hashing memasukkan bentuk aritmatik tersebut sebagai key dan memasukkannya ke dalam hash table

ada beberapa cara mendapatkan key yaitu:
1. mid-square
2. division
3. folding
4. digit extraction
5. rotating hash

jika ada beberapa string yang masuk ke dalam 1 array yang sama disebut dengan collision. Collision dapat di selesaikan dengan beberapa cara yaitu:
1. Linear Probing -> memasukkan string yang akan di masukkan ke dalam array yang sudah ada isinya tersebut ke array kosong terdekat.
2. Chaining -> tetap memasukkan string tersebut ke dalam srray yang sama dan menghubungkannya dengan linked list

Hashing digunakan dalam cryptographic untuk memperkecil output yang di keluarkan dan membuat transaksi menjadi aman dan tidak dapat di artikan oleh orang lain selain program itu sendiri.

Binary Tree

node yang paling atas disebut dengan Root

node yang dibuat dengan struct akan seperti ini

struct node {

  int data;

  struct node *left;

  struct node *right;

  struct node *parent;

};

struct node *root = NULL;

jika suatu node tidak memiliki child pointernya diisikan NULL

pertemuan 2

Linked list

ada 2 hal yang dapat dilakukan pada linked list yaitu
1. Push / insert -> push atau insert digunakan untuk menambahkan node dari sebuah linked list
2. Pop -> pop digunakan untuk menghilangkan sebuah node

A. Push
push dibedakan jadi 3 yaitu:
1. Push depan -> push depan berarti menambahkan node di depan linked list dan node baru itu menjadi node head. Harus diperhatikan bahwa node baru harus menunjuk ke node head yang lama baru node head bisa dipindahkan ke node yang baru ditambahkan.
2. Push belakang -> push belakang berarti menambahkan node menjadi tail sebuah linked list harus diperhatikan bahwa node yang baru harus memuliki nilai next yaitu NULL (kecuali  circular linked list). push belakang juga harus memperhatikan tail yang lama untuk menunjuk ke pada node yang baru.
3. Push tengah -> push tengah yaitu menambahkan node ke dalam linked list yang sudah ada. Perlu diperhatikan bahwa node sebelum harus menunjuk node yang baru tersebut dan node yang baru menunjuk node setelahnya agar linked list tetap berhubungan.

B. Pop
Pop dibedakan menjadi 3 yaitu:
1. Pop depan-> menghilangkan node head. Perlu dperhatikan bahwa node head harus dipindahkan dulu ke node sebelahnya baru melakukan free() pada node pertama.
2. Pop tengah-. menghilangkan node di antara head dan tail. Perlu diperhatikan bahwa node yang ada sebelum node yang akan di Free di hubungkan dulu ke node yang ada sesudah node yang akan di free baru bisa melakukan Free() kepada node yang ingin di hapus.
3. Pop belakang-> melakukan free pada node tail. perlu diperhatikan bahwa node tail harus dipindahkan dulu ke node sebelum yang kita inginkan untuk di hapus lalu melakukan Free() pada node paling akhir. Perlu juga diingat untuk memberikan nilai next pada tail yaitu NULL.

GSLC 1

Linked List adalah urutan data yang saling berhubungan.

CIRCULAR LINKED LIST

Circular linked list merupakan linked list dimana pointer tail menunjuk kepada pointer head dari linked list itu sendiri. Berbeda dari Single Linked List, Circular Single Linked List pada praktiknya tidak akan memiliki pointer yang menyimpan nilai NULL, karena semuanya saling terkoneksi membentuk loop.

DOUBLY LINKED LIST

Konsep double linked list sama seperti single linked list tapi yang membedakan yaitu setiap node mamiliki 2 hubungan yaitu dengan list sesudahnya dan sebelumnya.Dengan kata lain setiap node memiliki 2 pointer.

DOUBLY LINKED LIST: INSERT

Saat akan memasukka suatu list ke list yang sudah ada harus memperhatikan 2 node yang akan di geser agar list pointer next list sebelum menunjuk ke list kita yang baru dan pointer prev node sesudah menunjuk ke node baru.

DOUBLY LINKED LIST: DELETE

Ada 4 kondisi yang harus diperhatikan saat ingin mendelete suatu node:

1.      Node tersebut adalah satu satunya node dalam linked list

2.      Node tersebut adalah head

3.      Node tersebut adalah tail

4.      Node tersebut bukan merupakan head maupun  tail

CIRCULAR DOUBLY LINKED LIST

Mirip dengan single linked list circular doubly linked list seolah olah memiliki 2 loop yaitu:

1.      Loop 1: saat berada di node terakhir pointer next menunjuk ke head node

2.      Loop 2: saat berada di node pertama pointer prev  menunjuk ke tail node