Minggu, 03 Mei 2020


AVL TREE & B – TREE


AVL – TREE
AVL TREE merupakan kepanjangan dari Adelson Veleskii Landis Tree. AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. Dengan Balanced Binary Search Tree, kita dapat membuat suatu tree dengan tinggi minimum. Untuk menetapkan tingginya, kita dapat menggunakan rumus berikut:
O(log n)
Penerapan struktur data AVL tree digunakan pada Binary Search Tree bertujuan untuk menyeimbangkan tree tersebut, sehingga waktu pencarian dan struktur tree dapat disederhanakan.


 Insert AVL TREE
Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu :

1.      Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)
2.      Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)
3.      Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)
4.      Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)
T adalah node yang harus diseimbangkan kembali.
4 kasus tersebut dapat diselesaikan dengan melakukan rotasi yaitu:
1.      Kasus 1 dan 2 dengan single rotation
2.      Kasus 3 dan 4 dengan double rotation

Single rotation
Single rotasi (rotasi 1x) dilakukan apabila searah, left-left atau right-right.
Contoh Single Rotation :


Jika suatu Tree diinsert node baru dengan nilai 12, maka akan terjadi ketidak seimbangan dan hal ini terletak pada posisi root.

Double rotation
Double rotasi (rotasi 2x) dilakukan apabila searah, left-right atau right-left.
Contoh Double Rotation :

Gambar diatas merupakan kasus left – right

Delete AVL TREE
Deletion dalam AVL Tree sama seperti teknik deletion dalam binary search tree yang tidak seimbang.
Ada 2 kasus yang biasanya terjadi saat operasi delete dilakukan yaitu :
1.      Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus.
2.      Jika node yang akan dihapus memiliki anak, maka proses penghapusannya harus di cek kembali untuk menyeimbangkan Binary Search Tree dengan perbedaan tinggi / level maksimal 1.
Anggap T adalah node yang harus diseimbangkan kembali
·         Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)
·         Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)
·         Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)
·         Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)

Contoh:



B - TREE
B-Tree merupakan pengembangan dari 2-3 Tree. Sehingga aturan-aturan yang berlaku pun mirip.
Berikut beberapa hal yang perlu diketahui mengenai B-Tree:
·         M adalah jumlah order tree tersebut. (Contoh: order 4 mempunyai maksimal 3 node dan 4 child).
·         Semua "Leaf" berada level yang sama.
·         Setiap Node (kecuali root) punya minimal M/2 children.
·         Root memiliki paling tidak 2 children (bila bukan leaf)
·         Node tanpa leaf dengan k anak mengandung kunci k-1
·         Semua data yang disimpan dalam urutan yang diurutkan.

2 – 3 Tree
2-3 Tree adalah salah satu tipe struktur data, dimana setiap node dengan anaknya, memiliki 2 children dan 1 elemen data (2 node) atau 3 children dan 2 elemen data (3 node).
Sifat-sifat 2-3 Tree :
·         Setiap non-leaf terdapat 2-node atau 3-node. Sebuah 2-node berisi satu item data dan memiliki dua anak/children (anak kiri dan anak tengah). Sebuah 3-node berisi dua item data dan memiliki 3 anak/children (anak kiri, tengah, dan kanan).
·         Semua leaf berada di level yang sama (level bawah/bottom level).
·         Semua data yang disimpan akan diurutkan :
o   Misalkan A adalah data yang tersimpan di 2-node. Subtree kiri harus berisi data yang nilainya lebih kecil dari A. Subtree tengah harus berisi data yang nilainya lebih besar dari A.
o   Misalkan A dan B adalah data yang tersimpan di 3-node. Subtree kiri harus berisi data yang nilainya kurang dari A. Subtree tengah berisi nilai antara A dan B, dan subtree kanan berisi nilai yang lebih dari B.




Contoh :
Gambar diatas merupakan contoh 2 – node yaitu node yang berisi 1 data dan mempunyai 2 child


