Seputar Struktur Data

Pengertian dan Penjelasan Struktur Data, Stack, Queue, Sorting (Bubble Sort & Selection Sort)

1. STRUKTUR DATA Struktur data adalah cara menyimpan atau merepresentasikan data didalam komputer agar bisa dipakai secara efisien. Sedangkan data adalah representasi dari fakta dunia nyata. Fakta atau keterangan tentang kenyataan yang disimpan, direkam atau direpresentasikan dalam bentuk tulisan, suara, gambar, sinyal atau simbol.

Secara garis besar type data dapat dikategorikan menjadi: 

Type data sederhana. Type data sederhana tunggal, misalnya Integer, real, boolean dan karakter.

Type data sederhana majemuk, misalnyaString 

Struktur Data, meliputi: Struktur data sederhana, misalnya array dan record. 

Struktur data majemuk, yang terdiri dari: Linier : Stack, Queue, sertaList dan Multilist Non Linier : Pohon Biner dan Graph 

Pemakaian struktur data yang tepat didalam proses pemrograman akan menghasilkan algoritma yang lebih jelas dan tepat, sehingga menjadikan program secara keseluruhan lebih efisien dan sederhana. 

Contoh :
X : Array[1..10] of integer
Artinya : mendefinisikan 10 variabel bertipe integer
Yaitu : X1, X2, X3, … X10

Contoh lain :
NamaHari : Array [1..7] of String
Nilai : Array [1..10] of Char
Frekuensi : Array[‘A’..‘E’] of Real

Contoh :

X : Array[1..10] of integer

Artinya    : mendefinisikan 10 variabel bertipe integer

Yaitu       : X₁, X₂, X₃, … X₁₀

Contoh lain :

NamaHari  : Array [1..7] of String

Nilai   : Array [1..10] of Char

Frekuensi : Array[‘A’..‘E’] of Real

Bentuknya :
tipe nama_var[ukuran];

Dengan :
● tipe : menyatakan jenis elemen array (int, char, unsigned, dan lain-lain)
● ukuran : menyatakan jumlah maksimal elemen array

Contoh Program dalam bahasa C++ :
#include
main()
{
int N[5]={25,12,17,10,15};
int i;
for(i=0; i<=4; i++)
cout << N[i];
}

atau :
#include
main()
{
int N[5]={25,12,17,10,15};
int i;
for(i=0; i<=4; i++)
printf(“%d \n”,N[i]);
}

Output :
25
12
17
10
15

B. Array Dimensi Dua
Array dua dimensi hampir sama dengan array berdimensi satu, namun biasanya array berdimensi dua banyak digunakan untuk penyajian data berbentuk tabel atau juga berbentuk matriks.
Cara Memberikan Nilai/Harga pada Array
NilaiMka : Array[1..10] of Char
NilaiMka1 ß ’A’
NilaiMka2 ß ’C’
NilaiMka3 ß ’ ’

Bahasa C++ :
Variabel array dideklarasikan dengan mencantumkan tipe dan nama variable yang diikuti dengan banyaknya lokasi memori yang ingin dibuat.
Bentuknya :
tipe nama_var[ukuran];

Dengan :
● tipe : menyatakan jenis elemen array (int, char, unsigned, dan lain-lain)
● ukuran : menyatakan jumlah maksimal elemen array

Contoh :
● int c[5];
C++ secara otomatis akan menyediakan lokasi memori sesuai dengan yang dideklarasikan, dimana nomor indeks selalu dimulai dari 0.
● int c[5] = {-12, 0, 20, 85, 1551};
Nilai suatu variabel array dapat juga diinisialisasi secara langsung seperti yang terdapat di dalam tanda kurung kurawal pada saat deklarasi di atas.
● int x[5] = {0};
Deklarasi variable array sekaligus mengisi setiap lokasi memorinya dengan nilai 0.

Contoh Algoritma :
Algoritma Array1D
DEKLARASI
N : array[1..5] of integer
i : integer
DESKRIPSI
N1ß 25
N2ß 12
N3ß 17
N4ß 10
N5ß 15
For i ß 1 to 5 do
Output (Ni)
endfor
Contoh Program dalam bahasa C++ :
#include
main()
{
int N[5]={25,12,17,10,15};
int i;
for(i=0; i<=4; i++)
cout << N[i];
}

atau :
#include
main()
{
int N[5]={25,12,17,10,15};
int i;
for(i=0; i<=4; i++)
printf(“%d \n”,N[i]);
}

