TREE
Tree adalah kumpulan dari satu node atau lebih.
Beberapa istilah atau konsep dalam tree:
- Root : Node yang berada di paling atas
- Parent : Induk dari sebuah node
- Child / children : Turunan dari sebuah node
- Edge : Garis yang menghubungkan parent dengan child
- Leaf : Node yang tidak memiliki children
- Sibling : Node yang memiliki parent yang sama
- Degree : Jumlah sub-tree dari sebuah node
- Height / depth : Degree maksimum dalam sebuah tree
- Ancestor : Terdiri dari parent node itu sendiri beserta parent dari parent suatu node
- Descendant : Terdiri dari parent node itu sendiri beserta parent dari parent suatu node
_______________________________________________________________________
BINARY TREE
Binary tree adalah sebuah tree yang tiap node-nya memiliki paling banyak 2 children. Kedua child ini biasanya dibedakan menjadi left child dan right child.
Tipe dari binary tree:
- PERFECT Binary Tree, adalah binary tree yang seluruh level-nya memiliki height (depth) yang sama.
- COMPLETE Binary Tree, adalah binary tree yang seluruh level-nya terisi penuh (kemungkinan terkecuali level terakhir). Semua node berada pada bagian kiri sejauh mungkin (bergantung pada jumlah parents, dsb.). Perfect Binary Tree termasuk Complete Binary Tree.
- SKEWED Binary Tree, adalah binary tree yang tiap node-nya memiliki paling banyak satu child.
- BALANCED Binary Tree, adalah binary tree yang terbentuk dimana tidak ada leaf yang lebih jauh dari root dibandingkan dengan leaf yang lain (tidak ada leaf yang lebih jauh atau lebih dekat dari leaf lain).
Properti dari Binary Tree:
- Jumlah maksimal node pada binary tree dari level k adalah 2<sup>K</sup>
- Jumlah maksimal node pada binary tree dari height h adalah 2<sup>h+1</sup>-1
- Height maksimum suatu binary tree dari node n adalah <sup>2</sup>log(n)
- Height minimum suatu binary tree dari node n adalah n-1
Representasi dari Binary Tree menggunakan array:
- Index dari array merepresentasikan atau menunjukan nomor node
- Index ke-0 merupakan root
- Index dari Left Child adalah 2p + 1, dimana p = index dari parent
- Index dari Right Child adalah 2p + 2, dimana p = index dari parent
- Index dari Parent adalah (p-1)/2
Representasi dari Binary Tree menggunakan linked list:
_______________________________________________________________________
EXPRESSION TREE
Expression tree dapat dibuat dari prefix atau postfix dengan proses rekursif.
Konsep dari expression tree:
- Prefix : Print L R
Contoh : *+abc - Postfix : L R Print
Contoh : ab+c* - Infix : L Print R
Contoh : (a+b)*c