Chrystopher's Blog

Sesi 4 :

Konsep Tree
Tree adalah kumpulan dari satu atau lebih node.
DEGREE of TREE = 3
DEGREE of C = 2
HEIGHT = 3
PARENT of C = A
CHILDREN of  A = B, C, D
SIBLING of F = G
ANCESTOR of F = A, C
DESCENDANT of C = F, G
Konsep :
– Node di top disebut root.
– Garis yang menghubungkan parent ke child disebut edge.
– Node yang tidak memiliki children disebut leaf.
– Node yang memiliki parent yang sama disebut sibling.
– Degree dari node adalah total sub tree dari node tersebut.
– Height / Depth adalah degree maksimum dari node dalam suatu tree.
– Jika ada garis yang menghubungkan p ke q, maka p disebut ancestor dari q, dan q adalah descendant dari p.

Contoh binary tree yang memiliki 9 node, di mana root / akar-nya berada di node yang mengandung nilai 2. Leaf-nya adalah node-node yang mengandung nilai 2, 5, 11, dan 4.

Tipe-Tipe Binary Tree
– PERFECT binary tree adalah binary tree di mana setiap levelnya berada pada depth yang sama

– COMPLETE binary tree adalah binary tree di mana setiap levelnya, kecuali mungkin yang terakhir, telah terisi sepenuhnya, dan semua node-nya berada di sebelah kiri sejauh mungkin. Perfect binary tree adalah complete binary tree.

– SKEWED binary tree adalah binary tree di mana setiap node memiliki setidaknya 1 child.

– BALANCED binary tree adalah binary tree di mana tidak ada leaf yang berada jauh dari root daripada leaf lainnya (skema balancing yang berbeda memungkinkan definisi berbeda dari kata “jauh lebih jauh / much farther away”).

Properti dari Binary Tree
Jumlah node maksimum dari level k dari suatu binary tree adalah 2^k.
Jumlah node maksimum pada suatu binary tree dari height h adalah 2^h+1 – 1.
Dalam beberapa literatur, level / tingkat binary tree dimulai dengan 1 (root).

Node maksimum dari suatu binary tree dengan height 3 :
= 1 + 2 + 4 + 8
= 2⁰ + 2¹ + 2² + 2³
= 2⁴ – 1 = 15

Height minimum dari suatu binary tree dari node n adalah ²log(n).
Height maksimum dari suatu binary tree dari node n adalah n – 1.

Skewed binary tree memiliki height maksimum.

 

 

Representasi Binary Tree
– Implementasi menggunakan array

Index pada array mewakili angka node.
Index 0 adalah root node.
Index Left Child adalah 2p + 1, di mana p adalah index parent.
Index Right Child adalah 2p + 2.
Index Parent adalah (p – 1) / 2.

– Implementasi menggunakan linked list

struct node
{
int data;
struct node *left;
struct node *right;
struct node *parent;
};

struct node *root = NULL;

 

 

Konsep Expression Tree
Prefix  : *+ab/-cde
Postfix    : ab+cd-e/*
Infix  : (a+b)*((c-d)/e)

Kita akan menggunakan struct ini untuk setiap node di dalam tree :

struct tnode
{
char chr;
struct tnode *left;
struct tnode *right;
};

Membuat Expression Tree dari Prefix
Kita bisa membuat sebuah expression tree dari prefix dengan recursive.

 

 

Prefix & Postfix Traversal
Membuat prefix atau postfix traversal cukup mudah.

Pada prefix, kita harus print / proses sebelum child-nya diproses.

Pada postfix, kita harus print / proses setelah child-nya diproses.

Infix Traversal

Bisakah kode di samping cukup untuk infix traversal?

Kode tersebut kelihatan benar, namun infix memiliki ambiguitas precedence (prioritas) tanpa tanda kurung “()”.
Sebagai contoh :
* + a b c pada prefix akan dikodekan (encode) ke dalam infix menjadi a + b * c dengan kode di atas, sedangkan infix yang benar adalah (a + b) * c.

a + b * c : b dikalikan dengan c, lalu ditambahkan dengan a
(a + b) * c : a ditambahkan dengan b terlebih dahulu, lalu dikalikan dengan c.

Prefix  : *+abc

Postfix  : ab+c*

Infix yang salah  : a+b*c

Infix yang benar  : (a+b)*c

Untuk memperbaikinya, kita dapat menambahkan tanda kurung () saat memperluas operator.
Sehingga * + a b c dalam prefix akan dikodekan menjadi ((a + b) * c) dalam infix, di mana itulah yang benar.