binary tree

Tree adalah salah satu bentuk struktur data tidak linear yang menggambarkan hubungan dan bersifat hirearki.

Binary Tree adalah tree yang mempunyai syarat bahwa tiap node maksimal memiliki dua subtree dan kedua subtree itu haruslah terpisah.
Binary Search Tree adalah sebuah konsep penyimpanan data, dimana data disimpan dalam bentuk tree yang setiap node dapat memiliki anak maksimal 2 node. Aturannya yaitu anak bagian kiri dari sebuah parent yang sama harus memiliki nilai lebih kecil daripada anak bagaian kanan.


jenis-jenis binary tree:
a)Perfect Binary Tree
Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.
b)Complete Binary Tree
Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child
c)Skewed Binary Tree
yakni Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.


Binary tree search ( BST )
Struktur data yang mengadopsi konsep binary tree namun terdapat aturan bahwa setiap child (anak ) node sebelah kiri selalu lebih kecil nilainya dari pada root node. yang artinya Jika nilai selanjutnya lebih kecil dari parentnya makan di letakan disebelah kiri dan jika lebih besar makan diletakan di sebelah kanan.


Binary search Operation
Operation dari binary search tree ada 3 yaitu :
- Find(x) : Untuk mencari BST (Binary search tree )
- Insert : Untuk menambahkan BST
- Remove : Untuk menghapus BST

Operations: Search
Mencari binari search tree tidak susah kita mulai dari root. Root adalah node pertama dalam sebuah binary tree. Contoh yang ingin kita cari adalah x dan pada root berisi x, maka pencarian akan berakhir. Jika x lebih kecil dari kunci root, maka cari secara rekursif pada sub pohon pada bagian kiri, jika tidak ada makan kita akan mencari secara rekursif disub pohon bagian kanan.
Algorithm:
struct node* search (struct node *curr, int X) {
if ( curr == NULL ) return NULL;
// X is found
if ( X == curr->data ) return curr;
// X is located in left sub tree
if ( X < curr->data ) return find(curr->left, X);
// X is located in right sub tree
return find(curr->right, X);
}

Operations: Insertion
Insert pada binary search tree juga dilakukan dengan cara rekursif. Contoh kita akan membuat simpul baru yang bernilai X. Maka mulailah searching dari root. Jika X lebih kecil dari root maka masukan X ke dalam sub pohon bagian kiri, dan jika nilai X lebih besar dari root maka masukan X kedalam bagian sub pohon kanan. X akan selalu berupa daun baru.
Algorithm:
Step 1: IF TREE = NULL, then
Allocate memory for TREE
SET TREE->DATA = VAL
SET TREE->LEFT = TREE ->RIGHT = NULL
ELSE
IF VAL < TREE->DATA
Insert(TREE->LEFT, VAL)
ELSE
Insert(TREE->RIGHT, VAL)
[END OF IF]
[END OF IF]
Step 2: End

Operations: Deletion
Ada 3 hal yang harus kita pertimbakan pada operation delete ini :
Jika yang akan kita hapus adalah daun, maka dapat langsung di hapus.
Jika yang akan kita hapus adalah node yang memiliki satu anak, maka hapus node itu dan hubungkan anaknya ke induknya.
Jika yang akan kita hapus adalah node yang memiliki dua anak, maka temukan anak paling kanan dari sub pohon kiri (simpul P), ganti node yang akan kita hapus dengan P dan keluarkan P secara rekursif.
Algorithm:
Step 1: IF TREE = NULL, then
Write “VAL not found in the tree”
ELSE IF VAL < TREE->DATA
Delete(TREE->LEFT, VAL)
ELSE IF VAL > TREE->DATA
Delete(TREE->RIGHT, VAL)
ELSE IF TREE->LEFT AND TREE->RIGHT
SET TEMP = findLargestNode(TREE->LEFT)
SET TREE->DATA = TEMP->DATA
Delete(TREE->LEFT, TEMP->DATA)
ELSE
SET TEMP = TREE
IF TREE->LEFT = NULL AND TREE ->RIGHT = NULL
SET TREE = NULL
ELSE IF TREE->LEFT != NULL
SET TREE = TREE->LEFT
ELSE
SET TREE = TREE->RIGHT
FREE TEMP
Step 2: End