ALGORITMA DAN STRUKTUR DATA : BAB 12

SORTING (1)

12. 1 Sorting

Sorting / pengurutan adalah suatu proses untuk mengurutkan elemen-elemen berdasarkan key /
kunci tertentu. Tujuan dari sorting adalah agar mudah dan cepat dalam melakukan pencarian /
searching.
Dalam kehidupan sehari-hari banyak sekali contoh yang dapat diberikan tentang sorting ini,
misalnya Absen Mahasiswa diurutkan / disort berdasarkan NIM , Daftar Dosen diurutkan berdasarkan
Kode Dosen. Urutan dalam sorting :
• Bisa dilakukan secara menaik dari kecil ke besar ( Ascending ), yang berarti elemen dengan
key yang kecil akan berada diatas dari elemen dari key yang lebih besar atau

• Bisa dilakukan secara menurun dari besar ke kecil ( Descending ), yang berarti elemen
dengan key besar akan berada di atas elemen dengan key yang lebih kecil.
Teknik melakukan sorting ini cukup banyak , yang dapat dikelompokkan dalam 3 (tiga) kelompok,
yaitu :

1. Simple Sort Techniques
• Exhange sort / Bubble Sort
• Selection Sort
• Insertion Sort

2. Advanced Sort Techniques
• Heap Sort
• Quick Sort
• Merge Sort

12. 1.1 Exchange / Bubble Sort

Exchange Sort melakukan pengurutan dengan membandingkan elemen dengan elemen berikutnya.
Jika elemen sekarang ternyata lebih besar ( untuk Ascending Sort ) dibandingkan dengan elemen
berikutnya,maka dilakukan pertukaran tempat (SWAP). Dibawah ini disajikan contoh dalam
melakukan Exhange Sort.
Contoh : Apabila terdapat daftar angka 390, 205, 182, 45, 235, lakukan sorting dengan teknik
Exchange Sort.

GambarGambar

Prosedure untuk melakukan Exchange Sort adalah sebagai berikut :

#define Nmaks 1000;
typedef int LarikInt[Nmaks+1];
void ExchangeSort (LarikInt *L, int N)
{
int I;
int K;
int Temp;
for (I=1; I <=N-1; I++)
for (K = N; K>= I+1; K–)
if (*L[K] < *L[K-1])
{
Temp = *L[K];
*L[K] = *L[K-1];
*L[K-1] = Temp;
}
}

12.1.2 Selection Sort

Konsep dasar dalam melakukan pengurutan dengan teknik selection sort adalah dengan memilih nilai
terkecil dari nilai-nilai yang akan diurutkan. Dibawah ini disajikan contoh secara bertahap mengenai
proses Selection Sort.
Contoh bila diketahui list angka 390, 205, 182, 45, 235 dilakukan sorting dengan teknik Selection Sort.

Gambar

 

Langkah-langkahnya adalah sebagai berikut :

1. Dari list angka ambil yang paling kecil, yaitu angka 45, tukar tempat antara 45 dengan
elemen yang berada pada tempat pertama, yaitu angka 390, berarti sudah ada 1 angka (
yaitu 45 ) yang diurut, yang ditandai dengan garis bawahnya.

2. Dari list angka yang belum sort ( dari 205,182,,390,235 ) ambil angka yang paling kecil.
Yaitu angka 182. tukar tempat antara 182 dengan angka pada posisi kedua, yaitu 205.
berarti sudah ada 2 angka ( yaitu 45 dan 182 ) yang sudah urut.

3. dstnya
Prosedur untuk melakukan Selection Sort adalah sebagai berikut :

#define Nmaks 1000;
typedef int LarikInt[Nmaks+1];
void selectionsort(LarikInt *L, int N);
{
int I;
int J;
int Imin;
int Temp;
for (I=1; I<=N-1; I++)
{
Imin = I;
for (J=I+1; J<=N; J++)
if (*L[J] < *L[Imin])
Imin = J;
Temp = *L[Imin];
*L[Imin] = *L[I];
*L[I] = Temp;
}
}

12.1.3 Insertion Sort

Insertion Sort dilakukan dengan menambahkan satu demi satu elemen ke dalam list elemen-elemen
yang telah terurut, sehingga data tepat sorted. Berikut diberikan ilustrasi secara bertahap dalam
melakukan Insertion Sort.

Contoh : untuk list angka yang sama seperti diatas, yaitu : 390, 205, 182, 45, 235 lakukan
Sorting dengan teknik Insertion Sort

Gambar

Langkah pengerjaan Insertion Sort adalah sebagai berikut :

1. Ambil 2 angka yang paling bawah , yaitu 45 dan 235, lakukan pengurutan terhadap kedua
angka tersebut.

2. Tambahkan 1 angka lagi ke dalam list data yang sudah terurut, yang menjadi 182, 45, 235
lakukan pengurutan terhadap list data ini.

3. dstnya.
Prosedur untuk melakukan Insertion Sort adalah sebagai berikut :
#define Nmaks 1000;
typedef int LarikInt[Nmaks+1];
void InsertionSort(LarikInt *L, int N)
{
typedef enum{true=1, false=0} boolean;
int I;
int J;
int x;

boolean ketemu;
for (I=2; I<=N; I++)
x = *L[I];
J = I-1;

ketemu = false;
while (J >= 1) && (! ketemu)
{
if (x < *L[J])
{
*L[J+1] = *L[J];
J—;
}
else
ketemu = true;
}
*L[J+1] = x;
}
}

Iklan

ALGORITMA DAN STRUKTUR DATA : BAB 13

SORTING II

13.1 Advanced Sorting

Kelemahan dari Simple Sort Teknik adalah diperlukannya waktu yang lama untuk melakukan sorting ,
terutama bila data yang hendak disort panjang. Kelemahan ini diatasi dengan Advanced Sort Teknik
yang pada umumnya memerlukan waktu yang lebih sedikit.

13.2 Quick Sort

Konsep dalam Quick Sort adalah “ memecah “ list yang akan di sort menjadi dua bagian, dan masingmasing
bagian akan dilakukan Sort tersendiri. Misalkan elemen yang diurutkan adalah :
r[1], r[2],……….r[n]

Maka satu langkah dalam quicksort akan menghasilkan :
r[1], r[2], ….. r[j-1], r[j] r[j+1],…..r[n]
(a) (b) (c)

Dapat dikatakan bahwa r[j] berada pada posisi yang “tepat” dengan pengertian bahwa semua elemen
yang berada dikiri r[j] LEBIH KECIL dibandingkan r[j], dan smeua elemen yang berada dikanan r[j]
LEBIH BESAR dibandingkan r[j]

Langkah berikutnya adalah mengurutkan elemen r[1] sampai dengan r[j-1] dan elemen r[j+1] sampai
r[n] dengan teknik yang sama seperti diatas.

Contoh ;
1. 73 79 76 72 75 78 71 77 74
2. 72 71 73 76 75 78 79 77 74
3. [71] 72 [73] 76 75 78 79 77 74
4. [71 72 73] 76 75 78 79 77 74
5. [71 72 73] 74 75 [76] 79 77 78
6. [71 72 73 74] 75 [76] 79 77 78
7. [71 72 73 74 75 76] 79 77 78
8. [71 72 73 74 75 76] 77 78 [79]
9. [71 72 73 74 75 76 77 78 79]

Langkah-langkahnya adalah sebagai berikut :

1. Carilah posisi yang paling tepat untuk angka 73. arti posisi paling tepat adalah bahwa semua
angka di sebelah kiri 73, harus lebih kecil dari 73 dan yang sebelah kanan 73 harus lebih
besar dari 73.

2. Cara mencari posisi yang paling tepat adalah ;
a. Cari dari kiri ke kanan sampai ketemu angka yang lebih besar dari 73.
b. Cari dari kanan ke kiri sampai ketemu angka yang lebih kecil dari 73.
c. Cek apakah sudah overlapping (apakah j >= k).

• Jika belum overlapping, maka tukar elemen, yang berada pada posisi j dengan
elemen yang berada pada posisi k.

• Jika sudahOverlapping, maka tukar elemen yang lebih kecil, dengan elemen
yang ingin dicarikan posisi tepatnya.
Contoh : akan dicarikan posisi yang paling tepat untuk angka 73.
73 79 76 72 75 78 71 77 74

• Dicari dari kiri kanan, sampai ketemu angka yang lebih besar dari 73, ketemu dengan angka

• Dicari dari kanan ke kiri, sampai ketemu angka yang lebih kecil dari 73, ketemu dengan
angka 71.

• Cek apakah sudah overlapping, bila belum maka tukar tempat antara 79 dengan 71 hasilnya
adalah:
73 71 76 72 75 78 79 77 74

• Pencarian diteruskan dari tempat berakhir tadi, dicari lagi dari kiri kanan, sampai ketemu
angka yang lebih besar dari 73, ketemu dengan angka 76.

• Pencarian dari kanan juga diteruskan dari tempat berakhir tadi, dicari ke kanan untuk
menemukan angka yang lebih kecil dari 73, ketemu dengan angka 72.

• Cek apakah sudah overlapping, ternyata belum, maka tukar tempatkan antara angka 76
dengan 72.hasilnya adalah.
73 71 72 76 75 78 79 77 74

• Pencarian diteruskan lagi, mencari dari kiri ke kanan sampai ketemu angka yang lebih besar
dari 73 , ketemu dengan angka 76.

• Pencarian dari kanan ke kiri juga dilakukan untuk mencari angka yang lebih kecil dari 73,
ketemu dengan angka 72,

