AVL TREE

AVL tree is a binary search tree in which the difference of heights of left and right subtrees of any node is less than or equal to one. The technique of balancing the height of binary trees was developed by Adelson, Velskii, and Landi and hence given the short form as AVL tree or Balanced Binary Tree.

·        Height of a node:

Ø  The height of an empty subtree is 0.

Ø  The height of a leaf is 1.

Ø  The height of an internal node is the maximum height of its children plus 1.

·        Balance factor:

Ø  The difference height of its LEFT subtree and its RIGHT subtree.

·        The balance factor of all nodes in AVL tree should be at most 1.

·        INSERTION

Ø  Step 1: First, insert a new element into the tree using BST's (Binary Search Tree) insertion logic.

Ø  Step 2: After inserting the elements you have to check the Balance Factor of each node.

Ø  Step 3: When the Balance Factor of every node will be found like 0 or 1 or -1 then the algorithm will proceed for the next operation.

Ø  Step 4: When the balance factor of any node comes other than the above three values then the tree is said to be imbalanced. Then perform the suitable Rotation to make it balanced and then the algorithm will proceed for the next operation.

·        DELETION

Ø  Step 1: Firstly, find that node where k is stored

Ø  Step 2: Secondly delete those contents of the node (Suppose the node is x)

Ø  Step 3: Claim: Deleting a node in an AVL tree can be reduced by deleting a leaf. There are three possible cases:

§  When x has no children then, delete x

§  When x has one child, let x' becomes the child of x.

§  Notice: x' cannot have a child, since subtrees of T can differ in height by at most one :

v  then replace the contents of x with the contents of x'

v  then delete x' (a leaf)

Ø  Step 4:  When x has two children,

§  then find x's successor z (which has no left child)

§  then replace x's contents with z's contents, and

§  delete z

Ø  In all of the three cases, you will end up removing a leaf.

BINARY SEARCH TREE

Binary search tree is a data structure that quickly allows us to maintain a sorted list of numbers. It allows us to support faster searching, rapid sorting, and easy insertion and deletion.

Binary Search Tree has the following basic operations:

·        find(x)                   : find key x in the BST

·        insert(x)               : insert new key x into BST

·        remove(x)            : remove key x from BST

Cara Kerja :

• Find

Metode ini ga jauh beda sama insert Cuma metode ini lebih rumit aja. Input X yang akan dicari lalu dia akan terus mencari sampai ketemu dengan kondisi jika X lebih kecil dari root key maka dia akan mencari di sebelah kiri dan sebaliknya. Pencarian akan di lakukan berulang sampai ketemu.

• Insert

Input X untuk di cari. Lalu bandingkan dengan tree paling atas, jika lebih besar taro di sebelah kanan jika lebih kecil taro di sebelah kiri. Akan di lakukan terus sampai ketemu.

• Remove

Np : Cuma mau kasih tau kalo BBT ini kemaren di jelasin di kelas gede dia itu di pake di pembuatan game NFS a.k.a Need For Speed. Jadi ternyata gw juga baru tau kalo mobil di NFS itu ngga bergerak dan yang bergerak itu backgroundnya menggunakan si insert dan remove itu. Itu aja sih fact nya. Thankyou.

HASHING TABLE

Hash Table

Hash table adalah sebuah table yang isinya adalah sebuah data yang berfungsi untuk memetakan nilai kunci unik untuk setiap baris menjadi angka lokasi record tersebut di dalam tabel. Hash tabel sendiri memiliki sebuah kelebihan yaitu waktu aksesnya cepat sehingga jika ada record yang di cari maka langsung terletak pada angka hash lokasi storage nya.

Fungsi Hashing

Sebenarnya fungsi hashing itu bebas, terserah kalian ingin mendefinisikannya seperti apa. Tapi, berikut adalah fungsi hashing yang di harapkan :

·        Untuk dua buah key yang sama, hasil hashing-nya selalu sama.

·        Memiliki kompleksitas rendah.

·        Meminimalkan collision (akan dijelaskan pada bagian selanjutnya).

Ada beberapa operasi pada Hash tabel :

·        - Insert

·        - Find

·       -  Remove

·       -  getIterator

Hash collision

Perhatikan bahwa jumlah kemungkinan kunci sangat banyak. Jika kunci adalah nama, jumlah kemungkinan nama tersebut sangat banyak, sedangkan jumlah sel dalam hash table terbatas. Hal ini bisa memungkinkan terjadinya collision.

Karena collision tidak mungkin terhindarkan, implementasi hash table harus menentukan apa yang harus dilakukan bila terjadi collision. Salah satu cara yang banyak dipakai yaitu dengan mengijinkan lebih dari satu nilai dalam satu lokasi. Umumnya hash table menggunakan struktur data linked list untuk menyimpan lebih dari satu nilai dalam satu lokasi yang sama.

Bila data akan dimasukkan ke dalam bucket yang sudah ada isinya (collision terjadi), maka operasinya tidak sesederhana pada kasus bucket kosong. Mari kita perhatikan animasi yang saya buat di bawah ini.