Insert
Syarat insertion yaitu:
·         Pertama tentukan dahulu dimana key akan diletakkan menggunakan algoritma search, key pasti ditempatkan pada node leaf.
·         Jika node tadi adalah 2-node, maka letakkan saja key tersebut disitu.
·         Jika nodenya adalah 3-node, maka jadikan data tengah dari key, A, dan B (A dan B adalah data yang sudah ada sebelumnya di dalam node), menjadi parent, dan split 2 data tersisa menjadi 2 buah 2-node. Cek apakah parent adalah 3-node, jika iya maka ulangi langkah 3 sampai parent menjadi 2-node.
Contoh:


Delete
Syarat Deletion yaitu:
·         Tentukan di node mana data yang ingin dihapus
·         Jika berada dalam 3-node, langsung hapus saja datanya.
·         Jika berada dalam 2-node :
o   Jika parent adalah 3-node : ambil satu data dari parent.
Jika sibling adalah 3-node, ambil salah satu data nya untuk  dijadikan data pada parent (agar parent menjadi 3-node lagi).
Jika sibling adalah 2-node, buat parent menjadi 2-node dengan menggabungkan (merge) sibling dengan node tempat data didelete.
o   Jika parent adalah 2-node : Jika sibling adalah 3-node, turunkan data parent ke node dan ambil satu data dari sibling untuk menggantikan parent. Jika sibling 2-node, gabungkan sibling dengan node yang dihapus datanya.
Contoh:


Pada gambar diatas, misalkan yang ingin di delete adalah angka 15 maka langsung di hapus karena 15 merupakan leaf.




Sumber:
https://socs.binus.ac.id/2016/12/20/insertion-avl-tree/
https://socs.binus.ac.id/2017/05/15/deletion-avl-tree/
http://strukturdatatugas.blogspot.com/2016/05/rangkuman-pertemuan-6.html
http://sysbreaker.blogspot.com/2014/05/b-tree-dan-heap-deap-tree.html
http://alecatmadja.blogspot.com/2011/06/2-3-tree-part-1.html
http://nurahman11.blogspot.com/2011/06/deletion-2-3-tree.html
https://www.geeksforgeeks.org/2-3-trees-search-and-insert/




Senin, 30 Maret 2020

Rangkuman Semester 2 Data Struct



Ringkasan Data Struct

Single Linked List
Linked List atau senarai berantai adalah struktur data yang dibangun dari satu atau lebih node yang menempati lokasi memori secara dinamis dan disusun saling sambung – menyambung. Single Linked List adalah kumpulan dari node yang saling berhubungan dengan node lain melalui sebuah pointer(next).
Macam – macam pointer yang terdapat dalam single linked list:
  • Head : elemen yang berada pada posisi pertama dalam suatu linked list
  • Tail : elemen yang berada pada posisi terakhir dalam suatu linked lis
  •  Curr : elemen yang berada pada linked list dan pointer ini bisa pindah - pindah
  • Next

Memory allocation dynamic
JIka memerlukan untuk mengalokasikan memori secara dinamis(dalam runtime) dapat menggunakan malloc di C/ C++
Rumus:
                Curr = (struct data*)malloc(sizeof(struct data));
Keterangan : data di warnai merah artinya bisa dinamai apa aja

Single linked list ketika belum ada data (ketika head == NULL)
curr ->angka = data; (misalkan diketahui int angka)
head = curr;
tail = curr;
tail ->next = NULL

Single linked list insert menambah data di bagian belakang
tail -> next = curr;
curr -> tail;
tail -> next = NULL;

Single linked list insert menambah data  di bagian depan
curr -> next = head;
head = curr;

Single linked list insert menambah data di tengah
x -> next = curr;
curr -> next = y;
x = head;
while(x -> next -> angka > curr ->angka){
      x = x -> next;
}
y = x -> next;
x -> next = curr;
curr -> next = y;
Keterangan : x dan y adalah pointer baru

Single Linked List delete depan
if(head ->angka==x){
               curr = head;
               head = head->next;
               free(curr);
}
Ket : angka = deretan dari banyak angka , x = nilai yang dihapus

Single Linked List delete tengah
If(tail->angka==x){
              curr = head;
              while(curr->next!=tail){
                   curr= curr->next;
             }
             free(tail);
             tail=curr;
             tail->next = NULL;
}
Ket : angka = deretan dari banyak angka , x = nilai yang dihapus