• Ternyata sudah overlapping, sehingga dilakukan pertukaran tempat antara angka yang kecil
yaitu : 72 dengan angka yang ingin dicarikan tempat yang tepat, yaitu 73 hasilnya adalah :
72 71 [73] 76 75 78 79 77 74
(a) (b)

Sekarang angka 73 sudah berada pad posisi yang tepat, artinya semua angka di sebelah kirinya lebih
kecil darinya dan semua angka di sebelah kanannya lebih besar darinya. Pencarian diteruskan untuk
dua sub-list berikutnya, yaitu sub list (a) dan sub list (b).

Prosedur untuk melakukan Quick Sort adalah sesuai dengan menggunakan Recursive yaitu suatu
fungsi yang memanggil dirinya sendiri.

void quicksort (int *arr, int kr, int kn)
{
int i, j, k;
if (kr < kn)
{
j = kr;
k = kn + 1;
do {
do j++; while (j <= kn && arr[j] < arr[kr]);
do k–; while (arr[k] > arr[kr]);
if (j < k) tukar (&arr[j], &arr[k]);
} while (j<= k);
tukar (&arr[kr], &arr[k]);
quicksort (arr, kr, k-1);
quicksort (arr, k+1, kn);
}
}

13. 3 Heap Sort

Heap Sort adalah suatu teknik sorting yang memanfaatkan Heap / Complete Binary Tree yang telah
dibahas pada bab terdahulu. seperti diketahui ada 2 tipe Heap, yaitu Minimum Heap dan Maksimum
Heap. Bila dipergunakan minimum Heap dalam melakukan sorting maka hasil pengurutan berbentuk
Descending, sedangkan
kebalikannya bila menggunakan Maksimum Heap, maka akan dihasilkan sorting secara Ascending.

Tahapan dalam melakukan Heap Sort adalah :
• Membangun Heap Awal sehingga memenuhi kondidi heap (heapify)
• Mengambil data dari heap untuk diurutkan sesuai dengan urutannya, dengan cara pertukaran
data [1] dengan data [j] dengan j = n, n-1, …., 2. Setiap pertukaran ini menyebabkan kondisi
heap rusak. Untuk menanggulangi ini maka harus dibangun lagi heap ke kondisi semula.
Contoh lakukanlah sorting terhadap angka-angka 390, 205, 182, 45, 235 dengan mempergunakan
teknik Heap Sort dan menggunakan Minimum Heap.

Langkah 1: membangun Heap awal

Gambar

Tree yang dibangun berdasarkan list angka, tetapi masih belum berupa Maximum Heap. Lakukan
pertukaran tempat sampai terjadi Maximum Heap seperti pada gambar berikut ini

Gambar

Gambar

Gambar

Gambar

Gambar

Gambar

Gambar

Proses pengurutan dengan metode heapsort maximum selesai dan menghasilkan urutan elemen

secara ascending.

void addroot(int *arr, int i, int n)
{
int child, temp;
for (temp = arr[i]; i*2 <= n; i =child)
{
child = i * 2;
if ((child != n) && (arr[child +1] > arr[child])) child++;
if (temp < arr[child]) arr[i] = arr[child];
else break;
}
arr[i] = temp;
}
void heapsort(int *arr, int n)
{
int i
for (i = n/2; i > 0; i–) addroot(arr, i, n);
for (i = n; i > 1; i–)
{
tukar(&arr[1], arr[i]);
addroot(arr, 1, i-1);
}
}

13.4 Merge Sort dengan metode rekursif
Terdapat 3 prosedur dalam metode ini, yaitu prosedur mergesort, merge, dan insert.
Prosedur mergesort
Langkah – langkahnya:

1. membagi 1 array menjadi 2 dengan cara:
cari tengahnya mid = (a+b) div 2 sehingga terdapat 2 bagian, (a, mid) dan (mid+1, b)
lakukan terus pembagian samapi pada leaves (daun) yang tidak bisa dibagi lagi.

2. lakukan merge pada daun yang tidak bisa dibagi lagi

3. kedua langkah diatas dilakukan apabila a < b (indeks kiri lebih kecil dari indeks kanan)

algoritmanya:
procedure mergesort(a, b: integer)
begin
if a < b then
begin
mid := (a+b) div 2
mergesort(a, mid)
mergesort(mid+1, b)
merge (a,b)
end if
end

Prosedur merge
Langkah – langkahnya:
1. cari mid-nya
2. tentukan indeks i 􀃆 a = i
3. tentukan k 􀃆 k = mid + 1
4. bandingkan elemen yang ke-i dengan elemen yang ke-k
jika nilai elemen yang ke-i <= nilai elemen yang ke-k, maka
naikkan jumlah
jika tidak, maka

  • insert elemen yang ke-k ke elemen yang ke-i
  • naikkan jumlah i
  • naikkan jumlah k
  • naikkan mid

5. lakukan langkah 4 sampai i > mid atau k > b

algoritmanya:
prosedure merge(a,b: integer)
begin
mid = (a+b) div 2
i = a
k = mid +1
repeat
if a[i] <= a[k] then i = i+1
else
begin
insert (k, i)
i = i+1
k = k+1
mid = mid + 1
endif
until i > mid or k > b
end

Prosedur insert
Langkahnya:
1. tentukan nilai yang akan di insert (k), lalu masukkan nilai dari elemen ke-k ke variabel temp.
2. tentukan bahwa j = k 􀃆 posisi dari j sampai i + 1 menggeser ke kanan.
3. masukkan temp ke a[i]

algoritmanya:
procedure insert(k,i)
begin
temp = a[k]
for j = k downto i + 1
a[j] = a[j-1]
endfor
a[i] = temp
end

misalkan ada 10 elemen, yaitu

Gambar

Gambar
Gambar
Gambar

Gambar
Gambar

ALGORITMA DAN STRUKTUR DATA : BAB 14

14.1 Graph

Graph adalah suatu struktur data yang berbentuk network / jaringan dimana hubungan antara
elemen-elemennya adalah many-to-many . contoh dalam kehidupan sehari-hari yang berbentuk
graph ini cukup banyak , misalnya: hubungan dosen dengan mahasiswa, dimana satu dosen bisa
mengajar lebih dari satu mahasiswa, dan satu mahasiswa dapat memiliki lebih dari satu dosen.
Graph terdiri dari Node ( VERTEX) dan ARC ( EDGE ). Yang dimaksud degan Node adalah
elemen graph yang berisi informasi sedangkan ARC (Edge ) dalah Path yang menghubungkan
dua buah node. Dua buah node yang dihubungkan dengan edge juga disebut Adjacent Node.

Gambar

Teminologi

Suatu subset / bagian dari Graph dinamakan SubGraph. Sedangkan yang disebut dengan Path
adalah hubungan dari kumpulan node-node dimana tiap node dengan node berikutnya
dihubungkan dengan Edge. Sebuah path dikatakan simple path bila setiap node hanya “muncul”
satu kali dalam path tersebut.

Graph dibedakan atas dua tipe , yaitu :

• Undirected GRAPH
Jika sepasang node yang membentuk edge dalam graph tidak berarah seperti ditunjukkan
oleh gambar di bawah ini :

Gambar
Gambar 14.2: Undirected Graph

Gambar

Bila ada minimal sepasang node mempunyai hubungan maka graph tersebut UnConnected Graph
seperti gambar di bawah ini :

Gambar

Jika node pertama dan node terakhir dalam graph adalah sama,maka graph tersebut dinamakan
Cycle Graph. Apabila semua edge dalam graph diberi nilai ( value ) , maka graph tersebut
dinamakan Weight Graph.

1. Representasi Graph
Graph dapat direpresentasi Graph dengan dua cara yaitu : Adjancency List dan Adjacency Matrix.
Dengan mempergunakan gambar di bawah ini sebagai contoh maka representasi graph dengan
masing-masing cara dapat dijelaskan sebagai berikut :

Gambar

a) Adjacency List

Gambar

14.2 Graph Traversal
Sama seperti Tree , maka dalam graph juga dikenal operasi Graph Traversal, yaitu penelusuran
semua node di dalam graph. Ada 2 cara untuk melakukan Traversal dalam Graph yaitu ;
Breadth First Search dan Depth First Search.

prosedur pencarian Breadth-First Search menggunakan ADT Queue dalam pemrosesan
node, sebaliknya untuk Depth First Search kita mengunakan ADT Stack.
Selama pemrosesan dari algoritma, setiap node didalam graph akan berada pada 3 keadaan
dibawah ini, yang disebut status dari n, 3 keadaan tersebut sebagai berikut:
STATUS = 1: (Ready status) keadaan awal dari setiap node.

STATUS = 2: (Waiting status) node N sudah berada pada queue atau stack, menunggu untuk
pemrosesan selanjutnya.

STATUS = 3: (Processed status) node N sudah diproses.

• Breadth-First Search
Inti dari Breadth First Search(BFS) sendiri adalah pencarian yang dimulai dari root A. Pertama
kita periksa root-nya A, setelah itu node – node yang bertetanggaan dengan A. Setelah
selesai baru kita periksa semua node tetangga A yang bertentanggaan lagi, dan seterusnya.
Selanjutnya kita harus mengikuti semua tetangga dari A dengan cermat, jangan sampai ada
satu node yang diproses lebih dari satu kali. Semuanya dapat dilakukan dengan bantuan
queue yang menyimpan node yang menunggu untuk diproses dan dengan menggunakan field
STATUS untuk mengetahui status dari node.
Algoritmanya:

1. inisialisasi semua node dalam keadalam ready. (STATUS = 1).
2. letakkan root in queue dan ganti statusnya menjadi tunggu (STATUS = 2).
3. ulangi langkah 4 dan 5 sampai queue kosong:
4. pindahkan depan node N di queue. Proses N dan ganti statusnya menjadi sudah
diproses (STATUS = 3).
5. tambahkan ke belakang dari queue semua tetangga dari N yang dalam status ready
saja (STATUS = 1), lalu ganti statusnya (STATUS = 2)
6. exit.
Catatan: algortima diatas akan memeriksa hanya node yang dapat di capai oleh node A saja.

Gambar

A      FRONT = 1                                       QUEUE: A
REAR = 1                                          ORIG: 0

B      FRONT = 2                                       QUEUE: A, F, C, B
REAR = 4                                          ORIG: 0, A, A, A

C      FRONT = 3                                       QUEUE: A, F, C, B, D
REAR = 5                                          ORIG: 0, A, A, A, F

D      FRONT = 4                                       QUEUE: A, F, C, B, D
REAR = 5                                          ORIG: 0, A, A, A, F

E      FRONT = 5                                       QUEUE: A, F, C, B, D, G
REAR = 6                                          ORIG: 0, A, A, A, F, B

F      FRONT = 6                                       QUEUE: A, F, C, B, D, G
REAR = 6                                          ORIG: 0, A, A, A, F, B

G      FRONT = 7                                      QUEUE: A, F, C, B, D, G, E
REAR = 7                                        ORIG: 0, A, A, A, F, B, G

H       FRONT = 8                                      QUEUE: A, F, C, B, D, G, E, J
REAR = 8                                         ORIG: 0, A, A, A, F, B, G, E

Dikarenakan J adalah tujuannya maka berhenti proses tersebut dan balik arah dari J ke A dengan
menggunakan array ORIG untuk mendapatkan path, sehingga didapatkan:
J < E < G < B < A

• Depth-First Search
ide dari DFS ini hampir sama dengan BFS, hanya saja pada DFS kita akan menggunakan
struktur data Stack. Prosesnya pun sama dengan menggunakan ketiga status yang kita
gunakan juga pada BFS.

Algortimanya:
1. inisialisasi semua node dalam keadalam ready. (STATUS = 1).
2. letakkan root in queue dan ganti statusnya menjadi tunggu (STATUS = 2).
3. ulangi langkah 4 dan 5 sampai queue kosong:
4. pindahkan depan node N di queue. Proses N dan ganti statusnya menjadi sudah
diproses (STATUS = 3).
5. tambahkan ke belakang dari queue semua tetangga dari N yang dalam status ready
saja (STATUS = 1), lalu ganti statusnya (STATUS = 2)
6. exit.
Catatan: algortima diatas akan memeriksa hanya node yang dapat di capai oleh node A saja.

Contoh DFS:
Misalkan kita akan mencari semua node yang bisa di jangkau oleh node J:

a. push J kedalam stack
STACK: J

b. pop, dan cetak elemen teratas J, kemudian push kedalam stack semua neighbor J (yang
berada pada status READY)
PRINT: J STACK: D, K

c. pop, dan cetak elemen teratas K, kemudian push kedalam stack semua neighbor K (yang
berada pada status READY)
PRINT: K STACK: D, E, G

d. pop, dan cetak elemen teratas G, kemudian push kedalam stack semua neighbor dari G (yang
berada pada status READY)
PRINT: G STACK: D, E, C

e. pop, dan cetak elemen teratas C, kemudian push kedalam stack semua neighbor dari C (yang
berada pada status READY)
PRINT :C STACK: D, E, F

f. pop, dan cetak elemen teratas F, kemudian push kedalam stack semua neighbor dari F (yang
berada pada status READY)
PRINT: F STACK: D, E

g. pop, dan cetak elemen teratas E, kemudian push kedalam stack semua neighbor dari E (yang
berada pada status READY)
PRINT: E STACK: D

h. pop, dan cetak elemen teratas D, kemudian push kedalam stack semua neighbor dari D (yang
berada pada status READY)
PRINT: D STACK:

Stack dalam keadaan kosong sekarang, selesainya proses traversal DFS dari node J. Hasilnya
yang tercetak adalah:
J,K, G, C, F, E, D

ALGORITMA DAN STRUKTUR DATA : BAB 11

11. 1 HEAP (COMPLETE BINARY TREE )

Heap atau sering juga disebut Complete Binary Tree harus memenuhi karakteristik ini :
• Jika suatu node mempunyai child, maka jumlah childnya harus selalu dua.
• Semua node dalam heap harus memenuhi persamaan :

  • r[i] < r[2] dan r[i] < r[2i+1] untuk minimum Heap, yang mempunyai arti bahwa nilai
    parent harus selalu lebih kecil dari kedua anaknya.
  • r[i] > r[2i] dan r[i] > r[2i+1] untuk maximum Heap, yang mempunyai arti bahwa nilai
    parent harus selalu lebih besar dari kedua anaknya.

Gambar di bawah ini memperlihatkan contoh minimum Heap

Gambar
Gambar 11.1: Minimum heap

Representasi dengan menggunakan ARRAY akan menghasilkan

Gambar

Sedangkan gambar di bawah ini merupakan contoh untuk maksimum Heap

Gambar
Gambar 11.2: Maximum heap

Representasi dengan menggunakan ARRAY akan menghasilkan

Gambar

 

11. 2 OPERASI HEAPCREATE

Operasi HeapCreate berfungsi untuk menciptakan heap, dengan cara mengurutkan nilai dari
nodanya, Prosedur untuk melakukan HeapCreate adalah sebagai berikut :
1. Mulai dari LEAF,yang mana semua LEAF telah memenuhi persyaratan HEAP.

2. Ambil salah satu parent dari LEAF, teliti apakah sudah memenuhi syarat HEAP (harus
ditentukan terlebih dahulu apakah yang ingin diciptakan adalah maksimum HEAP atau
minimum HEAP ).

3. Bila belum memenuhi persyaratan, maka lakukan tukar tempat :
• Untuk maksimum HEAP, tukar tempat parent dengan child yang paling BESAR.
• Untuk minimu HEAP, tukar tempat Parent dengan child yang paling kecil.

Contoh :
Apabila diketahui TREE di bawah ini, yang masih belum memenuhi persyaratan Maksimum HEAP,
lakukan operasi HeapCreate.

Gambar

Bila ditambahkan angka 90 ke dalam Tree yang berada di dalam kotak, maka Tree tersebut menjadi
tidak maksimum Heap lagi, yang harus dilakukan adalah tukar tempat antara 90 (parent) dengan 450
(Child yang mempunyai nilai paling besar), sehingga Tree tetap menjadi Maksimum Heap, Hasilnya
ditunjukan oleh gambar di bawah ini :

Gambar

Apabila ditambahkan angka 110 ke dalam Tree yang berada kotak, maka kembali Tree menjadi tidak
maksimum heap, lakukan hal sama seperti diatas, yaitu dengan menukarkan angka 110 (parent )
dengan angka 550 (Child dengan nilai paling besar), hasilnya ditunjukkan oleh gambar di bawah ini

Gambar

Apabila diteruskan dengan menambahkan angka 40 (parent) maka lakukan tukar tempat antara angka
40 dengan angka 450 (child dengan nilai paling besar). Ternyata setelah dilakukan tukar tempat,
masih belum menghasilkan maksimum Heap, karena masih ada child dari 40 yang nilainya lebih
besar. Lakukan lagi pertukaran tempat antara angka 40 dengan angka 90 hasilnya adalah sebagai
berikut :

Gambar

Langkah terakhir yang dilakukan adalah dengan menambahkan angka 80, yang harus tukar tempat
dengan angka 550, dilanjutkan dengan tukar tempat antara 80 dengan 330. Hasil akhir berupa
maksimum heap seperti ditunjukkan gambar di bawah ini:

Gambar

 

11. 3 B-TREE

B-Tree merupakan satu-satunya Tree yang mana Nodenya bisa berisi lebih dari 1 elemen. Jumlah
elemen dalam suatu node tergantung kepada Order dari B-Tree tersebut, dengan ketentuan:
Node ROOT :
• Jumlah minimum elemen 1
• Jumlah maksimum adalah 2d

Node lain yang bukan ROOT :
• Jumlah minimu elemen dalam setiap node (kecuali ROOT) adalah d.
• Jumlah maksimumnya adalah 2d, dimana d adalah order.

Hal ini yang dapat ditentukan pada B-Tree adalah jumlah children dari suatu node, yaitu minimunya
adalah 0 (berarti node tersebut adalah LEAF), dan maksimumnya adalah jumlah maksimumnya
elemen dalam node tersebut ditambah satu.

11.3.1 Operasi INSERT

Pada setiap kali penambahan (insert) elemen ke dalam node, harus dijaga agar jumlah elemen di
dalam node maksimunya adalah 2d. Ada 2 kasus yang dapat terjadi pada saat dilakukan insert
elemen ke dalam node yaitu :
Kasus 1 : Insert langsung

> jika node belum penuh yang berarti jumlah elemen dalam node masih < 2d, maka elemen
baru bisa langsung diinsert ke dalam node tersebut

Contoh :
Bila diketahui order dari B-Tree=2, yang berarti maksimum elemen pada sebuah node adalah = 2d =
4 elemen.
B-Tree sebelum di insert

Gambar

Kasus 2 :Insert dengan Split Node
􀃆 Jika node sudah penuh, yang berarti jumlah elemen dalam node sudag 2d. Maka
penambahan elemen baru mengakibatkan jumlah elemen menjadi > 2d hal ini tidak
diperkenankan karena maksimum elemen dalam node hanya 2d. Apabila terjadi hal ini,
maka perlu dilakukan Node Split dengan langkah:
• Split node menjadi 2
• Letakkan d elemen terkecil di node kiri
• Letakkan d elemen terbesar di node kanan
• Letakkan d elemen ditengah ke node parentnya
Contoh :
Diketahui B-Tree dengan Order = 2, dengan kondisi sebelum diinsert sebagai berikut ;

