Tree = Collection of one or more nodes

Istilah di dalam tree :
-Parent
-Children
-Sibling
-Ancestor
-Descendant
-Root
-Edge
-Leaf

Root = Top of tree
Edge = Garis yang menghubungkan 2 buah node.
Leaf = Node yang tidak mempunyai satupun anak(node yang dihubungkan dengan edge yang berada dibawahnya).

Parent : Sebuah node yang merupakan orang tua dari node yang dibawahnya (memiliki edge ke node dibawahnya).

Children : Sebuah/beberapa node yang merupakan anak dari sebuah node parent (berada 1 tingkat dibawah parent) yang terikat pada edge yang sama.

Sibling : Beberapa node yang mempunyai/terhubung pada parent yang sama.

Ancestors : Node-node yang berada diatas sebuah node yang ditunjuk yang masih memiliki koneksi edge dengan node yang ditunjuk (parent , parent dari “parent” , parent dari “parent dari parent” sampai ke top).

Descendant : Node-node yang berada dibawah sebuah node yang dipilih yang masih terdapat edge yang dapat menghubungkan node yang dipilih ke node-node tersebut secara terus menerus kebawah (sampai ke leaf).

BINARY TREE

Binary tree mempunyai 4 tipe :
Perfect
Complete
Skewed
Balance

BT = Binary Tree;

Perfect BT : Binary tree yang semua parentnya memiliki 2 anak terkecuali leaf nya(leaf = tidak mempunyai anak sama sekali). Perfect BT juga termasuk kedalam complete BT.

Complete BT : Binary tree yang semua parentnya memiliki 2 anak terkecuali node yang berada 1 tingkat diatas tingkat leaf (1 tingkat diatas leaf = perfect BT , dengan tambahan leaf leaf dibawah nya , maka tidak menjadi perfect lagi melainkan menjadi complete).

Skewed BT : Binary tree parentnya sama sekali tidak ada yang memiliki 2 anak . satu node hanya mempunyai satu anak atau bahkan tidak ada sama sekali.

Balance BT : Binary tree yang mempunyai jumlah node , jumlah parent , jumlah leaf yang sama pada sisi kanan dan kiri sebuah BT. Terhitung dari node node descendant yang dimiliki oleh kedua anak dari root , anak 1 = sisi kiri , anak 2 = sisi kanan ataupun sebaliknya.

Cara menghitung maksimum node :
Maksimum node baris baling bawah (maximum leaf) pada sebuah binary tree adalah 2^k dimana k adalah level dimulai dari 0 (top/root) dan naik satu setiap keturunan.

Maksimum seluruh node sebuah BT dapat dihitung dengan 2^k+1-1  dimana jumlah maksimum node = jumlah node pada perfect binary tree.

Minimum height of binary tree of n nodes is ²log(n)

Maximum height of binary tree of n nodes is n-1 , dimana maksimum height adalah skewed binary tree.

Implementasi Binary tree :
Binary tree juga menjadi dasar dari David A Huffman , seorang mahasiswa di MIT untuk membuat code kompressi seperti yang terkenal winrar atau winzip sekarang , sekarang code kompresi disebut huffman codes <- Search google for more info.