Single Linked List delete belakang
curr = head;
while(curr->next->score!=x){
     curr = curr->next;
}
temp = curr->next;
curr->next=temp->next;
free(temp);
Ket : angka = deretan dari banyak angka , x = nilai yang dihapus


Double Linked List
Double linked list adalah linked list dengan node yang memiliki data dan dua buah pointer(next dan prev) yang menunjuk ke node sebelum dan node sesudah.
Macam – macam pointer yang terdapat dalam double linked list :
  • Head : elemen yang berada pada posisi pertama dalam suatu linked list
  • Tail : elemen yang berada pada posisi terakhir dalam suatu linked list
  • Curr : elemen yang berada pada linked list dan pointer ini bisa pindah - pindah
  • Next
  • Prev

Contoh syntax untuk double linked list (dari kelas LAB)





Stack & Queue
Stack
Stack(tumpukan) artinya data yang pertama kali masuk, maka data tersebut paling akhir keluar.
Contoh : tumpukan piring.
Stack dapat diimplementasikan menggunakan array (ada batasannya) dan linked list(tidak ada batasan/ unlimited).
Elemen – elemen yang ada di stack dapat ditambahkan dan dihapus hanya dari satu ujung yaitu bagian atas.
Data disimpan dengan cara Last In First Out (LIFO).
Macam – macam stack operations :
  •  Push(x) : memasukkan data ke dalam stack.
  • Pop() : menghapus elemen yang terletak pada posisi paling atas dati sebuah tumpukan.
  • Top() :  mengembalikan(return) data teratas dari tumpukan.

Infix, Postfix, dan Prefix Notation
  • Prefix   : Operator yang di tulis sebelum operan ( operator operand operand)
  • Contoh : * 4 10
  • Infix     : Operator yang ditulis antara operan ( operand operator operand)
  • Contoh: 4 * 10
  • Postfix : Operator yang ditulis setelah operan (operand operand operator)
  • Contoh : 4 10 *

Queue
Queue(urutan) artinya data yang pertama kali masuk maka data tersebut akan pertama kali keluar.
Queue dapat diimplementasikan dengan menggunakan array atau linked list.
Elemen – elemen dalam queue ditambahkan di satu ujung yang disebut bagian belakang dan dihapus dari ujung lain yang disebut depan.
Data yang disimpan dengan cara First in First Out (FIFO).
Macam – macam queue operations:
  • Push(x)     : menambahkan item x ke belakang antrian
  • Pop()         : menghapus item dari depan antrian
  • Front()      : mengungkapkan / mengembalikan item paling depan dari antrian.


Depth First Search (DFC)
Depth First Search (DFC) adalah suatu algoritma untuk melintasi atau mencari di pohon atau grafik. DFD dapat diimplementasikan dengan fungsi rekursif atau iterative produce menggunakan stack, hasilnya mungkin memiliki sedikit perbedaan pesanan kunjungan tetapi keduanya benar. Proses pencarian pada algoritma DFC akan dilakukan pada semua anaknya terlebih dahulu, sebelum dilakukan pencarian ke node – node yang selevel.
Deques
Deques adalah suatu daftar/list dimana elemen yang digunakan untuk memasukkan(insert) atau menghapus(delete) di bagian kedua ujungnya yaitu head dan tail.

Priority Queue
Ada 2 aturan umum untuk memproses priority queue adalah:
Elemen dengan prioritas lebih tinggi adalah proses sebelum elemen dengan prioritas lebih rendah.
Dua elemen dengan prioritas yang sama diproses berdasarkan FCFS.

Breadth First Search(BFC)
Breadth First Search adalah metode pencarian yang dilakukan dengan mengunjungi setiap node secara sistematis pada tiap setiap level hingga keadaan tujuan ditemukan. Atau algoritma untuk melintasi atau mencari di pohon atau grafik.