Output :
25
12
17
10
15

Bentuknya :
DEKLARASI
NamaArray : TipeElemen Array[r_indeks1, r_indeks2]

Cara mengakses suatu elemen :
NamaArrayindeks1,indeks2
Contoh

1
2
3
4
1
10
1
11
15
2
20
2
21
25
3
30
3
31
35
4
40
4
41
45

Harga1,1 ß 10
Harga2,3 ß 21
Harga3,1 ß 30

*Bahasa C++ :
Bentuknya :
tipe nama_var[ukuran1][ukuran2];

ukuran1 = jumlah baris
ukuran 2 = jumlah kolom

Contoh :
int data_huruf[2][4];
Contoh :
Sebuah matrik A berukuran 2×3 dapat dideklarasikan sebagai berikut:
int a[2][3] = {{11, 7, 4},{12, 3, 9}} yang akan menempati lokasi memori dengan susunan berikut :
0
1
2
0
11
7
4
1
12
3
9

Dan definisi variabel untuk setiap elemen tersebut adalah :
0
1
2
0
a[0][0] a[0][1] a[0][2] 1
a[1][0] a[1][1] a[1][2]

Contoh Program dalam bahasa C++:
/* Program : array.cpp */
#include
void printArray(int [][3]);

main()
{ int matrik1 [2][3] = { {1, 1, 1}, {2, 2, 2}};
int matrik2 [2][3] = { {3, 3, 3}, {4, 4, 4}};
int matrik3 [2][3] = { {5, 5, 5}, {6, 6, 6}};
printArray(matrik1);
printArray(matrik2);
printArray(matrik3);
return 0;
}

void printArray(int a[][3])
{ int i, j;

for(i=0; i<=1; i++)
{ for(j=0; j<=2; j++)
cout << a[i][j]<< ” “;
cout << endl;
}
}

atau :
/* Program : array.cpp */
#include
void printArray(int [][3]);

main()
{ int matrik1 [2][3] = { {1, 1, 1}, {2, 2, 2}};
int matrik2 [2][3] = { {3, 3, 3}, {4, 4, 4}};
int matrik3 [2][3] = { {5, 5, 5}, {6, 6, 6}};
printArray(matrik1);
printArray(matrik2);
printArray(matrik3);
return 0;
}

void printArray(int a[][3])
{ int i, j;

for(i=0; i<=1; i++)
{ for(j=0; j<=2; j++)
printf(“%d “,a[i][j]);
printf(“\n”);
}
}

C.Array Dimensi Banyak
Algoritma :
Bentuknya :
DEKLARASI
NamaArray : TipeElemen Array[r_indeks1, r_indeks2,… , r_indeksn]

Cara mengakses suatu elemen :
NamaArrayindeks1, indeks2, indeks3

Bahasa C++ :
Bentuknya :
tipe nama_var[ukuran1][ukuran2]. . .[ukuranN];