Gambar

 

11. 3. 2 Operasi DELETE
Kebalikan dari operasi Insert, maka dalam Operasi Delete harus dijaga agar dijumlah elemen dalam
node tidak lebih kecil dari d (atau untuk ROOT, minimal 1 elemen dalam node). Terdapat 3 kasus
yang dapat terjadi pada saat penghapusaan elemen yaitu :
Kasus 1 : Delete langsung
􀃆 Jika target node yang akan dihapus berisi elemen > d, maka elemen bisa langsung
dihapus tanpa perlu diregenerate. Dalam hal ini dapat langsung dihapus karena jumlah
elemen dalam node tersebut belum mencapai jumlah minimum.
Contoh :
Diketahui B-Tree dengan Order =2, dengan kondisi sebelum didelete sebagai berikut :

Gambar

 

Kasus 2: Delete dengan peminjaman elemen
􀃆 jika target node yang akan dihapus berisi d elemen , maka target elemen tidak bisa
langsung dihapus karena penghapusan langsung akan menyebabkan underflow. Untuk
mencegah terjadinya underflow maka harus dilakukan regenerasi yang akan dilakukan
dengan meminjam elemen dari node yang berada di kiri atau berada di kanan, yang
memiliki jumlah elemen > d. Langkah pengerjaannya adalah sebagai berikut :
• Delete target elemen dari node ybs.
• Pinjam elemen dari node yang memiliki jumlah elemen > d
• Jadikan elemen yang dipinjam menjadi parent ( ditarik ke atas).
• Parent yang semula dijadikan elemen dalam node ybs.

Contoh :
Bila diketahui B-Tree dengan Order =2 dengan kondisi seperti ditunjukan oleh gambar di bawah ini :

Gambar

 

ALGORITMA DAN STRUKTUR DATA : BAB 10

BINARY SEARCH TREE & AVL TREE

10.1 Binary Search Tree

Kelemahan dari Binary Tree yang telah dibahas pada bab sebelumnya adalah tidak efisien dalam
pencarian (searching the target Node), yang harus dilakukan secara sequensial dari mulai ROOT
sampai ke Node yang dikehendaki. Selain juga penghapusan terhadap Node Binary Tree tidak dapat
dilakukan, yang dapat dilakukan penghapusan 1 sub tree. Hal ini disebabkan karena pada Binary Tree
node tidak diurut. Binary Search Tree mengeliminir kelemahan tersebut diatas, dengan cara
mengurutkan node yang ada.

Ketentuan peletakkan node dalam binary search tree adalah sebagai berikut :
• Semua LEFT CHILD harus lebih kecil dari pada PARENT dan RIGHT CHILD
• Semua RIGHT CHILD harus lebih kecil dari pada PARENT dan LEFT CHILD

Gambar ini merupakan contoh dari Binary Search Tree :

Gambar
Gambar 10.1: Binary Search Tree

Keuntungan dari Binary Search Tree dibandingkan dengan Binary Tree adalah :

• Searching / pencarian target node menjadi lebih efisien dan cepat dibandingkan dengan
Binary Tree.

• Penghapusan dapat dilakukan terhadap target node, bukan terhadap 1 subtree seperti pada
Binary Tree.
Semua operasi dalam Binary Tree bisa di implementasikan langsung pada Binary Search Tree ,
kecuali :
• INSERT
• UPDATE
• DELETEKEY
Karena operasi diatas dapat mengakibatkan Binary Search Tree tidak urut. Sehingga harus dilakukan
modifikasi terhadap posisi node agar Binary Search Tree tetap terurut.

OPERASI INSERT
Operasi insert pada Binary Search Tree dilakukan dengan cara mencari lokasi untuk node yang akan
di insert. Pencarian selaku dimulai dari ROOT, jika node yang akan diinsert ternyata lebih kecil dari
ROOT, maka akan dilakukan insert pada left sub tree sedangkan bila node yang akan diinsert lebih
besar dari ROOT, maka akan dilakukan insert pada right sub tree. Pencarian lokasi untuk node
diteruskan sampai memenuhi kondisi Binary Search Tree yaitu semua node yang berada pada left
sub tree lebih kecil dari parentnya, sedangkan yang berada pada right sub tree harus lebih besar dari
parentnya.

Berikut ini akan dilakukan operasi insert, yang langsung akan digambarkan Binary Search Tree
setelah dilakukan operasi insert

insert (20)
Gambar

insert (50)
Gambar

insert (40)
Gambar

Gambar 10.2: Operasi Insert pada BST

OPERASI DELETEKEY
Berbeda dengan Binary Tree dimana penghapusan harus dilakukan terhadap sebuah sub tree, maka
pada Binary Seacrh Tree, penghapusan dapat dilakukan terhadap sebuah node (key) tertentu.
Operasi deletekey dapat mengakibatkan Binary Search Tree menjadi tidak urut lagi, sehingga perlu
dilakukan rotasi terhadap Binary Search Tree tersebut agar menjadi urut kecuali, beberapa posisi
node pada saat dilakukan operasi deletekey adalah :

1. Node yang dihapus adalah LEAF, sehingga penghapusan akan tetap membuat Binary Search
Tree terurut. Bila yang terjadi adalah ini, maka operasi penghapusan dapat langsung
dilakukan.

2. Node yang dihapus adalah node yang memiliki node 1 child, sehingga child yang
bersangkutan dapat langsung dipindahkan untuk menggantikan posisi node yang dihapus.

3. Node yang akan dihapus memiliki 2 children (2 subtree), maka node yang diambil untuk
menggantikan posisi node yang dihapus adalah :
a. Bisa berasal dari left sub tree, dimana node yang diambil adalah node yang
mempunyai nilai paling besar (yang berada pada posisi paling kanan).
b. Bisa berasal dari Right Sub Tree, dimana node yang diambil adalah node yang
mempunyai nilai paling kecil (yang berada pada posisi paling kiri).
Dengan menggunakan gambar Binary Search Tree berikut ini ,akan diilustrasikan operasi deletekey
untuk masing-masing kondisi di atas.

Gambar

Posisi 1: jika yang didelete adalah LEAF, maka tidak perlu dilakukan modifikasi terhadap lokasi contoh :
Gambar

Posisi 2 : jika yang didelete adalah NODE yang hanya memilki 1 child, maka child tersebut langsung
menggantikan parentnya contoh :
Gambar

POSISI 3: jika yang didelete adalah NODE dengan 2 children ( 2 Subtree), maka node yang diambil
untuk menggantikan posisi node yang dihapus adalah :

1. Berasal dari LEFT SUB TREE, yang diambil adalah node yang paling kanan
(yang mempunyai nilai yang terbesar)
2. Atau dari RIGHT SUBTREE, yang diambil adalah node yang paling kiri ( yang
mempunyai nilai yang terkecil).

10. 2 AVL TREE
Walaupun Binary SearchTree sudah dapat mengatasi kelemahan pada Binary Tree dengan cara
mengurutkan / sort node yang di-insert, di-update dan di-delete, tetapi masih ada kendala lain yang
dihadapai binary search tree , yaitu masih ada kemungkinan terbentuk skewed binary tree
(treemiring), yang mempunyai perbedaan height (height-balanced) antara subtree kiri dengan subtree
kanan sampai AVL (Adelson, Velskii dan Landis) Tree mengatasi hal ini dengan cara membatasi
height-balanced maksimum 1. AVL Tree dapat didefinisikan sebagai Binary Search Tree yang
mempunyai ketentuan bahwa “ maksimum perbedaan height antara subtree kiri dan subtree kanan
adalah 1”. AVL Tree juga sering disebut dengan height-balanced 1-tree. Gambar di bawah ini

memperlihatkan Binary Search Tree setelah dilakukan operasi insert sebagai berikut : +1, +2,
+3,……………..+n.

Gambar

Bila dilakukan pencarian terhadap node n diatas, maka pencarian sama seperti dilakukan pada Binary
Search Tree, yaitu pencarian menjadi sekuensi, yang memakan waktu lama, hal ini tidak mungkin
terjadi pada AVL Tree karena perbedaan height dibatasi maksimal hanya 1. berikut ini adalah contoh
ATL Tree dan yang bukan AVL Tree.

Gambar

Bila dilakukan pencarian terhadap node n diatas, maka pencarian sama seperti dilakukan pada Binary
Search Tree, yaitu pencarian menjadi sekuensi, yang memakan waktu lama, hal ini tidak mungkin
terjadi pada AVL Tree karena perbedaan height dibatasi maksimal hanya 1. berikut ini adalah contoh
ATL Tree dan yang bukan AVL Tree.

Gambar

Path pencarian lokasi untuk penentuan lokasi elemen pada operasi INSERT disebut dengan
Searching Path. Bila node pada search Path yang balancenya TallLeft (tanda-) tau TallRight (tanda +)
dan terletak paling dekat dengan node yang baru maka node tersebut dinamakan PIVOT POINT.
Gambar di bawah ini menunjukan pivot point :

Gambar

OPERASI INSERT
Agar AVL Tree dapat tetap mempertahankan Height-Balanced 1-Tree maka setiap kali pelaksanaan
operasi insert, jika diperlukan maka harus dilakukan rotasi. Operasi insert dalam AVL Tree ada 3
kondisi / kasus , yaitu :
• Case 1
Tidak ada Pivot Point dan setiap node adalah balance, maka bisa langsung diinsert sama
seperti pada Binary Search Tree (tanpa perlu diregenerate)