Ketika memasukkan data (insert), pada bucket yang tidak kosong maka perlu dilakukan operasi komparasi kunci untuk melihat apakah kunci yang sama sudah ada di bucket itu atau belum. Bila kunci yang sama ternyata ada di situ, artinya operasi insert berubah menjadi operasi update, yaitu mengubah data yang lama dengan yang baru. Bila kunci yang dimasukkan tidak ada di situ, maka kunci dan data yang dimasukkan akan disimpan di node paling akhir dari bucket tersebut.

Berikut ini cara-cara yang digunakan untuk mengatasi collision :

1.   Closed hashing (Open Addressing)

Close hashing menyelesaikan collision dengan menggunakan memori yang masih ada tanpa menggunakan memori diluar array yang digunakan. Closed hashing mencari alamat lain apabila alamat yang akan dituju sudah terisi oleh data. 3 cara untuk mencari alamat lain tersebut :

• Linear Probing
• Quadratic Probing
• Double hashing

2.   Open hashing

Pada dasarnya open hashing membuat tabel yang digunakan untuk proses hashing menjadi sebuah array of pointer yang masing-masing pointernya diikuti oleh sebuah linked list, dengan chain (mata rantai) 1 terletak pada array of pointer, sedangkan chain 2 dan seterusnya berhubungan dengan chain 1 secara memanjang.

Stack and Queue

Tentang prefix dan postfix:

• ·        Postfix itu caranya dengan menaruh semua operator di sebelah kanan dan mulai di scannya dari sebelah kiri. Lalu setiap angka yang bertemu dengan sebuah operator, maka angka tersebut akan di kalkulasikan dengan 1 angka sebelum angka tersebut dan hasilnya berada di posisi yang sama. Cara tersebut akan di lakukan terus sampai semuanya terkalkulasi.
• ·        Prefix itu hanya beerbeda dari mana mulainya. Kalau postfix semua operator di taruh di sebelah kiri, prefix kebalikannya. Begitu juga dengan cara menghitungnya, kebalikan dari postfix.

Stack

Sebuah penyimpanan data yang tersusun secara linear. Hanya ada 1 jalan keluar sehingga jika ada yang di taruh di atas atau paling terakhir, maka yang di paling atas atau terakhir juga yang di keluarkan atau di sebut dengan last in first out (LIFO).

Queue

Berbeda dengan stack, queue akan menyimpan sebuah data dengan lebih terstruktur. Ibaratnya seperti kita mengantri yang pertama datang yang pertama di layani atau di sebut first ini first out (fifo).

LINKED LIST

Ø Pengertian Linked list :

·        sekumpulan elemen bertipe sama, yg mempunyai keterurutan tertentu, yang setiap elemennya terdiri menjadi dua bagian

·        struktur berupa rangkaian elemen saling berkait dimana setiap elemen dihubungkan elemen lain melalui pointer. Pointer merupakan alamat elemen. Penggunaan pointer buat mengacu elemen mengakibatkan elemen-elemen bersebelahan secara logik walau tak bersebelahan secara fisik di memori.

Ø  Link list adalah desain tmpt penyimpanan data yang terdiri dari node-node (simpul-simpul) yg saling terhubung. Link list dapat diilustrasikan misalnya kereta barah, dimana kereta api terdiri menurut gerbong-gerbong yg saling terhubung yg dapat mengangkut penumpang. Gerbong disini setara menggunakan node pada link list yang berfungsi buat menyimpan data.
Jika kita menyimpan data 3, 5 dan 7 pada array, maka ilustrasi tempat penyimpanannya sbb:

Ø  Dengan 1 nama, array mampu menyimpan data yg bertipe sama. Dimana setiap data memiliki indeks. Sedangkan apabila data tersebut disimpan dalam link list, maka ilustrasi tempat penyimpanannya menjadi berikut :

1.      Singly Linked List :

·   Setiap node pada linked list memiliki field yang berisi pointer ke node berikutnya & juga memiliki field yg berisi data.

·   Akhir linked list ditandai dengan node terakhir akan menunjuk ke null yang akan digunakan sebagai kondisi berhenti ketika pembacaan linked list.

2.      Doubly Linked List :

·   Linked list dengan menggunakan pointer, dimana setiap node mempunyai 3 field, yaitu: 1 field pointer yg menunjuk ke pointer berikutnya, 1 field pointer yang menunjuk ke pointer sebelumnya & field yg berisi data dari node tadi.

·   Pointer next & prev-nya menunjuk ke null.

3.      Singly Circular Linked List :

·   Single Linked List yg pointer next-nya menunjuk ke dirinya sendiri, jika terdiri dari beberapa node maka pointer terakhirnya akan memilih ke pointer terdepannya.

4.      Double Circular Linked List :

·   Double Linked List yg pointer next & prev-nya menunjuk ke dirinya sendiri secara circular.

Link list tidak memiliki indeks misalnya array. Kita hanya bisa untuk memberi nama node. Akan tetapi, tidak seluruh node pada link list memiliki nama. Sebaiknya kita memberi nama untuk node yang pertama (misal namanya head), & node yang terakhir (misal namanya tail). Tujuannya buat memudahkan operasi link list dari depan atau belakang, misal nambah data atau menghapus data.