Hashing
Hashing adalah teknik yang digunakan untuk menyimpan dan mengambil kunci dengan cepat. Tujuan hashing adalah sebagai metode untuk menyimpan data dalam sebuah array agar penyimpanan data, pencarian data, penambahan datam dan penghapusan data dapat dilakukan dengan cepat.
Hash table adalah salah satu struktur data yang digunakan dalam penyimpanan data sementara. Hash table menggunakan memori penyimpanan utama berbentuk  array dengan tambahan algoritma untuk mempercepat pemrosesan data.
Hash Function adalah suatu fungsi sederhana untuk mendaoatkan nilai hash dari nilai kunci(key value) suatu data.
Ada beberapa hal dalam membuat hash function antara lain :
  • Ukuran array/ table size (m)
  • Key value/ nilai yang di dapat dari data (k)
  • Hash value/ hash index/index yang dituju (h)

Beberapa metode pentuk untuk membangun hash functions antara lain:
  • Mid – Square
  • Metode Mid-Square yaitu teknik hashing di mana kunci unik dihasilkan.

·         Division (most common)
Metode division yaitu Jumlah lokasi memori tersedia dihitung , kemudian jumlah tersebut digunakan sebagai pembagi untuk membagi nilai yang asli dan menghasilkan sisa(nilai hashnya). Secara umum rumus division sebagai berikut :
                                                                                h(z) = z mod M
Keterangan:
z          = key/ suatu lokasi  memori yang beralamat h(z)
M        = jumlah lokasi memori yang tersedia pada array

·         Folding
Metode folding terbagi menjadi dua langkah yaitu :
Ø  Bagi nilai kunci menjadi beberapa bagian dimana setiap bagian memiliki jumlah digit yang sama kecuali bagian terakhir yang mungkin memiliki angka lebih sedikit daripada bagian lainnya.
Ø  Tambahan bagi individu. Yaitu memperoleh jumlah part 1 + part 2 + .. + part n. Nilai hash yang dihasilkan dengan mengabaikan carry terakhir, jika ada.

·         Digit Extraction
Metode digit extraction yaitu mendapatkan hash key dengan cara mengambil digit – digit tertentu dari sebuah string untuk dijadikan hash keynya.

·         Rotating Hash
Metode Rotating Hash yaitu mendapatkan hash key maka di lakukan rotasi untuk menggeser digit sehingga menemukan alamat hash key baru.

Dalam penyimpanan data di Hash Table sangat dimungkinkan 1 index menyimpan lebih dari 1 data, hal ini disebut denan Collision. Ada 2 cara untuk menangani collision yaitu :
·         Linear Probing
Mencari slot kosong berikutnya dan letakkan string disana.
·         Chaining
Masukkan string ke dalam slot sebagai chained list(linked list).

Tree  & Binary Tree
Tree adalah salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lainnya (disebut subtree).
Jenis – jenis binary tree:
·         Perfect binary tree
Adalah binary tree yang setiap level berada pada kedalaman/ depth yang sama.
·         Complete binary tree
Adalah binary tree yang setiap levelnya kecuali yang terakhir semua telah terisi penuh dan setiap nodesnya paling panjang ke kiri.
·         Skewed binary tree
Adalah binary tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.
·         Balanced binary tree
Adalah binary tree yang dimana yang setiap leafnya sama jauhnya dari root

Binary Search Tree (BST)
Binary Search Tree adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap clild node sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node.
Aturan main Binary Search Tree :

  • Setiap child node sebelah kiri harus lebih kecil nilainya daripada root nodenya.
  • Setiap child node sebelah kanan harus lebih besar nilainya daripada root nodenya.
Syntax Binary Search Tree







Kamis, 12 Maret 2020

Hashing & Binary Tree


Hashing & Hash Tables
Hashing
Hashing adalah teeknik yang digunakan untuk menyimpan dan mengambil kunci dengan cepat. Tujuan hashing adalah sebagai metode untuk menyimpan data dalam sebuah array agar penyimpanan data, pencarian data, penambahan datam dan penghapusan data dapat dilakukan dengan cepat.

Hash Table
Hash table adalah salah satu struktur data yang digunakan dalam penyimpanan data sementara. Hash table menggunakan memori penyimpanan utama berbentyj array dengan tambahan algoritma untuk mempercepat pemrosesan data.

