Heap :

Heap adalah jenis tree yang unik. Heap terdiri dari 3 jenis yaitu :

1.Heap max = heap yang rootnya pasti yang terbesar, sehingga node orang tuanya lebih besar dari node anaknya.

2.Heap min = heap yang rootnya pasti yang terkecil, sehingga node orang tuanya lebih kecil dari node anaknya.

3.Heap min-max = heap yang rootnya terkecil, lalu node yang berada di level ganjil selalu maximal dan mode yang berada di level genap selalu minimal

untuk insert pada min-max heap, harus di sesuaikan dengan levelnya, bila mana di level genap ada element max maka harus di tukar dengan element min karena di level genap harusnya hanya ada element min.

TRIES

Tries adalah jenis tree yang digunakan untuk menyimpan array asosiatif yang biasanya berupa string. trie diambil dari kata RETRIEVAL karena tries dapat menemukan kata hanya dengan beberapa huruf depannya saja.

contoh pada tree tries di atas maka jika anda mengetik B-O maka akan muncul 3 pilihan yaitu BOM /BOS / BOR

Hashing

hashing adalah metode untuk menimpan data berdasarkan indexnya sehingga lebih mudah di akses dan di cari, biasanya pada database.

bentuk dari hashing adalah hash tabel

dapat dilihat bahwa atan yang huruf depannya a di simpan di index pertama, lalu index 1 kosong karena itu seharusnya untuk data yang berhuruf depan b.

Red Black Tree

Red black tree adalah jenis tree yang mempunyai warna merah di hitam di node-nodenya.

Termasuk tree yang balance pada saat insertionnya. contohnya sebagai berikut

• Memasukan node seperti binary tree insertion.
• Node yang baru selalu berwarna merah

:

syarat untuk memasukan node baru adalah :

• kalau parentnya black, berarti tidak ada violation.
• jika orang tuanya merah maka terjadi violation, anak merah tidak boleh memiliki orang tua yang merah.

cara untuk memperbaiki tree :

• Node baru disebut q, orang tuanya p, dan saudara dari orang tuanya s (paman dari q). Jika orang tua tidak mempunyai saudara, maka s adalah hitam (node external berwarna hitam).
• Jika s adalah merah, maka ubah p dan s ke warna hitam dan orang tua dari p menjadi merah.
• Jika s adalah hitam, lakukan rotasi single atau double, ubah pivot rotasi terakhir menjadi hitam dan anaknya merah.

2-3 Tree

bukan binary tree, sehingga cabangnya tidak harus 2. suatu node bisa punya 2 anak dan 1 data atau 3 anak dan 2 data.

Lalu insertion yang dilakukan seperti ini :

beberapa syarat insertion antara lain :

• Memasukan data baru data key.
• Lakukan pencarian dimana key akan diletakan, seharusnya ada di leaf.
• Jika leaf adalah  2-node maka taruh saja key baru disana (jadi sekarang 3-node).
• Jika leaf sudah 3-node push data di tengah. Diantara A, B and key (A dan B dalah kedua data yang ada di 3-node) ke orang tuanya dan pisah kedua data sisa tadi menajadi dua 2-node. Betulkan orang tuanya secara recursive .

beberapa Syarat deletion :

• Mengahapus key dari 2-3 tree.
• Seperti pada BST, kita harus menemukanleaf key yang dapat menggatikan key yang mau kita hapus.Jadi penghapusan akan selalu berada di leaf.
• Jika leafnya adalah 3-node, maka hapus keynya sehingga menjadi 2-node.
• Jika leafnya 2-node:
• Jika orang tuanya 3-node, ambil 1 nilai dari sana.Jika saudaranya 3-node, dorong 1 nilai dari saudara ke orang tua sehingga menjadi 3-node lagi. Jika saudaranya 2-node, buat orang tua menjadi 2-node dan gabungkan node yang sekarang dengan saudaranya..
• Jika orang tuanya 2-node. Jika saudaranya 3-node ambil 1 nilai dari orang tuanya dan push 1 nilai dari suadaranya ke orang tuanya. kalau tidak gabungkan orangtuanya dengan saudaranya.
• Betulkan orangtuanya secara rekursif.

Pertemuan 6 : guest lecturer selvakumar manickam

TREE

Tree adalah konsep data dimana data-data dihubungkan oleh suatu garis yang tidak membuat sirkuit. Garis di sebut Edges sedangkan data-data disebut vertices.

Tree juga memiliki beberapa jenis yaitu :

-Binary Tree

-Binary Search Tree

-Balance Tree (AVL)

AVL TREE

AVL berasal dari nama penemunya Georgy Adelson-Velsky and Evgenii Landis .

AVL tree adalah salah statu jenis tree yang berasal dari BST, tetapi memiliki karakteristik khusus yaitu tree yang dihasilkan harus balance (seimbang).

Balance faktor adalah salah satu element untuk menentukan apakah AVL tree itu sudah balance apa belum. Jika nilainya lebih dari 1 maka AVL tree tersebut tidak balance

Jika Tree tidak balance maka akan ada tindakan berupa rotasi 1x atau rotasi 2x.

contoh rotasi 1x

AVL sendiri digunakan untuk mempercepat pencarian dan penghapusan data karena cabang kanan dan kiri tidak berbeda jauh height nya.