Heap Tree

Heap is a complete binary tree based data structure that satisfies heap property.

Heap Property :

• Min Heap = each node’s element is smaller than its children’s node.
  • It implies that the smallest element is located at the root of the tree.
  • The largest element is located somewhere at one of the leaves node.
  • Insertion in min heap :
    • We would like to insert a new element into the heap, but we should maintain its heap property.
    • Insert the new element at the end of the heap (after the index of the last element).
    • Upheap the new element (fixing its heap property).
  • Deletion in min heap :
    • Here we only concern with deletion of the smallest element which is located at the root.
    • Replace root with the last element of the heap.
    • Decrease the number of element in heap.
    • Downheap root (fixing its heap property).
• Max Heap = each node’s element is larger than its children’s.
  • Each node’s element is larger than its children’s element.
  • It implies that the largest element is located at the root of the tree
  • Max-heap holds the same principle as min-heap and can be used to create priority queue which need to find the largest element instead of the smallest one.
• Min Max Heap :
  • The heap condition alternates between minimum and maximum level to level
  • Each element on even/odd level are smaller than all its children (min-level).
  • Each element on odd/even level are larger than all its children (max-level).The purpose of min-max heap is to allow us to find both the smallest and the largest element of the heap at the same time.
  • The smallest element is located at the root.
  • The largest element is located in one of the root’s child (either left/right child).
  • Note: the largest element may be located at root if there is only one element in the heap.
  • Insertion :
    • Insert the new element at the end of the heap (after the index of the last element).
    • Upheap the new element (fixing its heap property).
    • Upheap in min-max heap is a bit different with min-heap or max-heap.
  • Deletion :
    • Deletion MIN
      • Replace root with the last element in heap.
      • Decrease the number of element in heap.
      • Downheapmin from root.
    • Deletion MAX :
      • Replace either left-child or right child of root (depends on which one is larger) with the last element in heap.
      • Decrease the number of element in heap.
      • Downheapmax from the node.

Data Structures 07 :

• 2-3 Tree
• Red Black Tree

2-3 Tree :

2-3 Tree ada 2 jenis node

• node 2 : tidak punya anak atau punya 2 anak.  contoh node 2. p dan q bisa null bisa ber angka :  
• node 3: tidak punya anak atau punya 3 anak. contoh node 3. p, q dan r bisa null bisa ber angka : 

2-3 Tree harus simetris, alias perbedaan level kiri dan kanan harus sama.

Insert :

• Selalu insert mengisi yang kosong dari paling atas. kalau dari bawah kosong, cek dahulu ke parentnya, apakah kosong atau penuh, jika kosong, naik lagi sampai terisi bagian atas semua.

Delete:

• Jika yang di delete adalah leaf node, bisa langsung dilakukan penghapusan.
• Jika bukan, harus dilakukan reposisi.

 

Red Black Tree

Kriteria:

• Root selalu berwarna hitam
• Paling bawah selalu terdapat null node (hitam)
• Tree balance tidak balance dihitung dari jumlah lompatan node hitam dari setiap null node. Jumlahnya harus sama.

Insert :

Node yang baru diinsert selalu berwarna merah.

Jika node yang baru masuk, parent dari node tersebut berwarna merah, dan tetangga dari parent tsb juga berwarma merah, maka harus dilakukan color flip : 

Jika node yang baru masuk, parent dari node tersebut berwarna merah, dan tetangga dari parent tsb berwarma hitam, maka harus dilakukan single/double rotation seperti AVL :

Jika setelah melakukan color flip dan mengubah root node menjadi merah, maka harus dilakukan Re-coloring. atau mengubah warna menjadi hitam. re-coloring ini biasa hanya berlaku untuk root node.

AVL TREE

---

Binary tree -> tidak tersusun, angka lebih besar atau kecil daripada root bisa bebas kiri atau kanan.

Binary Search tree -> tersusun rapih, biasanya angka lebih kecil daripada root ke kiri dan yg lebih besar ke kanan.

BALANCED BST -> Balanced binary search tree terdiri dari yang disebut AVL tree (Georgy Adelson-Velsky and Evgenii Landis‘ tree) dan Red Black Tree.

 

θ (log⁡ n) -> avl dan red black tree.

Kali ini hanya membahas AVL tree. AVL ada namanya balance factor. Balance factor adalah perbandingan level antara level kiri dan kanan. contoh: child kiri ada 4 level kebawahnya, child kanan ada 3 level kebawahnya, berarti balance factornya adalah 1. Jika balance factor lebih dari 1, berarti tree tsb tidak balance.

 

ada 2 cara untuk menyeimbangkan tree tsb

• Single Rotation 
• Double Rotation

*nama-nama diambil dari wikipedia.