Hash Function
Hash Function adalah suatu fungsi sederhana untuk mendaoatkan nilai hash dari nilai kunci(key value) suatu data.
Ada beberapa hal dalam membuat hash function antara lain :
·        Ukuran array/ table size (m)
·        Key value/ nilai yang di dapat dari data (k)
·        Hash value/ hash index/index yang dituju (h)
Beberapa metode pentuk untuk membangun hash functions antara lain:
  • Mid – square
  • Division (most common)
  • Folding
  • Digit Extraction
  • Rotating Hash

Mid – square
Mid-Square hashing adalah teknik hashing di mana kunci unik dihasilkan. Dalam teknik ini, nilai benih diambil dan dikuadratkan. Kemudian, beberapa digit dari tengah diekstraksi. Angka-angka yang diekstrak ini membentuk angka yang diambil sebagai benih baru. Teknik ini dapat menghasilkan kunci dengan keacakan tinggi jika nilai benih yang cukup besar diambil. Namun, itu memiliki batasan. Saat bijinya dikuadratkan, jika angka 6-digit diambil, maka persegi akan memiliki 12-digit. Ini melebihi kisaran tipe data int. Jadi, overflow harus diurus. Jika terjadi overflow, gunakan tipe data int panjang atau gunakan string sebagai perkalian jika luapan masih terjadi. Kemungkinan tabrakan di tengah-tengah hashing rendah, tidak usang. Jadi, dalam peluang, jika tabrakan terjadi, itu ditangani menggunakan beberapa peta hash.
Contoh:
Nilai
Di kuadratkan
Nilai di ekstraksi
4765
22705225
7052
3725
13875625
8756


Algoritma dalam mid – square
  • Pilih nilai seed. Ini adalah langkah penting karena untuk nilai seed yang sama, urutan nomor acak yang sama dihasilkan.
  • Ambil kuadrat dari nilai seed dan perbarui seed dengan jumlah digit tertentu yang terjadi di square. Catatan: Semakin besar jumlah digit, semakin besar keacakannya.
  • Kembalikan kuncinya.

Division
Jumlah lokasi memori tersedia dihitung , kemudian jumlah tersebut digunakan sebagai pembagi untuk membagi nilai yang asli dan menghasilkan sisa(nilai hashnya).
Secara umum rumus division sebagai berikut :
h(z) = z mod M
Keterangan:
z          = key/ suatu lokasi  memori yang beralamat h(z)
M        = jumlah lokasi memori yang tersedia pada array
Contoh:
Ukuran table = 97

COBB
Abjad
Nilai ASCII
C
67
O
79
B
66
B
66
total
278
H(z) = 278 mod 97 = 84

HIKE
Abjad
Nilai ASCII
H
72
I
73
K
75
E
69
total
289
H(z) = 289 mod 97 = 95

ABCD
Abjad
Nilai ASCII
A
65
B
66
C
67
D
68
total
266
H(z) = 278 mod 97 = 72


Folding
Metode lipat berfungsi dalam 2 langkah :
  • Bagi nilai kunci menjadi beberapa bagian dimana setiap bagian memiliki jumlah digit yang sama kecuali bagian terakhir yang mungkin memiliki angka lebih sedikit daripada bagian lainnya.
  • Tambahan bagi individu. Yaitu memperoleh jumlah part 1 + part  + .. + part n. Nilai hash yang dihasilkan dengan mengabaikan carry terakhir, jika ada.


  Contoh:
Key = 6632
Parts = 66 dan 32
Jumlah = 98
Hash value = 98

Digit Extraction
Mendapatkan hash key dengan cara mengambil digit – digit tertentu dari sebuah string
untuk dijadikan hash keynya.
Contoh: terdapat string yaitu 14568, jika kita mengambil digit 1, digit 3, dan digit 5 maka
hash keynya adalah 158.

Rotating Hash
Mendapatkan hash key maka di lakukan rotasi untuk menggeser digit sehingga
menemukan alamat hash key baru.
Contoh :
Hash key = 3456
Hasil rotasi = 6543