Gambar

• Case 2
Jika ada Pivot Point tetapi subtree yang akan ditambahkan node baru memiliki height yang
lebih kecil, maka bisa langsung diinsert .

Gambar

 

• Case 3
Jika ada Pivot point dan subtree yang akan ditambahkan node baru memiliki height yang lebih
besar, maka tree harus diregenerate , supaya tetap menghasilkan AVL Tree. Cara melakukan
re-generate adalah dengan melakukan :
o Single Rotation
o Double Rotation

Gambar

Contoh 1 : insert (5), sebelum dilakukan Single-Rotation
Gambar

 

Contoh 1

Gambar

(a) menunjukan sebelum ditambah angka 25, sedangkan gambar (b) menunjukkan setelah
ditambahkan angka 25 dan dilakukan Double – Rotation

kasus – kasus yang dapat diatasi dengan single rotation:
􀂃 kasus 1

Gambar

􀂃 kasus 2

Gambar

Gambar

Double Rotation
Pada beberapa kasus di AVL tree dapat diselesaikan hanya dengan cara single rotation, seperti pada
contoh diatas, tetapi ada pula yang tidak dapat diselesaikan hanya dengan single rotation, itu artinya
kita harus menggunakan teknik double rotation untuk menyelesaikan masalah imbalance pada tree.
􀂃 Kasus 1

Gambar

Gambar

Gambar

Operasi Delete
Operasi delete dalam AVL Tree adalah sama dengan operasi Deletekey dalam Binary Search Tree
(3 kasus yang bisa terjadi ). Yang harus diperhatikan adalah harus diusahakan agar pohon asli Delete
tetap berupa AVL-Tree yaitu dengan melakukan rotasi.

ALGORITMA DAN STRUKTUR DATA : BAB 9

TREE

9.1 TREE
Tree merupakan struktur data yang mempunyai hubungan One – to- Many, atau juga di sebut Nested /
Hirarki. Hubungan One-to-Many ini meliputi juga hubungan One- to – One, atau One-to-Zero, yang
dapat dijelaskan bahwa satu parent ( orang – tua ) bisa memiliki satu, atau nol atau lebih child (
anak ). Elemen dalam TREE disebut dengan NODE. Banyak sekali contoh yang bisa diberikan
mengenai tree ini. Seperti : hubungan orang – tua dengan anak ( satu ibu bisa mempunyai satu atau
lebih anak atau tidak memiliki anak ) hubungan bagian kerja dengan pekerjanya ( misal bagian
Penjualan memiliki lebih dari satu pekerja ) dan seterusnya.

Gambar

 

Gambar 9.1 : Contoh TREE

Karakteristik dari Tree adalah :
> Terdapat 1 node yang unique, yang tidak memiliki predecessor. Node ini disebut ROOT.
Kalau melihat ke contoh di atas, maka PERUSAHAAN merupakan ROOT.

> Terdapat satu atau beberapa node yang tidak mempunyai successor. Node ini disebut LEAF.
BAGIAN PEMBELIAN. BAGIAN LAINNYA, STAFF ( A ) , STAFF ( B ) dan STAFF ( C )
merupakan LEAF pada contoh di atas.

> Setiap node, kecuali ROOT, pasti memiliki 1 predecessor yang unique. Kembali dengan
mempergunakan contoh di atas, maka predecessor dari STAFF ( B ) PENJUALAN adalah
BAGIAN PENJUALAN, predescessor dari BAGIAN PEMBELIAN adalah PERUAHAAN.

> Setiap node, kecuali LEAF, pasti memiliki 1 atau lebih successor. Contoh successor dari
BAGIAN PENJUALAN adalah STAFF ( A ) , STAFF ( B ) dan STAFF ( C ).

Dibawah ini akan dijelaskan bebrapa istilah yang akan dipergunakan untuk menjelaskan tentang
TREE ( pembahasan di bawah akan mempergunakan TREE berikut sebagai contoh).

Gambar

 

HUBUNGAN PARENT CHILD

> PARENT adalah predecessor langsung dari suatu node, Semua node kecuali ROOT pasti
memiliki 1 PARENT yang unique.
Contoh : TREE pada gambar 1 diatas, PERUSAHAAN merupakan PARENT dan BAGIAN
PEMBELIAN, BAGIAN PENJUALAN dan BAGIAN LAINNYA.contoh TREE pada gambar 2
diatas B merupakan PARENT dari E, F.

> CHILD adalah Successor langsung dari suatu node, semua node kecuali LEAF pasti memiliki
1 atau lebih CHILD.
Contoh TREE pada gambar 1 diatas, BAGIAN PENJUALAN memiliki CHILD sebagai berikut
STAFF ( A ), STAFF ( B ) dan STAFF ( C ). Contoh TREE pada gambar 2 diatas, CHILD dari
node O adalah node R, T

> Node-node yang memiliki PARENT yangs sama disebut SIBLING.
Contoh TREE pada gambar 1 diatas STAFF ( A ) mempunyai SIBLING sebagai berikut TREE
( B ) dan staff ( C ) . contoh TREE pada gambar 2 di atas, node O mempunyai SIBLING K

HUBUNGAN ANCESTOR – DESCENDENT

> ANCESTOR adalah semua node yang berada di atas / sebelum node tertentu yang terdapat
pada path yang sama.
Contoh TREE pada gambar 2 diatas , node R mempunyai 4 buah ANCESTOR yaitu node O,
X, C, A.

> DESCENDAT adalah semua node yang berada di bawah / setelah node tertentu
Contoh TREE pada gambar 2 diatas, node C mempunyai 6 DESCENDAT, yaitu X, M, O, K, R,
T.

> TREE memiliki sifat yang dinamakan RECURSIVE, yang dapat di definisikan bahwa untuk
sebuah node tertentu , node tersebut beserta semua descedantnya adalah
SUBTREE dari parentnya. SUBTREE tersebut memiliki semua karakteristik dari suatu TREE.
Definisi lain yang berhubungan dengan height adalah TREE PATH-LENGTH, yaitu :

> Untuk SIMPLE TREE, path length adalah sama dengan JUMLAH NODE dikurangi 1.

> Secara umum, path length diambil dari path length dari subtree yang terpanjang ( atau tree
height dikurangi 1 ).

Gambar

 

Gambar 9.3 : RECURSIVE

Pada gambar di atas, terlihat bahwa A mempunyai 2 Subtree, yaitu Sub Tree 1 dan SubTree 2, yang
mana masing-masing subtree mempunyai karakteristik yang sama dengan tree keseluruhan, misalnya
tersebut ada ROOT, LEAF dll.

Setiap node dalam TREE pasti akan berada pada suatu level tertentu. Dimana ROOT dapat
didefinisikan memiliki level yang paling rendah yaitu 1 CHILD dari memiliki 1 level lebih tinggi dari
PARENTnya, sehingga CHILD dari ROOT dapat didefinisikan berada pada level 2 dstnya. Dengan
mengetahui level dari suatu node, maka TREE HEIGHT ( tinggi pohon ) dapat ditentukan , yaitu :

merupakan level paling tinggi dari nodenya sebagai contoh, tree pada gambar dibawah ini memiliki 11
node dan memiliki TREE HEIGHT 4.

Gambar
Gambar 9.4: TREE HEIGHT

 

9.2 BINARY TREE
Binary Tree memiliki semua karakterisktik dari TREE, yang menjadi perbedaan adalah bahwa
maksimum CHILD yang bisa dimiliki suatu node dalam BINARY TREE adalah 2 yang disebut LEFT
CHILD dari RIGHT CHILD. Gambar memperlihatkan contoh dari Binary Tree. Seperti terlihat pada
gambar, bahwa node dalam Binary Tree dapat memiliki 0, 1 atau maksimum 2 CHILD, contoh node W
memiliki 2 CHILD, node Y memiliki 1 CHILD ( yaitu LeftChild, berupa node T ) dan Node tidak memiliki
CHILD.

Gambar

Gambar 9. 5 : Binary Tree

 

Binary Tree dapat memiliki beberapa bentuk yaitu :

> Complete Binary Tree atau juga disebut HEAP. Definisi Complete Binary Tree adalah
sebuah Binary Tree yang bila semua nodenya memiliki 0 ( berarti LEAF ) atau 2 children .
berarti di dalam Completer Binary Tree, node tidak diperkenankan untuk memiliki hanya 1
child. Subtree dalam heap dapat mempunyai path length yang berbeda. Tree pada contoh 6
ini bukan merupakan Complete Binary Tree karena ada node yang memiliki hanya 1 child.
Gambar 7 menggambarkan contoh dari Complete Binary Tree.

Gambar
Gambar 9.6 : Complete Binary Tree

> Skewed Binary Tree, atau disebut Binary Tree Miring. Adalah Binary Tree yang bila semua
node, kecuali LEAF pasti memiliki hanya 1 child.

Gambar

Gambar 9.7 : Skewed Binary Tree

> Full Binary Tree adalah Binary Tree yang semua nodenya, kecuali LEAF harus memiliki 2
Children dan semua subtree harus memiliki path length yang sama. Gambar 9 menunjukan
contoh dari Full Binary Tree.

Gambar
Gambar 9.8 : Full Binary Tree

Berikut akan dibahas tentang operasi dalam Binary Tree.
Elemen : Elemen dalam Binary Tree disebut dengan node.
Struktur : Binary Tree akan memiliki struktur hirarki, yaitu disbut ROOT dan bila mempunyai
child, maka maksimum child yang dapat dimiliki adalah 2 ( left dan right child )
Operasi :

