Tree

Tree merupakan salah satu bentuk struktur data bukan linier yang menggambarkan bentuk hierarki antara elemen-elemen. Tree biasanya terdiri dari root (akar) dan node-node (simpul-simpul) yang berada di bawah root. Struktur seperti tree sangat banyak sekali dgunakan dalam dunia nyata, misalnya: struktur organisasi suatu perusahaan, pengaturan filesystem, daftar isi sebuah buku, dan masih banyak lagi.

Ilustrasi struktur data tree:

Degree (derajat) adalah jumlah edge yang keluar dan masuk dari sebuah node.
Contoh : node E memiliki in degree 1 dan out degree 2

Root (akar) adalah node yang memiliki derajat keluar >=0 dan derajat masuk = 0.
Contoh : node A adalah root

Subtree / child adalah bagian salah satu node dibawah root sampai ke bawah.
Contoh : tree C adalah right subtree dari A dan tree B merupakan left subtree dari A
node G dan F merupakan child dari node C
node F merupakan parent dari node J dan K

Ancestor adalah Node yang berada di atas node lain.
Contoh : node B adalah ancestor dari node E
Descendant adalah node yang berada di bawah node lain.
Contoh : node E adalah descendant dari node A.

Leaf (daun) adalah semua node yang derajat masuknya 1 dan derajat keluarnya 0.
Contoh : node D, H, I, J, K, dan G adalah leaf

Sibling adalah node yang mempunyai level yang sama dan parent yang sama.
Contoh : node D adalah sibling dari node A
Height (ketinggian) adalah level tertinggi dari tree ditambah 1.
Contoh : height dari tree A adalah 3 + 1 = 4

Weight (bobot) adalah jumlah leaf(daun) pada tree.
Contoh : weight dari tree A adalah 6


BINARY TREE
Sebuah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal 2 subtree yang disebut sebagai subpohon kiri(left subtree) dan subpohon kanan (right subtree) dan kedua subtree tersebut harus terpisah, atau dengan kata lain tiap node dalam binary tree hanya boleh memiliki paling banyak 2 child.

Binary tree terdiri dari :
1. Full Binary Tree : semua node (kecuali leaf pasti memiliki 2 anak dan tiap subtree memiliki panjang path yang sama)
2. Complete Binary Tree : mirip dengan full binary tree, tetapi tiap subtree boleh memiliki panjang path yang berbeda dan tiap node (kecuali leaf memiliki 2 anak)
3. Skewed Binary Tree : binary tree yang semua nodenya (kecuali leaf) hanya memiliki satu anak


BINARY SEARCH TREE
Binary tree dengan sifat bahwa nilai dari semua left child harus lebih kecil daripada nilai dari right child dan parentnya.
Contoh :
42 77 60 90 85 97 50 25 35 15 10 5

Contoh Implementasi Binary Search Tree :