Data Structure - Tree and Binary Tree

TREE  & BINARY TREE

27-3-2018


Binary Tree
Merupakan sebuah pengorganisasian secara hirarki dari beberapa buah node, dimana node tidak memiliki child lebih dari dua masing-masingnya. Binary tree dapat diimplementasikan dengan menggunakan struktur data linked list. Ada tiga bagian pada masing-masing node, yaitu sebuah data atau info dan dua buah pointer yang disebut juga pointer kiri dan kanan.



Tipe-tipe Binary Tree

 - Perfect Binary Tree : Semua adalah node (kecuali daun) memiliki dua child, setiap cabang memiliki panjang dan ruas yang sama.

- Complete Binary Tree : Semua adalah node (keculai daun), hampir mirip seperti perfect binary tree, mempunyai dua child tetapi setiap cabang memiliki panjang ruas yang berbeda.

- Skewed Binary Tree : Adalah dua pohon yang semuanya mempunyai satu child atau sibling.

- Balanced Binary Tree : Adalah binary tree yang tidak memiliki daun lebih dari yang lain.
Contoh Perfect Binary Tree


Contoh Complete Binary Tree

Contoh Skewed Binary Tree


Properti dari Binary Tree
  1. Maksimal jumlah node dalam suatu binary tree adalah 2^n.
  2. Tinggi maksimal dari node binary tree adalah 2^n+1 - 1.
  3. Minimum tinggi dari suatu binary tree dari n node adalah ^2logn.
  4. Maximum tinggi dari suatu binary tree dari n node adalah n-1.








Komentar

Posting Komentar

Postingan populer dari blog ini

Pertemuan 3 - Data Structure

Gambar
Linked List Implementation II Pertemuan 3 Stack adalah struktur data yang tersusun bertumpuk-tumpuk, seperti sebuah tumpukan piring, jika kita ingin mengambil piring terserbut, maka yang paling atas adalah yang pertama kita ambil. Bisa disebut juga bahwa data yang terakhir masuk adalah data yang pertama kali keluar juga dan data tersebut juga yang dapat masuk dan dihapuskan yang biasa disebut TOP. Ada tiga operasi stack, diantaranya adalah: Push = menambah item Pop = data yang paling atas akan diambil Top = data yang paling atas akan ditampilkan. Ada juga fungsi-fungsi lain stack, yaitu: Evaluasi prefix Evaluasi infix Evaluasi postfix Mengubah infix menjadi prefix Mengubah infix menjadi postfix Depth first search Membalikkan urutan data Mengkonveksi infix menjadi postfix Mengkonveksi postfix menjadi infix Dari gambar di atas, kita tahu bahwa angka 2,3,4,5,6,10 merupakan sebuah operand yang mana adalah nilai asal yang dapat digunakan untuk pro...
Baca selengkapnya

Pertemuan 4 - Data Structure

Gambar
Introduction to Tree, Binary Tree, and Expression Tree TREE Tree yang dimaksud disini adalah satu atau lebih dari satu nodes yang disebut Root dan node lainnya, tree dapat juga dibilang sebagai bentuk struktur data tidak linear yang ada berhubungan dengan sifat hirarkis atau one to many antara elemen-elemen. Konsep-konsep tree : Node yang paling atas disebut Root. Garis yang menghubungkan antara parent dengan child  disebut Edge. Node yang tidak memiliki children  disebut Leaf. Sibling adalah sebutan untuk node yang memiliki parent  yang sama. Total dari sub tree  dari node disebut Degree. Degree maksimum dari suatu node dalam tree  disebut Height atau Depth. Binary Tree  Binary tree merupakan data tree yang sudah di root yang mana nodenya memiliki paling banyak dua children, dengan syarat bahwa setiap node hanya boleh maksimal punya dua child, yaitu anak kiri dan kanan. Konsep Binary Tree : Hanya mempunyai dua anak, kiri dan...
Baca selengkapnya