1.PENGERTIAN TREE DAN BINARY

• Tree merupakan salah satu struktur data yang paling penting, karena banyak aplikasi menggunakan informasi dan data yang secara alami memiliki struktur hirarkis berguna dalam membantu memecahkan banyak masalah algoritmis.

BINARY TREE

Karakteristik : Maksimum child adalah 2 (Left Child dan Right Child)

Complete Binary Tree :

Bila semua node kecuali Leaf memiliki 0 atau 2 child. Subtree pada Heap

Tree dapat memiliki path length yang berbeda

Skewed Binary Tree (Miring) :

Bila semua node, kecuali Leaf memiliki hanya 1 child

Full Binary Tree :

Bila semua node kecuali Leaf memiliki 2 Child dan semua subtree harus

memiliki path yang sama

Representasi :

- Ekspresi MM dengan Binary Tree

- Huffman Code

​

Implementasi Binary Tree :

a. Array

b. Linked List

Implementasi BT pada array :

- Indeks pada array menyatakan nomor kode

- Node root mempunyai indeks array = 1

- Leftchild suatu node dengan nomor p adalah (2p)

- Rightchild suatu node dengan nomor p adalah (2p+1)

- Parent dari suatu node dengan nomor p adalah (p div 2)

​

2.Uraian umum dalam tree

• JENIS-JENIS TREE
• BINARY TREE
• Tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua sub
• pohon dan kedua subpohon harus terpisah.
• Kelebihan struktur Binary Tree :
• Mudah dalam penyusunan algoritma sorting
• Searching data relatif cepat
• Fleksibel dalam penambahan dan penghapusan data

​

3. Contoh program tree

Pengertian AVLtree

• AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.

CONTOH AVL

Jenis-jenis tree

• ) Prodecessor : node yang berada diatas node tertentu.
• b) Successor : node yang berada di bawah node tertentu.
• c) Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.
• d) Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.
• e) Parent : predecssor satu level di atas suatu node.
• f) Child : successor satu level di bawah suatu node.
• g) Sibling : node-node yang memiliki parent yang sama dengan suatu node.
• h) Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.

​

• Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.