13/12/2013
Binary Tree
Contoh Tree
1
13/12/2013
Struktur Tree • Tree adalah struktur hirarki yang menempatkan elemen pada simpul pada cabang2nya yang dimulai dari root. • Node (simpul) dalam tree dibagi dalam level dari tertinggi yaitu node root • Sembarang node dalam tree dapat mempunyai banyak successor pada level di bawahnya. Sehingga tree adalah struktur non linier
Struktur Tree (lanj) • Sistem operasi menggunakan tree untuk pengelolaan struktur file
2
13/12/2013
Struktur Tree (lanj) • Pada binary tree, setiap node paling banyak mempunyai 2 cabang.
Terminologi Tree • Struktur tree adalah kumpulan node yang dimulai dari node unik yang disebut root. – Setiap node terdiri dari sebuah nilai dan beberapa link ke node di bawahnya – Istilah parent dan child menggambarkan relasi antar node dan succesor nya
3
13/12/2013
Terminologi Tree (lanj)
Terminologi Tree (lanj) root A
child
sibling parent B
C
D
interior (internal) node E
F
G
H
leaf node I
J
subtree
4
13/12/2013
Terminologi Tree (lanj) • Jalur antara parent node P dan sebuah node N dalam subtree adalah deretan node P=X0, X1, . . ., Xk = N dimana k adalah panjang jalur. Setiap node Xi dalam deretan tsb adalah parent dari Xi+1 untuk 0 ≤ i ≤ k-1. – Level dari sebuah node adalah panjang jalur dari root ke node. Bayangkan node sebagai root dari subtree, tinggi (height) node adalah panjang dari jalur terpanjang dari node ke leaf dalam subtree – Tinggi tree adalah level maksimum dalam tree.
Terminologi Tree (lanj)
5
13/12/2013
Binary Tree • Pada binary tree, setiap parent tidak mempunyai anak lebih dari 2 • Binary tree mempunyai struktur seragam yang menggambarkan struktur node yang sederhana dan pengembangan untuk beberapa algoritma tree
Binary Tree (lanj) • Setiap node pada binary tree mempunyai subtree left dan right. Setiap subtree merupakan tree Right child of T Left child of T
6
13/12/2013
Binary Tree (lanj) • Alternatif definisi rekursif dari binary tree: – T adalah binary tree jika T • Tidak mempunyai node (T adalah tree kosong) atau • Mempunyai paling banyak two subtree.
Binary Tree (lanj)
7
13/12/2013
Tinggi (Height) Binary Tree • Tinggi binary tree adalah panjang dari jalur terpanjang dari rott ke node leaf. Misalnya TN adalah subtree dengan root N dan TL dan TR adalah root dari subree kiri dan kanan dari N. height(N) = height(TN) =
{
-1 1+max( height(TL), height(TR))
if TN is empty if TN not empty
Tinggi (Height) Binary Tree (Hasil)
Degenerate binary tree
8
13/12/2013
Density (Kepadatan) Binary Tree • Dalam binary tree, jumlah node setiap node berada pada jangkauan nilai tertentu – Pada level 0, terdapat 1 node yaitu root; pada level 1 terdapat 1 atau 2 node. – Pada sembarang level k, jumlah node dalam jangkauan dari 1 ke 2k. – Jumlah node per level merupakan kepadatan tree. Density adalah ukuran tree (jumlah node) relatif terhadap tinggi tree
Density (Kepadatan) Binary Tree
9
13/12/2013
Density (Kepadatan) Binary Tree (lanj) • complete binary tree dari tinggi h mempunyai semua kemungkinan node melalui level h-1, dan node pada kedalaman h terdapat cabang kiri dan kanan yang penuh.
Density (Kepadatan) Binary Tree (lanj)
10
13/12/2013
Density (Kepadatan) Binary Tree (lanj) • Tentukan tinggi minimum dari complete tree yang mempunyai n elemen – Melalui level h - 1 pertama, jumlah node adalah 1 + 2 + 4 + ... + 2h-1 = 2h - 1 – Pada kepadatan h, jumlah node tambahan dalam jangkauan dari minimum 1 sampai maksimum 2h. – Sehingga jumlah node dalam complete binary tree dengan tinggi h berada pada jangkauan 2h - 1 + 1 = 2h ≤ n ≤ 2h - 1 + 2h = 2h+1 - 1 < 2h+1
Density (Kepadatan) Binary Tree (lanj) • Sehingga didapatkan h ≤ log2 n < h+1 dan menghasilkan complete binary tree dengan n node harus mempunyai tinggi h = int(log2n)
11
13/12/2013
Density (Kepadatan) Binary Tree (hasil)
Number of elements (n)
Calculation (log2n)
Height (h = int(log2n))
10
log2 10 = 3.321
int(3.321) = 3
5000
log25000 = 12.287
int(12.287) = 12
1000000
log2 1000000 = 19.931
int(19.931) = 19
Node Binary Tree • Buat node binary tree sebagai anggota dari class generic TNode class. – Sebuah node terdiri dari 3 field. • data value, dinamakan nodeValue. • Variabel referensi, left dan right yang menyatakan left child dan right child
12
13/12/2013
Node Binary Tree (lanj)
Class TNode public class TNode
{ // node's value public T nodeValue; // subtree references public TNode left, right; // create instance with a value and null subtrees public TNode(T item) { nodeValue = item; left = right = null; } // initialize the value and the subtrees public TNode (T item, TNode left, TNode right) { nodeValue = item; this.left = left; this.right = right; } }
13
13/12/2013
Membangun Binary Tree • Binary tree terdiri dari collection obyek TNode objects yang mereferensi nilai ke link anak tertentu. Membangun binary tree per satu node TNode p, q;
// references to TNode objects with // Integer data // p is a leaf node with value 8; p = new TNode(8); // q is a node with value 4 and p as a right child q = new TNode(4, null, p);
Membangun Binary Tree (lanj) • Menggunakan class TNode untuk membangun binary tree dari bawah ke atas. // references to Integer tree nodes TNode root, p, q, r; // create leaf node p with value 20 // and leaf node q with value 40 p = new TNode(20); q = new TNode(40); // create internal node r with value 30, // left child q, and a null right child r = new TNode(30, q, null); // create root node with value 10, // left child p, and right child r root = new TNode(10, p, r);
14
13/12/2013
Membangun Binary Tree (lanj) // n is in the range 0 to 2 public static TNode buildTree(int n) { ... }
Algoritma Penelusuran Binary Tree dengan Rekursif • Untuk menelusuri tree secara rekursif, kita harus mengunjungi node (N), menelusuri subtree kiri (L), dan menelusuri subtree kanan (R). Urutan N, L, R menentukan algoritma penelusuran
15
13/12/2013
Penelusuran Inorder • Penelusuran inorder dari tree mengujungi subree kiri L, mengunjungi node N, kemudian mengunjungi subtree kanan R. Penelusuran dimulai dari root
Scan order: B D A E C
Contoh Penelusuran Rekursif Preorder (NLR): Inorder (LNR): Postorder (LRN):
A D G
B G D
D B B
G A H
C H I
E E E
H I F
I C C
F F A
16
13/12/2013
Metode Penelusuran Rekursif public static ReturnType scanMethod(TNode t) { // check for empty tree (stopping condition) if (t == null) < return information for an empty tree > else { // descend to left subtree and record return information valueLeft = scanMethod(t.left); // visit the node and record information < evaluate t.nodeValue > // descend to right subtree and record return information valueRight = scanMethod(t.right); } return }
Metode Penelusuran Rekursif (lanj) Preorder Design Pattern: <evaluate t.nodeValue> valueLeft = scanMethod(t.left); valueRight = scanMethod(t.right);
// visit node first // go left // go right
Postorder Design Pattern: valueLeft = scanMethod(t.left); valueRight = scanMethod(t.right); <evaluate t.nodeValue>
// go left // go right // visit node last
17
13/12/2013
Metode Penelusuran Rekursif (lanj) // list the nodes of a binary tree using an LNR scan public static void inorderOutput(TNode t) { // the recursive scan terminates on an empty subtree if (t != null) { inorderOutput(t.left); // descend left System.out.print(t.nodeValue + " "); inorderOutput(t.right); // descend right } }
Metode Penelusuran Rekursif (lanj) // list the nodes of a binary tree using an LNR scan public static String inorderDisplay(TNode t) { // return value String s = ""; // the recursive scan terminates on a empty subtree if (t != null) { s += inorderDisplay(t.left); // descend left s += t.nodeValue + " "; // display the node s += inorderDisplay(t.right); // descend right } return s; }
18
13/12/2013
Latihan 1 • Bagaimana urutan preorder, inorder dan postorder dari binary tree di bawah ini?
Latihan 2 • Bagaimana urutan preorder, inorder dan postorder dari binary tree di bawah ini?
19