Traverse ( Ord : Order )

{ Operasi yang melakukan traversal / penelusuran terhadap node-node di dalam TREE.
Parameter pada operasi Traversal adalah Ord, yang menunjukan cara traversal yang
diinginkan , yaitu PreOrder, InOrder, atau PostOrder }.

  • Pre – Binary Tree tidak boleh EMPTY.
  • Post – Semua node dalam Tree akan dilewati, dan akan menghasilkan list sesuai dengan Order
    yang disebutkan dalam parameter Operasi traverse tidak akan mempengaruhi Tree dan posisi
    penunjuk Current tidak akan berubah.)

Case Ord of

  • PreOrder : Setiap node akan dilewati sebelum melewati node lainnya di dalam subtreenya.
  • InOreder : Setiap node akan dilewati setelah melewati subtree kirinya dan sebelum melewati
    subtree kanannya.
  • PostOrder : Setiap node akan dilewati setelah melewati subtree kiri dan subtree kanannya.

Insert ( e:Elemen Type ; Rel : Relative Position, Var fail : BOOLEAN )

{ Operasi untuk menambahkan 1 elemen ke dalam tree, berdasarkan posisi yang diinginkan,
seperti yang ditunjukkan oleh parameter Rel }

  • Pre – Jika rel = ROOT maka Binary TREE harus Empty
    Jika rel <> ROOT maka TREE harus tidak EMPTY
  • Post – e akan ditambah kedalam TREE pada posisi tergantung pada rel. Setelah di insert posisi
    current akan pindah ke ke e.

Case Rel of

  • ROOTV : Insert pada posisi ROOT
  • LeftChild : Insert sebagai LeftChild.
  • RightChild : Insert sebagai RightChild.
  • Parent ; Insert sebagai Parent akan selalu FALSE.

Delete Sub
{ Operasi menghapus subtree yang ditunjuk oleh posisi Current }

  • Pre – Binary Tree tidak EMPTY
  • Post – Subtree yang ditunjuk oleh posisi current akan dihapus dan Posisi current akan pindah ke
    node parent dari node yang dihapus.

Find ( rel : RelPosition; var fail : BOOLEAN )

  • Pre – Binary Tree tidak EMPTY
  • Post – Current akan pindah ke posisi Rel ( bisa ROOT, PARENT ) LEFTCHILD atau RIGHTCHILD ).

Empty : BOOLEAN
{ Operasi untuk mengetes apakah Binary Tree sudah ada nodenya atau masih kosong }

  • pre – Tidak ada
  • Post – Jika TREE belum berisi node maka EMPTY akan TRUE
    Jika TREE sudah berisi node mnaka EMPTY akan FALSE

Create
{ Operasi untuk menciptakan Binary Tree yang baru dan kosong }

  • pre – tidak ada
  • post – Binary Tree yang baru dan kosong akan terbentuk

CLEAR
{ Operasi untuk menghapus semua node yang ada di dalam Binary Tree }

  • pre – tidak ada
  • post – semua node akan terhapus dan binary tree menjadi kosong

Update ( e: Elemen Type )
{ Operasi untuk mengubah isi dari node yang ditunjuk oleh Current , posisi Current setelah operasi
ini tidak berubah }

  • pre – Binary Tree tidak EMPTY
  • post – isi node yang ditunjuk current akan di update dengan isi dari e

Retrieve ( Var e : Elemen Type )
{ Operasi untuk mengambil isi dari node yang ditunjuk oleh Current }

  • pre – tidak ada
  • post – e akan berisi data yang pada node ditunjuk oleh Current.

Characteristics ( Var St : status )
{ Operasi untuk menghitung size, tree height dan average length dari Binary Tree }

  • Pre – Binary Tree tidak EMPTY
  • Post – ST akan berisi informasi mengenai size ( banyak node ), tree height dan average length dari

Binary Tree
Rumus Average Length :
JmlNodeLevel1*1 + JumlNode Level 2*2 + …. + JmlNOde Level n*n

Average : Size

9.2.1 Operasi TRAVERSE ( Ord : Order )
pada bagian ini akan dijelaskan mngenai Operasi Traverse secara lebih rinci. Seperti telah dijelaskan
diatas, bahwa traverse adalah operasi untuk menelusuri node di dalam Binary Tree atau juga berlaku
untuk tree pada umumnya, sesuai dengan order yang diinginkan . order dapat berupa PreOrder,
InOrder, dan PostOrder. Untuk menjelaskan tentang operasi traverse , akan dipergunakan gambar
9.9, yang menggambarkan sebuah Tree ( yang dipergunakan di sini bukan Binary Tree )

Gambar
Gambar 9.9 : Tree dengan Sub Tree

 

PreOrder

Penelusuran terhadap Tree secara PreOrder akan melewati setiap node dalam tree sebelum
melewati node lainnya di dlam subtreenya. Dengan melihat gambar 10 di atas, dapat dijelaskan
bahwa PreOrder dari Tree T adalah Root n, kemudian diikuti oleh Sub Tree T1 dalam bentuk
PreOrder, kemudian diikuti oleh SubTree T2 dalam bentuk PreOrder, dstnya sampai Tn.

Untuk memberikan contoh yang lebih nyata, maka Traversal PreOrder terhadap Tree pada gambar 11
akan menghasilkan : B, N, L, G, Q, P, D, X

Gambar
Gambar 9.10: Contoh Tree untuk Traverse

Berikut algortima untuk penelusuran preorder
PreOrder (ROOT n)
{
If (n != NULL) {
printf(n->info);
PreOrder(n->Left);
PreOrder(n->Right);
}
}

> InOrder
Penelusuran terhadap Tree secara InOrder akan melewati setiap node dalam Tree setelah melewati
subtree kirinya dan sebelum melewati subtree kanannya. Dengan melihat gambar 10 maka dapat
dijelaskan bahwa InOrder dari TREE T adalah sub-tree T1, dalam bentuk InOrder, diikuti oleh Root n,
diikuti T2 dalam bentuk InOrder, sampai Tn.

Gambar
Gambar 9.11 : Expression Tree

InOrder : 7 + 5 * 6 ( INFIX )
PreOrder : +7 * 5 6 ( PREFIX )
PostOrder : 7 5 6 * + ( POSTFIX)

9.2.2 Implemetasi BINARY TREE
Binary Tree dapat diimplemetasikan baik dengan menggunakan Array ( dengan Array 2 dimensi ,
dimana satu berisi Parent, sedangakan dimensi lainnya berisi Nodenya sendiri ) seperti digambarkan
pada tabel berikut ini, atau dengan menggunakan Link-List ( dengan Double Lik-List, dimana satu
pointer menunjuk ke LeftChild, sedangkan pointer lainnya menunjuk ke RightChild ) seperti
digambarkan pada Gambar 12.

Implementasi Binary Tree dengan Array
Didalam array, indexnya menyatakan nomor node dari tree. Pada node root nomor index array adalah
0. Pada bahasa C, array di-index mulai dari nomor 0, maka binary tree dengan n-node akan diberi
nomor node mulai dari 0 sampai dengan n-1., dengan ketentuan sebagai berikut:

  • LeftChild dari suatu node dengan nomor p adalah 2p + 1
  • RightChild dari suatu node dengan nomor p adalah 2p + 2

Parent dari suatu node dengan nomor p adalah p-1/2. dalam bahasa C integer dibagi integer
hasilnya adalah integer. Contoh: 1 dibagi 2 hasilnya 0.

Gambar

Binary tree-nya:

Gambar

Gambar
Posisi node dalam array

Implementasi Binary Tree dengan Link-List

  • Double Linked List

struct nodetype{
int info; //misal informasi bertipe integer
struct nodetype *left;
struct nodetype *right
};

LC = LEFT CHILD
RC = RIGHT CHILD

Gambar

 

ALGORITMA DAN STRUKTUR DATA : BAB 8

QUENUE

8.1 Implementasi Queue dengan struktur data Linked– List

Implementasi Queue dengan linked-list dapat menghindari masalah pengalokasian memory seperti
yang terjadi pada implementasi dengan array biasa ( dalam pembahasan di bab sebelumnya diajukan
circular array yang mengatasi permasalahan ini ). Hal ini dikarenakan alokasi memory yang bersifat
dinamis pada implementasi dengan menggunakan linked-list. Seperti halnya implementasi dengan
menggunakan array yang memerlukan dua buah penunjuk, maka implementasinya dengan link-list
juga memerlukan 2 penunjuk, yang bisa kita namakan head yang menunjuk posisi awal queue dan
tail tail menunjukkan posisi akhir queue.

Implementasi struktur data Queue dengan linked list dalam bahasa C

#include <stdio.h>
#include <malloc.h>
typedef int Elementype;
struct Node {
ElemenType data;
struct Node *next;
};
struct QUEUE{
struct Node *Head;
struct Node *Tail;
};
Struktur Data Dengan Bahasa C – 65 –
Bab 8 Queue II
struct QUEUE Q;
void create()
{
Q.Head = NULL;
Q.Tail = NULL;
}
Int empty()
{
if(Q.Head == NULL) return (1);
else return (0);
}
void enqueue(ElemenType e)
{
struct Node *Temp;
Temp = (struct Node*) malloc(sizeof(struct Node));
Temp -> data = e;
Temp -> next = NULL;
if(empty()){
Q.Head = Temp;
Q.Tail = Temp;
}
else {
Q.Tail-> next = Temp;
Q.Tail = Temp;
}
}

Gambar

