Heap and Tries

Heap adalah bentuk pohon biner yang mempertahankan properti unik.satu tumpukan populer adalah min-heap,yang mengatur data sedemikian rupa sehingga sangat mudah untuk mengakes yang terkecil dari elemen heap.
Heap-pohon biner khusus untuk menyimpan data yang diurutkan,dapat membuat lebih lambat untuk pencarian,tetapi lebih cepat untuk pemasangan,struktur heap data dapat digunakan secara efisien untuk menemukan elemen terkecil atau elemen terbesar dalam array.

Tries:struktur pohon yang digunakan untuk mewakili kata-kata,yang dimana tidak diperlukan simpul dalam menjalankannya,sebagai kunci dari tries atau nilai yang sangat dikaitkan dengan tepi,dan node dan hanya ada untuk pelengkap
A simple Node class can be used to represent nodes in the trie:

class Node:
   def __init__(self) -> None:
       # Note that using dictionary for children (as in this implementation)
       # would not allow lexicographic sorting mentioned in the next section
       # (Sorting), because an ordinary dictionary would not preserve the
       # order of the keys
       self.children: Dict[str, Node] = {}  # mapping from character ==> Node
       self.value: Any = None

Sumber :https://ada110.github.io/dist/course_notes/Heaps_and_Tries.pdf
             https://www.codingblocks.net/podcast/data-structures-heaps-and-tries/

Read More

AVL TREE

AVL adalah balanced binary search tree dimana ia memiliki perbedaan jumlah node pada subtree kiri dan subtree kanannya maksimal 1 (atau dapat dikatakan antara tingginya sama atau selisih satu).

Insert suatu node pada AVL sama halnya pada insert node pada binary search tree, dimana node baru diposisikan sebagai leaf. Setelah memasukkan node baru, maka harus dilakukan penyeimbangan kembali pada path dari node yang baru di insert atau path terdalam.

Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu :

anggap T adalah node yang harus diseimbangkan kembali

- Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)
- Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)
- Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)
- Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)

Ke-4 kasus tersebut dapat diselesaikan dengan melakukan rotasi
- Kasus 1 dan 2 dengan single rotation
- Kasus 3 dan 4 dengan double rotation

 

Single rotation

single rotation dilakukan bila kondisi AVL tree akan ditambahkan node baru dan posisi node baru seperti pada gambar berikut.t1,t2,t3 adalah subtree yang urutannya height-nya harus sama (>=0)

Double rotation

Double rotation dijalankan bila kondisi AVL tree akan ditambahkan node baru dan posisi node baru.t1,t2,t3,dan t4 adalah subtree yang urutannya harus seperti demikian.tinggi subtree T1 harus sama dengan T4(>=0),tinggi subtree T2 harus sama dengan T3(>=0).Node yang ditambahkan akan menjadi child dari T2 dan T3.

Deletion AVL

operasi penghapusan node sama seperti pada Binary Search Tree yaitu node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan.jika yang dihapus adalah leaf,maka langsung dihapus.namun jika node yang dihapus memiliki child maka childnya yang menggantikannya.dan tree dicek sampai keduanya seimbang.

delete node 60

Sumber:http://suciantinovi.blogspot.com/2014/05/balanced-binary-tree-and-2-3-tree.html

               https://socs.binus.ac.id/2017/05/15/deletion-avl-tree/

               http://dinda-dinho.blogspot.com/2013/06/pengertian-dan-konsep-avl-tree.html

Read More