Collision
Ada 2 cara untuk menangani collision :
·        Linear Probing
Mencari slot kosong berikutnya dan letakkan string disana.
Code :
void linear_probing(item, h[]) {
hash_key = hash(item);
i = has_key;
while ( strlen(h[i] != 0 ) {
         if ( strcmp(h[i], item) == 0 ) {
              // DUPLICATE ENTRY
         }
         i = (i + 1) % TABLE_SIZE;
         if ( i == hash_key ) {
              // TABLE IS FULL
         }
}
h[i] = item;
}

·        Chaining
Masukkan string ke dalam slot sebagai chained list(linked list).
Code:
void chaining(item, h[]) {
     hash_key = hash(item);
     trail = NULL, lead = h[hash_key];
     while ( lead ) {
     if ( strcmp(lead->item, item) == 0 ) { // DUPLICATE ENTRY }
     trail = lead; lead = lead->next;
     }
     p = malloc new node;
     p->item = item;
     p->next = NULL;
     if ( trail == 0 ) h[hash_key] = p; else trail->next = p;
}


Trees  & Binary Tree

Tree adalah salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lainnya (disebut subtree).
Istilah – istilah umum dalam tree :
·        Prodecessor : node yang berada diatas node tertentu.
·        Successor : node yang berada di bawah node tertentu.
·        Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.
·        Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.
·        Parent : predecssor satu level di atas suatu node.
·        Child : successor satu level di bawah suatu node.
·        Sibling : node-node yang memiliki parent yang sama dengan suatu node.
·        Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
·        Size : banyaknya node dalam suatu tree.
·        Height : banyaknya tingkatan/level dalam suatu tree.
·        Root : satu-satunya node khusus dalam tree yang tak punya predecssor.
·        Leaf : node-node dalam tree yang tak memiliki seccessor.
·        Degree : banyaknya child yang dimiliki suatu node.

Jenis – jenis binary tree:
·        Perfect binary tree
Adalah binary tree yang setiap level berada pada kedalaman/ depth yang sama.
·        Complete binary tree
Adalah binary tree yang setiap levelnya kecuali yang terakhir semua telah terisi penuh dan setiap nodesnya paling panjang ke kiri.
·        Skewed binary tree
Adalah binary tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.
·        Balanced binary tree
Adalah binary tree yang dimana yang setiap leafnya sama jauhnya dari root

Representation of Binary Tree
  • Implementation using array


        Index on array represents node number
        Index 0 is Root node
        Index Left Child is 2p + 1, where p is parent index
        Index Right Child is 2p + 2
        Index Parent is (p-1)/2
  • Implementation using linked list

         struct node {
int data;
struct node *left;
struct node *right;
struct node *parent;
          };
          struct node *root = NULL;

structure binary tree
struct tnode {
char chr;
struct tnode *left;
struct tnode *right;
};

Insert di binary tree mengunakan C
// C++ program to insert element in binary tree
#include <iostream>
#include <queue>
using namespace std;
  
/* A binary tree node has key, pointer to left child
and a pointer to right child */
struct Node {
    int key;
    struct Node* left, *right;
};
  
/* function to create a new node of tree and r
   eturns pointer */
struct Node* newNode(int key)
{
    struct Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
};
  
/* Inorder traversal of a binary tree*/
void inorder(struct Node* temp)
{
    if (!temp)
        return;
  
    inorder(temp->left);
    cout << temp->key << " ";
    inorder(temp->right);
}
  
/*function to insert element in binary tree */
void insert(struct Node* temp, int key)
{
    queue<struct Node*> q;
    q.push(temp);
  
    // Do level order traversal until we find
    // an empty place. 
    while (!q.empty()) {
        struct Node* temp = q.front();
        q.pop();
  
        if (!temp->left) {
            temp->left = newNode(key);
            break;
        } else
            q.push(temp->left);
  
        if (!temp->right) {
            temp->right = newNode(key);
            break;
        } else
            q.push(temp->right);
    }
}
  
// Driver code
int main()
{
    struct Node* root = newNode(10);
    root->left = newNode(11);
    root->left->left = newNode(7);
    root->right = newNode(9);
    root->right->left = newNode(15);
    root->right->right = newNode(8);
  
    cout << "Inorder traversal before insertion:";
    inorder(root);
  
    int key = 12;
    insert(root, key);
  
    cout << endl;
    cout << "Inorder traversal after insertion:";
    inorder(root);
  
    return 0;
}

Deletion in a Binary Tree
Given a binary tree, delete a node from it by making sure that tree shrinks from the bottom (i.e. the deleted node is replaced by bottom most and rightmost node). This different from BST deletion. Here we do not have any order among elements, so we replace with last element.
Contoh:
Delete 10 in below tree
       10
     /    \        
    20     30
Output :   
       30
     /            
    20    
Delete 20 in below tree
       10
     /    \        
    20     30
            \
            40
Output :   
       10
     /   \            
    40    30  

Algorithm
·        Starting at root, find the deepest and rightmost node in binary tree and node which we want to delete.
·        Replace the deepest rightmost node’s data with node to be deleted.
·        Then delete the deepest rightmost node.

Source code in C/C++
// C++ program to delete element in binary tree
#include <bits/stdc++.h>
using namespace std;
  
/* A binary tree node has key, pointer to left 
child and a pointer to right child */
struct Node {
    int key;
    struct Node *left, *right;
};
  
/* function to create a new node of tree and 
return pointer */
struct Node* newNode(int key)
{
    struct Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
};
  
/* Inorder traversal of a binary tree*/
void inorder(struct Node* temp)
{
    if (!temp)
        return;
    inorder(temp->left);
    cout << temp->key << " ";
    inorder(temp->right);
}
  
/* function to delete the given deepest node 
(d_node) in binary tree */
void deletDeepest(struct Node* root,
                  struct Node* d_node)
{
    queue<struct Node*> q;
    q.push(root);
  
    // Do level order traversal until last node
    struct Node* temp;
    while (!q.empty()) {
        temp = q.front();
        q.pop();
        if (temp == d_node) {
            temp = NULL;
            delete (d_node);
            return;
        }
        if (temp->right) {
            if (temp->right == d_node) {
                temp->right = NULL;
                delete (d_node);
                return;
            }
            else
                q.push(temp->right);
        }
  
        if (temp->left) {
            if (temp->left == d_node) {
                temp->left = NULL;
                delete (d_node);
                return;
            }
            else
                q.push(temp->left);
        }
    }
}
  
/* function to delete element in binary tree */
Node* deletion(struct Node* root, int key)
{
    if (root == NULL)
        return NULL;
  
    if (root->left == NULL && root->right == NULL) {
        if (root->key == key)
            return NULL;
        else
            return root;
    }
  
    queue<struct Node*> q;
    q.push(root);
  
    struct Node* temp;
    struct Node* key_node = NULL;
  
    // Do level order traversal to find deepest
    // node(temp) and node to be deleted (key_node)
    while (!q.empty()) {
        temp = q.front();
        q.pop();
  
        if (temp->key == key)
            key_node = temp;
  
        if (temp->left)
            q.push(temp->left);
  
        if (temp->right)
            q.push(temp->right);
    }
  
    if (key_node != NULL) {
        int x = temp->key;
        deletDeepest(root, temp);
        key_node->key = x;
    }
    return root;
}
  
// Driver code
int main()
{
    struct Node* root = newNode(10);
    root->left = newNode(11);
    root->left->left = newNode(7);
    root->left->right = newNode(12);
    root->right = newNode(9);
    root->right->left = newNode(15);
    root->right->right = newNode(8);
  
    cout << "Inorder traversal before deletion : ";
    inorder(root);
  
    int key = 11;
    root = deletion(root, key);
  
    cout << endl;
    cout << "Inorder traversal after deletion : ";
    inorder(root);
  
    return 0;
}


Sumber : 
materi binus
https://www.geeksforgeeks.org/mid-square-hashing/
https://www.geeksforgeeks.org/insertion-in-a-binary-tree-in-level-order/
https://www.geeksforgeeks.org/deletion-binary-tree/
http://new-funday.blogspot.com/2012/12/struktur-data-tree-dan-penjelasaanya.html
https://zoneblog123.blogspot.com/2018/04/pengertian-tree-binary-tree-beserta.html