Data Structure 4: Tree, Binary Tree and Expression Tree

  1. Tree

Tree adalah kumpulan dari beberapa node.

Ada beberapa istilah dalam sebuah tree:

Sumber: http://collegelabs.co/clabs/nld/images/tree%20(1).gif

  • Parent: node induk dari beberapa node.
  • Child : anak/bawahan dari beberapa node.
  • Edge: Garis yang menghubungkan parent ke child.
  • Height/Depth : jumlah tingkatan dari tree tersebut.
  • Degree : jumlah maksimal child dari suatu parent.
  • Ancestor : Semua node yang menunjuk suatu node x / seluruh parent dari x.
  • Descendant : Semua node child dari node x.
  • Leaf : node yang tidak memiliki child.
  • Sibling : Dua node yang memiliki 1 parent yang sama.

2. Binary Tree

Sumber: https://upload.wikimedia.org/wikipedia/commons/thumb/f/f7/Binary_tree.svg/220px-Binary_tree.svg.png

Binary adalah tree yang memiliki paling banyak 2 child, yaidu node kiri (left) dan node kanan (right). Node yang tidak memiliki child disebut leaf.

Jenis-jenis Binary Tree:

  1. PERFECT binary tree:
    Binary tree yang setiap level nya berada dalam Height/Depth yang sama.
  2. COMPLETE binary tree:
    Binary tree yang di setiap levelnya kecuali yang terakhir terisi penuh, setiap node semungkinnya terletak se-kiri-kirinya. Sebuah perfect binary tree adalah complete binary tree.
  3. SKEWED binary tree:
    Binary tree yang setiap node nya memiliki 1 child.
  4. BALANCED binary tree:
    Binary tree dimana tidak ada leaf yang lebih jauh dari leaf lainnya (di level yang sama).

Ciri-ciri Binary Tree:

  • Jumlah maksimum node di level k di sebuah binary tree adalah 2k
  • Jumlah maksimum node disebuah binary tree dengan height h adalah 2h+1-1
  • Height minimum di sebuah binary tree dengan jumlah node n adalah 2log(n)
  • Height maximum di sebuah binary tree dengan jumlah node n adalah n-1

3. Expression Tree

  • Expression tree adalah tree yang digunakan untuk notasi matematika.
  • Dapat digunakan dengan metode prefix, infix dan postfix.
    • Di prefix, operator dibaca terlebih dahulu baru turun sampai node paling dalam, diproses dari kiri ke kanan
    • Di infix, diambil operand pertama dahulu baru kembali ke parent untuk mendapat operator sebelum ke node kanan untuk mengambil operand kedua. Di infix, untuk menghindari kebingungan operasi matematika digunakan tanda kurung.
    • Di postfix, operand diambil dahulu sampai ke ujung leaf terakhir, barulah operator dibaca.