Gambar 8.1: Beberapa operasi enqueue pada queue dengan linked list

void dequeue(ElemenType *e)
{
struct Node *Temp;
if(empty()) printf(“Queue masih kosong\n”);
else{
Temp = Q.Head;
Q.Head = Q.Head->next;
*e=Temp->data;
free(Temp);
}
}

Gambar

 

Gambar 8.2: Operasi dequeue pada queue dengan linked list

Priority Queue
Priority Queue adalah queue dengan basis HPIFO ( Highest Priority In First Out ). Berbeda
dengan queue yang sangat tergantung kepada waktu kedatangan ( elemen yang datang
pertama akan selalu diambil / dihapus adalah elemen yang memilki priority tertinggi ( bila
yangmenjadi prioritas adalah waktu kedatangan maka Priority Queue berfungsi seperti queue
biasa ).

Priority Queue dibedakan atas 2 tipe yaitu ;

  1. Ascending Priority Queue; adalah Queue yang diurutkan dengan prioritas menarik.
  2. Descending Priority Queue; adalah queue yang diurutkan dengan prioritas menurun.

Untuk merepresentasikan Priority Queue dapat dilakukan dengan 3 cara : yaitu set, list dan
array. Dengan representasi set, data dimasukkan ke dalam ke dalam queue (enQueue),
berdasarkan waktu kedatangan, sedangkan pengambilannya ( dequeue ) tetap berdasarkan
prioritas. Keuntungan representasi set adalah operasi enQueue sngat cepat dan sederhana ,
tetapi operasi deQueue menjadi sangat kompleks karena diperlukan pencarian elemen dengan
prioritas tertinggi. Sedangkan dengan representasi list, data dienQueue dan dideQueue
berdasarkan prioritas. Gambar berikut menggambarkan posisi dari priority queue yang
direpresentasikan dengan set dan list bila dilakukan operasi sebagai berikut.
Create; enQueue (12); enQueue (117); enQueue (25); deQueue (e) .

Gambar
Gambar 8.4: Representasi queue dengan struktur data LIST

Procedure berikut ini merupakan implementasi dengan menggunakan struktur data array untuk priority
queue.

#include <stdio.h>
#define PJG_MAX 20
typedef int DataType;
typedef struct Elemen ElemenType;
int Jum_El, Head;
struct Elemen {
DataType data;
int priority;
};
ElemenType Q[PJG_MAX];
void create()
{
int Jum_El = 0;
int Head = 0;
}
int empty()
{
if(Jum_El == 0) return (1);
else return (0);
}
int full()
{
if(Jum_El == PJG_MAX – 1) return (1);
else return (0);
}
void move_queue_down(int awal, int akhir)
{
int i;
for(i=akhir; i>= awal; i–) Q[i] = Q[i-1];
}
void move_queue_up(int awal, int akhir);
{
int I;
for(i=awal; i<= akhir; i++) Q[i] = Q [i+1];
}
void enqueue(ElemenType e)
{
int Pos;
Pos = Head;
if(full()) printf(Queue sudah penuh\n):
else {
while ((e.priority < Q[Pos].priority && (Jum_El > Pos)) Pos = Pos +1;
if (Jum_el > Pos) move_queue_down(Pos+1, Jum_El);
Q[Pos] = e;
Jum_El = Jum_El +1;
}
}
void dequeue(ElemenType *e);
{
if(empty()) printf(Queue masih kosong\n);
else{
*e=Q[Head];
Jum_El = Jum_El – 1;
if(!empty())move_queue_up(Head, Jum_El-1);
}
}

 

ALGORITMA DAN STRUKTUR DATA : BAB 7

7.1 Implementasi Queue dengan struktur data Linked– List

Implementasi Queue dengan linked-list dapat menghindari masalah pengalokasian memory seperti yang terjadi pada implementasi dengan array biasa ( dalam pembahasan di bab sebelumnya diajukan circular array yang mengatasi permasalahan ini ). Hal ini dikarenakan alokasi memory yang bersifat dinamis pada implementasi dengan menggunakan linked-list. Seperti halnya implementasi dengan menggunakan array yang memerlukan dua buah penunjuk, maka implementasinya dengan link-list juga memerlukan 2 penunjuk, yang bisa kita namakan head yang menunjuk posisi awal queue dan tail tail menunjukkan posisi akhir queue.

Implementasi struktur data Queue dengan linked list dalam bahasa C

#include <stdio.h>
#include <malloc.h>

typedef int Elementype;

struct Node {
ElemenType data;
struct Node *next;
};

struct QUEUE{
struct Node *Head;
struct Node *Tail;
};

struct QUEUE Q;
void create()
{
Q.Head = NULL;
Q.Tail = NULL;
}

Int empty()
{
if(Q.Head == NULL) return (1);
else return (0);
}

void enqueue(ElemenType e)
{
struct Node *Temp;
Temp = (struct Node*) malloc(sizeof(struct Node));
Temp -> data = e;
Temp -> next = NULL;
if(empty()){
Q.Head = Temp;
Q.Tail = Temp;
}
else {
Q.Tail-> next = Temp;
Q.Tail = Temp;
}
}

Image

Beberapa operasi enqueue pada queue dengan linked list

Image

Operasi dequeue pada queue dengan linked list

 

Priority Queue
Priority Queue adalah queue dengan basis HPIFO ( Highest Priority In First Out ). Berbeda dengan queue yang sangat tergantung kepada waktu kedatangan ( elemen yang datang pertama akan selalu diambil / dihapus adalah elemen yang memilki priority tertinggi ( bila yangmenjadi prioritas adalah waktu kedatangan maka Priority Queue berfungsi seperti queue biasa ).

Priority Queue dibedakan atas 2 tipe yaitu ;

> Ascending Priority Queue; adalah Queue yang diurutkan dengan prioritas menarik.
> Descending Priority Queue; adalah queue yang diurutkan dengan prioritas menurun.

Untuk merepresentasikan Priority Queue dapat dilakukan dengan 3 cara : yaitu set, list dan array. Dengan representasi set, data dimasukkan ke dalam ke dalam queue (enQueue), berdasarkan waktu kedatangan, sedangkan pengambilannya ( dequeue ) tetap berdasarkan prioritas. Keuntungan representasi set adalah operasi enQueue sngat cepat dan sederhana , tetapi operasi deQueue menjadi sangat kompleks karena diperlukan pencarian elemen dengan prioritas tertinggi. Sedangkan dengan representasi list, data dienQueue dan dideQueue berdasarkan prioritas. Gambar berikut menggambarkan posisi dari priority queue yang direpresentasikan dengan set dan list bila dilakukan operasi sebagai berikut.

Create; enQueue (12); enQueue (117); enQueue (25); deQueue (e)

Image

Representasi Queue dengan struktur data SET

Image

Representasi queue dengan struktur data LIST

Procedure berikut ini merupakan implementasi dengan menggunakan struktur data array untuk priority queue.

#include <stdio.h>

#define PJG_MAX 20

 

typedef int DataType;

typedef struct Elemen ElemenType;

 

int Jum_El, Head;

 

struct Elemen {

DataType data;

int priority;

};

 

ElemenType Q[PJG_MAX];

 

void create()

{

int Jum_El = 0;

int Head = 0;

}

int empty()

{

if(Jum_El == 0) return (1);

else return (0);

}

 

int full()

{

if(Jum_El == PJG_MAX – 1) return (1);

else return (0);

}

 

void move_queue_down(int awal, int akhir)

{

int i;

for(i=akhir; i>= awal; i–) Q[i] = Q[i-1];

}

 

void move_queue_up(int awal, int akhir);

{

int I;

for(i=awal; i<= akhir; i++) Q[i] = Q [i+1];

}

 

void enqueue(ElemenType e)

{

int Pos;

Pos = Head;

if(full()) printf(Queue sudah penuh\n):

else {

while ((e.priority < Q[Pos].priority && (Jum_El > Pos)) Pos = Pos +1;

if (Jum_el > Pos) move_queue_down(Pos+1, Jum_El);

Q[Pos] = e;

Jum_El = Jum_El +1;

}

}

 

 

 

 

void dequeue(ElemenType *e);

{

if(empty()) printf(Queue masih kosong\n);

else{

*e=Q[Head];

Jum_El = Jum_El – 1;

if(!empty())move_queue_up(Head, Jum_El-1);

}

}

 

Latihan/ Tugas:

Apa yang dicetak dilayar monitor oleh main program dibawah ini

void main()

{

ElemenType x;

x.data=23;

x.priority=23;

enqueue(x);

 

x.data=44;

x.proirity=1;

enqueue(x);

 

x.data=45;

x.priority=7;

enqueue(x);

 

x.data=45;

x.priority=0;

enqueue(x);

 

dequeue(&x);

printf(“Data=%d Priority =%d\n”,x.data,x.priority);

dequeue(&x);

printf(“Data=%d Priority =%d\n”,x.data,x.priority);

dequeue(&x);

printf(“Data=%d Priority =%d\n”,x.data,x.priority);

dequeue(&x);

printf(“Data=%d Priority =%d\n”,x.data,x.priority);

}

ALGORITMA DAN STRUKTUR DATA : BAB 6

6.1 Definisi Queue

Queue merupakan satu bagian dari tipe data abstrak yang dibicarakan pada bab 5. Queue adalah suatu tipe data yang mengikuti pola First In First Out (FIFO), yang berarti elemen yang pertama masuk adalah elemen yang pertama pula dikeluarkan. Banyak contoh dalam kehidupan sehari-hari yang menerapkan konsep dari Queue, atau yang dalam bahasa Indonesia lebih dikenal dengan istilah antrian seperti antrian pasien di ruang tunggu dokter, antrian penonton yang membeli tiket, dsbnya. Sama halnya seperti stack, queue juga merupakan satu tipe data abstrak yang pengimplementasiannya bebas, artinya dapat diimplemetasikan dengan array maupun dengan list.

Image

Illustrasi Struktur data QUEUE

6. 2 Implementasi Queue dengan struktur data Array

Untuk setiap struktur data queue yang diimplementasikan dengan array, posisi front (depan) back (belakang) akan selalu ada. Perhatikan gambar berikut ini menunjukkan ilustrasi dari sebuah queue yang diimplementasikan dengan menggunakan array. Dua hal yang menarik perhatian adalah (1) queue bergerak dari indeks kecil menuju indeks yang besar dan (2) diperlukan dua buah penunjuk (dalam ilustrasi disebut head dan tail)

Image

Hal yang menarik, sekaligus merupakan kelemahan dari implementasi ini terjadi bila tail dari queue telah merambat sampai keposisi pjg_max maka queue tersebut tidak dapat diisi lagi walaupun sebenarnya queue tersebut belum penuh ( area yang berada di posisi 1 sampai head sebenarnya merupakan tempat yang kosong). Ilustrasinya digambarkan berikut ini.

Image

6. 3 Circular Array

Ide yang paling sederhana adalah dengan mengisi tempat kosong (jika tersedia) yang berada pada awal array bila tail telah mencapai posisi pjg_max sehingga penggunaan tempat menjadi lebih efisien. Jadi seolah-olah array di bawah ini dibulatkan manjadi sebuah lingkaran seperti digambarkan berikut ini (nama circular array berasal dari ide array yang dibulatkan).

Image

 

Circular Array

Berikut adalah program C untuk mengimplementasikan Queue dengan menggunakan circular array.

#include <stdio.h>
#define PJG_MAX 10
Typedef int elemenType;
elementypeQ[PJG_MAX];
int head, tail;

void create()
{
Head = 0; 
Tail = PJG_MAX -1;
}

void enqueue(elemenType e)
{
if(full()) printf(“queue sudah penuh\n”);
else {
Tail++;
Tail = Tail % PJG_MAX;
Q[Tail] = e;

}

 

void dequeue(elemenType*e)
{
if(empty()) printf(“Queue kosong\n”);
else {
*e = Q[head];
Head++;
Head = Head % PJG_MAX;
}
}
int empty()
{
if(((tail+1) % PJG_MAX) == Head) return (1);
else return (0);
}

void full()
{
int x;
x = Tail+2;
x = x % PJG_MAX;
if(x == Head) return (1); 
else return (0);
}

Image

 

Array setelah di CREATE / CLEAR

Image

Image

Beberapa operasi enqueue dengan circular array

 

Image

Operasi dequeue pada queue dengan circular array

ImageImage

Beberapa contoh Queue dalam kondisi EMPTY

 

Salah satu hal penting yang harus diperhatikan pada Circular array adalah kondisi seperti pada gambar di atas yang menunjukan bahwa array telah FULL terisi. Bila array di atas check dengan menggunakan function EMPTY maka pada kondisi yang bersamaan akan  dihasilkan  EMPTY = TRUE. Hal ini dapat diatas dengan mencegah array agar tidak terisi sampai penuh seperti di atas, dimana bila tersisa satu tempat kosong maka itu sudah menunjukan kondisi FULL dan tidak boleh diisi lagi, hal ini dilakukan untuk membedakan antara kondisi FULL dengan kondisi EMPTY . Gambar berikut ini menggambarkan  kondisi FULL seperti yang dimaksud dan dengan function FULL akan mencegah  terjadi full yang dimaksud diatas.Image

Array sudah FULL terisi

 

Algoritma dan Struktur Data : Bab 5

5.1  Aplikasi Stack

 

Stack mempunyai aplikasi yang sangat luas di bidang komputer, salah satu aplikasi yang akan kita bahas di sini adalah penggunaan stack dalam  polish notation ( notasi polish ). Sebelum dibahas tentang bagaimana penggunaan stack ini, akan disinggung terlebih dahulu tentang apakah polish notation ini.

 

Didalam menuliskan ekspresi matematika, kita selalu mempergunakanoperator dan operand. Operator adalah tanda operasi yang dipergunakan, diantaranya + (penjumlahan) , – (pengurangan), * (perkalian),  / (pembagian), ^ (pangkat), dsbnya. Sedangkan operand adalah identifier yang dipergunakan sebagai symbol, misalnya alphabet a/A … z/Z. selain operator dan operand, di dalam pengerjaan ekpresi matematika harus diperhatikan juga mengenai prioritas dari operator, dengan urutan sebagai berikut:

 

1.() Operasi dalam tanda kurung akan dikerjakan paling awal.

2. ^ ( pangkat )

3. * ( Perkalian dan / ( pembagian ).

4. + ( penjumlahan ) dan – ( pengurangan ).

 

 

 

Notasi yang dipergunakan untuk menuliskan ekspresi matematika ada tiga yaitu :

>   INFIX

Suatu notasi disebut infix jika operator  berada diantara operandnya. Notasi ini merupakan notasi yang sering kita gunakan sehari – hari.

Contoh : ( A+ B ) * ( C + D ).

 

>   PREFIX

Notasi disebut prefix,  atau sering juga di sebut  Polish Notation  ( diambil dari nama penemunya ) jika operator berada di depan dari kedua operandnya.

Contoh : +AB * + CD

 

>   POSTFIX

Suatu notasi akan disebut postfix atau  suffix  atau juga dikenal sebagai  Reverse Polish Notation  bila operator berada di belakang kedua operandnya.

Contoh : AB + CD +*.

 

INFIX

Algoritma pengerjaan operasi matematika dengan notasi infix adalah sebagai berikut :

1. Scan dari kiri ke kanan sampai ketemu dengan kurung tutup yang paling awal.

2. Scan kembali dari posisi tadi ke kiri sampai  ketemu dengan kurung buka yang pertama.

3. Lakukan operasi yang berada di dalam tanda kurung.

4. Ganti ekspresi di dalam tanda kurung tersebut dengan hasil operasi.

5. Ulangi langkah 1 sampai 4 sehingga keseluruhan ekspresi dilaksanakan.

Image

Beberapa kelemahan dari notasi infix di antaranya adalah proses pengerjaan ekspresi sangat lama, diperlukan tanda kurung untuk menandai operasi yang lebih rendah prioritasnya, dan pengerjaan sangat tidak efisien.

POSTFIX/ SUFFIX / REVERSE POLISH

Notasi postfix atau juga disebut suffix atau reverse polish notation ( selanjutnya akan dipergunakan istilah postfix ) dapat mengatasi kelemahan dari notasi infix, di antaranya adalah tidak diperlukannya tanda kurung untuk menandai operasi yang lebih tinggi prioritasnya. Lebih cepat dan efisien karena tidak diperlukan scan dari awal ekspresi.

Berikut adalah algoritma pengerjaan operasi matematika dengan notasi postfix.
1. Scan dari kiri ke kanan sampai ketemu dengan tanda operator.
2. Ambil 2 operand yang berada langsung di sebelah kiri dari operator tersebut.
3. Lakukan operasi dan ganti ekspresi tersebut dengan hasil operasi.
4. ulangi langkah 1 sampai 3 hingga keseluruhan ekspresi dilaksanakan, scan dilakukan mulai dari posisi pergantian ekspresi, jadi tidak perlu menscan dari posisi paling awal.

Dengan contoh yang dikonversikan dari notasi infix , yaitu 10 15 + 20 * 200 +, maka hasil pengerjaan dengan menggunakan notasi postfix adalah sebagai berikut :

Image

KONVERSI INFIX KE POSTFIX
Setelah mengetahui keuntungan notasi postfix dibandingkan dengan notasi infix, maka pada umumnya compiler akan dipergunakan notasi postfix di dalam mengerjakan ekspresi yang ada. Permasalahannya adalah pengguna komputer ( user ) lebih menyukai dan lebih akrab dengan notasi infix dibandingkan dengan notasi postfix, oleh karena itu diperlukan algoritma yang mengkonversikan ekspresi yang ditulis oleh user dalam notasi infix ke dalam notasi postfix sehingga dpat dikerjakan oleh compiler.

Algoritma Konversi INFIX ke POSTFIX

Infixtopostfix()
{
Postfix=” ”;
Clear(STACK);
While(!eoln(infix)) {
Read(symb);
If(symb == operand) postfix = postfix + symb;
Else {
While(!empty(STACK)) && prcd(stack[top], symb) == TRUE) {
Pop(c);
Postfix = postfix + c;
}
Push(symb);
}
}
While (!empty(STACK)) {
Pop(c);
Postfix = postfix + c;
}
}

 

Seperti terlihat pada algoritma konversi di atas, diperlukan STACK sebagai penampungan atau penyimpan operand ( kita akan menemukan operasi stack seperti pop, push, clear dan empty dalam algoritma konversi ini ), selain itu ada function lain yang diperlukan;
Precedence atau disingkat prcd; yaitu sebuah function yang akan mengecek prioritas dari dua buah operator dan akan mengembalikan nilai TRUE bila operator pertama mempunyai prioritas lebih tinggi dari operator kedua.

Contoh prcd (’’*’’, ’’+’’) TRUE
prcd (’’+’’, ’’*’’) FALSE

Algoritma di atas hanya berlaku bagi notasi infix yang tidak mempergunakan tanda kurung, untuk notasi infix yang dipergunakan tanda kurung diperlukan sedikit modifikasi terhadap algoritma di atas.