Contoh :
int data_huruf[2][4][6

 

Single Linked List

Linked List adalah salah satu bentuk struktur data, berisi kumpulan data
(node) yang tersusun secara sekuensial, saling sambungmenyambung,
dinamis dan terbatas.
- Linked List sering disebut juga Senarai Berantai
- Linked List saling terhubung dengan bantuan variabel pointer
- Masing-masing data dalam Linked List disebut dengan node (simpul) yang
menempati alokasi memori secara dinamis dan biasanya berupa struct
yang terdiri dari beberapa field.

Single Linked List adalah sebuah LINKED LIST yang menggunakan sebuah variabel pointer saja untuk menyimpan banyak data dengan metode LINKED LIST, suatu daftar isi yang saling berhubungan.

Ilustrasi single LINKED LIST:

Pada gambar di atas, data terletak pada sebuah lokasi dalam sebuah memory, tempat yang disediakan memory untuk menyimpan data disebut node ? simpul, setiap node memiliki pointer ( penunjuk ) yang menunjuk ke node berikutnya sehingga terbentuk suatu untaian yang disebut single LINKED LIST. Bila dalam single LINKED LIST pointer hanya dapat bergerak ke satu arah saja, maju / mundur, kanan / kiri, sehingga pencarian datanya juga hanya satu arah saja.

Ada 2 Tipe Single Linked List yaitu

·         Single Linked List Circular

·         Single Linked List Non Circular

1.     Single Linked List Circular

Single Linked List Circular adalah Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node,
maka pointer next pada node terakhir akan menunjuk ke node terdepannya.

Pengertian:
Single : artinya field pointer-nya hanya satu buah saja dan satu arah.
Circular : artinya pointer next-nya akan menunjuk pada dirinya sendiri sehingga berputar

Ilustrasi Single Linked List Circular
- Setiap node pada linked list mempunyai field yang berisi pointer ke node
  berikutnya, dan juga memiliki field yang berisi data.
- Pada akhir linked list, node terakhir akan menunjuk ke node terdepan
  sehingga linked list tersebut berputar. Node terakhir akan menunjuk lagi
  ke head.

PEMBUATAN SINGLE LINKED LIST CIRCULAR
Deklarasi node
Dibuat dari struct berikut ini:
typedef struct TNode{
int data;
TNode *next;
};

Penjelasan:
- Pembuatan struct bernama TNode yang berisi 2 field, yaitu field data
  bertipe integer dan field next yang bertipe pointer dari TNode
- Setelah pembuatan struct, buat variabel haed yang bertipe pointer dari
  TNode yang berguna sebagai kepala linked list.

Pembentukan node baru
Digunakan keyword new yang berarti mempersiapkan sebuah node baru
berserta alokasi memorinya.

TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = baru;

SINGLE LINKED LIST CIRCULAR MENGGUNAKAN HEAD
- Dibutuhkan satu buah variabel pointer: head
- Head akan selalu menunjuk pada node pertama

Deklarasi Pointer Penunjuk Kepala Single Linked List
Manipulasi linked list tidak bisa dilakukan langsung ke node yang dituju,
melainkan harus melalui node pertama dalam linked list. Deklarasinya sebagai berikut:

TNode *head;

Fungsi Inisialisasi Single LinkedList
void init(){
head = NULL;
}

Function untuk mengetahui kosong tidaknya Single LinkedList
int isEmpty(){
if(head == NULL) return 1;
else return 0;
}

PENAMBAHAN DATA
Penambahan data di depan
Penambahan node baru akan dikaitan di node paling depan, namun pada saat
pertama kali (data masih kosong), maka penambahan data dilakukan pada
head nya.
Pada prinsipnya adalah mengkaitkan data baru dengan head, kemudian head
akan menunjuk pada data baru tersebut sehingga head akan tetap selalu
menjadi data terdepan. Untuk menghubungkan node terakhir dengan node
terdepan dibutuhkan pointer bantu.

void insertDepan(int databaru){
TNode *baru,*bantu;
baru = new TNode;
baru->data = databaru;
baru->next = baru;

if(isEmpty()==1){
head=baru;
head->next=head;
}
else {
bantu = head;
while(bantu->next!=head){
bantu=bantu->next;
}
baru->next = head;
head = baru;
bantu->next = head;
}
cout<<"Data masuk\n";
}

Penambahan data di belakang Penambahan data dilakukan di belakang, namun pada saat pertama kali data langsung ditunjuk pada head-nya. Penambahan di belakang lebih sulit karena kita membutuhkan pointer bantu untuk mengetahui data terbelakang, kemudian dikaitkan dengan data baru. Untuk mengetahui data terbelakang perlu digunakan perulangan.

void insertBelakang (int databaru)
{
TNode *baru,*bantu;
baru = new TNode;
baru->data = databaru;
baru->next = baru;
if(isEmpty()==1){
head=baru;
head->next=head;
}
else {
bantu = head;
while(bantu->next != head){
bantu=bantu->next;
}
bantu->next = baru;
baru->next = head;
}
cout<<"Data masuk\n";
}

“Bagaimana dengan penambahan di tengah?”

MENAMPILKAN DATA
Function untuk menampilkan isi single linked list
void tampil(){ TNode *b;
b = head;
if(isEmpty()==0)
{
do
{
cout<data<<" ";
b=b->next;
}
while(b!=head);
cout<<<"Masih kosong\n";
}

- Function di atas digunakan untuk menampilkan semua isi list, di mana linked list ditelusuri satu-persatu dari awal node sampai akhir node. Penelusuran ini dilakukan dengan menggunakan suatu variabel node bantu, karena pada prinsipnya variabel node head yang menjadi tanda awal list tidak boleh berubah/berganti posisi.
- Penelusuran dilakukan terus sampai node terakhir ditemukan menunjuk ke head lagi. Jika belum sama dengan head, maka node bantu akan berpindah ke node selanjutnya dan membaca isi datanya dengan menggunakan field next sehingga dapat saling berkait. 

STACK

Pengertian Stack pada Struktur Data adalah sebagai tumpukan dari benda, sekumpulan data yang seolah-olah diletakkan di atas data yang lain, koleksi dari objek-objek homogen, atau Suatu urutan elemen yang elemennya dapat diambil dan ditambah hanya pada posisi akhir (top) saja. Stack pada Struktur Data dapat diilustrasikan dengan dua buah kotak yang ditumpuk, kotak yang satu akan ditumpuk diatas kotak yang lainnya. Jika kemudian stack 2 kotak tadi, ditambah kotak ketiga, keempat, kelima, dan seterusnya, maka akan diperoleh sebuah stack kotak yang terdiri dari N kotak. 

Stack bersifat LIFO (Last In First Out) artinya Benda yang terakhir masuk ke dalam stack akan menjadi yang pertama keluar dari stack 

Operasi-operasi yang biasanya tredapat pada Stack yaitu:

1. Push : digunakan untuk menambah item pada stack pada tumpukan paling atas

2. Pop : digunakan untuk mengambil item pada stack pada tumpukan paling atas

3. Clear : digunakan untuk mengosongkan stack

4. IsEmpty : fungsi yang digunakan untuk mengecek apakah stack sudah kosong

5. IsFull : fungsi yang digunakan untuk mengecek apakah stack sudah penuh

Cara mendefenisikan Stack dengan Array of Struct yaitu:

1. Definisikan Stack dengan menggunakan struct

2. Definisikan konstanta MAX_STACK untuk menyimpan maksimum isi stack

3. Buatlah variabel array data sebagai implementasi stack

4. Deklarasikan operasi-operasi/function di atas dan buat implemetasinya.

contoh :

//Deklarasi MAX_STACK

                #define MAX_STACK 10   

            

//Deklarasi STACK dengan struct dan array data

                typedef struct STACK{

                                int top;

                                char data[10][10];                                                           

                }; 

//Deklarasi/buat variabel dari struct

                STACK tumpuk;

Inisialisasi Stack

Pada mulanya isi top dengan -1, karena array dalam C dimulai dari 0, yang berarti stack adalah kosong.

Top adalah suatu variabel penanda dalam STACK yang menunjukkan elemen teratas Stack sekarang.  Top Of Stack akan selalu bergerak hingga mencapai MAX of STACK sehingga menyebabkan stack penuh.

Ilustrasi Stack pada saat inisialisasi

IsFull berfungsi untuk memeriksa apakah stack sudah penuh atau tidak. Dengan cara, memeriksa top of stack, jika sudah sama dengan MAX_STACK-1 maka full, jika belum (masih lebih kecil dari MAX_STACK-1)  maka belum full.

Ilustrasi Stack pada kondisi Full

IsEmpty berfungsi untuk memeriksa apakah stack masih kosong atau tidak. Dengan cara memeriksa top of stack, jika masih -1 maka berarti stack masih kosong.

Push berfungsi untuk memasukkan elemen ke stack, selalu menjadi elemen teratas stack (yang ditunjuk oleh TOS).

Tambah satu (increment)  nilai top of stack lebih dahulu setiap kali ada penambahan elemen stack.

Asalkan stack masih belum penuh, isikan data baru ke stack berdasarkan indeks top of stack setelah diincrement sebelumnya.

Pop berfungsi untuk mengambil elemen teratas (data yang ditunjuk oleh TOS) dari stack.

Ambil dahulu nilai elemen teratas stack dengan mengakses top of stack, tampilkan nilai yang akan dipop, baru dilakukan decrement nilai top of stack sehingga jumlah elemen stack berkurang.

 

Printberfungsi untuk menampilkan semua elemen-elemen stack dengan cara looping semua nilai array secara terbalik, karena kita harus mengakses dari indeks array tertinggi terlebih dahulu baru ke indeks yang kecil.

 

 

Operasi Push

void Push (NOD **T, char item)

                {

                                NOD *n;

                                n=NodBaru (item);

                                n->next=*T;

                                *T=n;

                }

Operasi Pop

char Pop (NOD **T)

                {

                                NOD *n; char item;

                                if (!StackKosong(*T)) {

                                                P=*T;

                                                *T=(*T)->next;

                                                item=P->data;

                                                free(P);

                                }

                                return item;

                }

 

create berfungsi untuk membuat sebuah stack baru yang masih kosong.

spesifikasi:

tujuan : mendefinisikan stack yang kosong

input : stack

syarat awal : tidak ada

output stack : - (kosong)

syarat akhir : stack dalam keadaan kosong

 QUEUE 

        Queue pada Struktur Data atau antrian adalah sekumpulan data yang mana penambahan elemen hanya bisa dilakukan pada suatu ujung disebut dengan sisibelakang(rear), dan penghapusan(pengambilan elemen) dilakukan lewat ujung lain (disebut dengan sisi depan atau front). 

Queue atau antrian prinsip yang digunakan adalah “Masuk Pertama Keluar Pertama” atau FIFO (First In First Out). 

Queue atau antrian banyak kita jumpai dalam kehidupan sehari-hari, ex: antrian Mobil diloket Tol, Antrian mahasiswa Mendaftar, dll. Contoh lain dalam bidang komputer adalah pemakaian sistem komputer berbagi waktu(time-sharing computer system) dimana ada sejumlah pemakai yang akan menggunakan sistem tersebut secara serempak.

Pada Queue atau antrian Terdapat satu buah pintu masuk di suatu ujung dan satu buah pintu keluar di ujung satunya dimana membutuhkan variabel Head dan Tail ( depan/front, belakang/rear). 

Karakteristik Queue atau antrian : 

1. elemen antrian 

2. front (elemen terdepan antrian) 

3. tail (elemen terakhir) 

4. jumlah elemen pada antrian 

5. status antrian Operasi pada Queue atau antrian 

1. tambah(menambah item pada belakang antrian) 

2. hapus (menghapus elemen depan dari antrian) 

3. kosong( mendeteksi apakah pada antrian mengandung elemen atau tidak) 

Operasi-operasi Queue : 

 1. Create() Untuk menciptakan dan menginisialisasi Queue Dengan cara membuat Head dan Tail = -1 

 2. IsEmpty() Untuk memeriksa apakah Antrian sudah penuh atau belum Dengan cara memeriksa nilai Tail, jika Tail = -1 maka empty Kita tidak memeriksa Head, karena Head adalah tanda untuk kepala antrian (elemen pertama dalam antrian) yang tidak akan berubah-ubah Pergerakan pada Antrian terjadi dengan penambahan elemen Antrian kebelakang, yaitu menggunakan nilai Tail. 

 3. IsFull Untuk mengecek apakah Antrian sudah penuh atau belum Dengan cara mengecek nilai Tail, jika 

Tail >= MAX-1 (karena MAX-1 adalah batas elemen array pada C) berarti sudah penuh 

 4. Enqueue Untuk menambahkan elemen ke dalam Antrian, penambahan elemen selalu ditambahkan di elemen paling belakang Penambahan elemen selalu menggerakan variabel Tail dengan cara increment counter Tail terlebih dahulu 

 5. Dequeue() Digunakan untuk menghapus elemen terdepan/pertama (head) dari Antrian Dengan cara menggeser semua elemen antrian kedepan dan mengurangi Tail dgn 1 Penggeseran dilakukan dengan menggunakan looping.

 6. Clear() Untuk menghapus elemen-elemen Antrian dengan cara membuat Tail dan Head = -1 Penghapusan elemen-elemen Antrian sebenarnya tidak menghapus arraynya, namun hanya mengeset indeks pengaksesan-nya ke nilai -1 sehingga elemen-elemen Antrian tidak lagi terbaca 

 7. Tampil() Untuk menampilkan nilai-nilai elemen Antrian Menggunakan looping dari head s/d tail 

4. SORTING 

      Sorting adalah proses menyusun elemen – elemen dengan tata urut tertentu dan proses tersebut terimplementasi dalam bermacam aplikasi. Kita ambil contoh pada aplikasi perbankan. Aplikasi tersebut mampu menampilkan daftar account yang aktif. Hampir seluruh pengguna pada sistem akan memilih tampilan daftar berurutan secara ascending demi kenyamanan dalam penelusuran data. Beberapa macam algoritma sorting telah dibuat karena proses tersebut sangat mendasar dan sering digunakan. Oleh karena itu, pemahaman atas algoritma – algoritma yang ada sangatlah berguna. 

1.Selection Sort (Ascending): Pengurutan dilakukan dengan memilih elemen terbesar dan menempatkan pada posisinya, kemudian mencari element terbesar berikutnya dan menempatkan pada tempatnya, dan seterusnya. 

Proses pengurutan dengan menggunakan metode selection sort secara terurut naik adalah : 

1. Mencari data terkecil dari data pertama sampai data terakhir, kemunian di tukar posisinya dengan data pertama. 

2. mencari data terkecil dari data kedua sampai data terakhir, kemudian di tukar dengan posisinya dengan data kedua. 

3. mencari data terkecil dari data ketiga sampai data terakhir, kemudian di tukar posisinya dengan data ketiga 

4. dan seterusnya sampai semua data turut naik. apabila terdapat n buah data yang akan di urutkan, maka membutukan (n - 1) langkah pengurutan, dimana data terakhir yaitu data ke-n tidak perlu di urutkan karena hanya tinggal satu satunya. 

2. Bubble Sort Konsep Buble Sort Metode pengurutan gelembung (Bubble Sort) diinspirasikan oleh gelembung sabun yang berada dipermukaan air. Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air, maka gelembung sabun selalu terapung ke atas permukaan. Prinsip di atas dipakai pada pengurutan gelembung. Bubble sort (metode gelembung) adalah metode/algoritma pengurutan dengan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat

Searching
Pencarian dalam binary search tree untuk suatu nilai key dapat dilakukan secara recursive maupun dengan proses iterative. Langkah pertama dalam pencarian ialah dengan melakukan identifikasi root node. Bila root node null maka key yang dicari tidak ada. Sebaliknya bila root tersebut exist, maka langkah selanjutnya ialah membandingkan nilai key dengan node root tersebut. Bila nilai root node sama seperti key yang dicari, maka nilai root node tersebut akan dikembalikan sebagai hasil. Bila nilai key lebih kecil dari node, maka pencarian diarahkan ke subtree di sisi kiri dari node, proses ini dilakukan terus berulang hingga key ditemukan. Sebaliknya bila nilai key lebih besar dari node, maka langkah selanjutnya ialah memilih subtree di sisi kanan node tersebut. Dalam kasus terburuk, pencarian ini akan mencapai ujung subtree terjauh dari root, atau setara dengan tinggi dari tree tersebut.
Contoh pencarian secara recursive dilakukan sebagai berikut.

function Find-recursive(key, node):
    if node = Null or node.key = key then
        return node
    else if key < node.key then
        return Find-recursive(key, node.left)
    else
        return Find-recursive(key, node.right)

Contoh pencarian secara recursive dilakukan sebagai berikut.

function Find(key, root):
    current-node := root
    while current-node is not Null do
        if current-node.key = key then
            return current-node
        else if key < current-node.key then
            current-node ← current-node.left
        else
            current-node ← current-node.right
    return Null

Terdapat beberapa istilah yang digunakan untuk memudahkan merujuk pada suatu node. Node parent ialah suatu node dalam binary search tree yang memiliki child, atau terdapat satu subtree, children, bila memiliki dua subtree di sisi kanan dan kiri. Node child ialah node yang ada menjadi subtree dari node parent.

Insertion
Proses insertion (memasukkan suatu data) dilakukan mulai secara bersamaan dengan proses pencarian data. Bila key tidak sesuai dengan nilai yang ada di root, pencarian dilakukan ke subtree kanan atau kiri. Hingga berada pada node luar, untuk kemudian dilakukan penambahan data key baru. Dengan kata lain dilakukan proses pemeriksaan root dan secara recursive memasukkan suatu node baru di sisi kiri bila nilainya lebih kecil, atau di sisi kanan bila nilainya lebih besar (atau bisa juga sama besar) dibandingkan dengan nilai dari root tersebut.

Deletion
Terdapat beberapa aturan dasar yang perlu diperhatikan dalam langkah menghapus suatu node, yakni.

1. Bila node tersebut tidak memiliki child, node tersebut dapat langsung dihapus
2. Bila node tersebut memiliki child, maka node (parent) tersebut dihapus dan child dari node tersebut menggantikan posisi dari node parent
3. Bila node tersebut memiliki dua children, maka langkah pertama yang dilakukan ialah mengganti nilai node parent dengan salah satu child, hapus nilai node parent awal, secara recursive hapus nilai node child yang telah digunakan untuk mengganti nilai node parent sebelumnya, kemudian lakukan seperti pada kasus pertama atau kedua

Suatu node dengan children, lebih sulit untuk dihapus. Bila node child lebih besar dari node parent yang digantikan maka disebut in-order successor. Sebaliknya bila node child lebih kecil dari node parent yang digantikan, maka disebut in-order predecessor.