Pelajari konsep dasar struktur data dan algoritma untuk merancang solusi komputasional yang efisien, terstruktur, dan dapat diterapkan pada berbagai masalah sains data.
Materi ini membahas tipe data statis dan dinamis, array, linked list, stack, queue, sorting, searching, analisis kompleksitas, tree, heap, binary search tree, AVL tree, B-tree, graph, serta algoritma pelacakan.
Pertemuan
Struktur & Algoritma
Evaluasi Utama
Algoritma dan struktur data merupakan dasar penting dalam merancang solusi komputasional yang efisien, terstruktur, dan mudah dikembangkan.
Algoritma adalah serangkaian langkah logis dan sistematis yang digunakan untuk menyelesaikan suatu permasalahan. Algoritma harus memiliki urutan proses yang jelas, menghasilkan keluaran, dan dapat diterapkan secara efektif.
Struktur data adalah cara untuk mengorganisasi, menyimpan, dan mengelola data agar dapat diakses serta dimanipulasi dengan efisien. Pemilihan struktur data yang tepat dapat memengaruhi kecepatan dan penggunaan memori suatu program.
Dalam mata kuliah ini, mahasiswa mempelajari struktur data linear seperti array, linked list, stack, dan queue. Selain itu, dibahas pula struktur data hierarki seperti tree, heap, binary search tree, AVL tree, dan B-tree, serta struktur graph.
Identifikasi masalah, kebutuhan data, input, proses, dan output yang diperlukan.
Tentukan struktur data yang sesuai dengan karakteristik dan kebutuhan permasalahan.
Susun langkah penyelesaian dan implementasikan algoritma menggunakan bahasa pemrograman.
Uji ketepatan solusi dan analisis kompleksitas waktu serta penggunaan ruang.
Contoh berikut menggunakan struktur data stack sederhana dengan prinsip LIFO, yaitu elemen yang terakhir dimasukkan akan menjadi elemen pertama yang dihapus.
Operasi append() digunakan untuk menambahkan
data ke stack, sedangkan pop() digunakan untuk
mengambil data paling akhir.
stack = []
stack.append("Data A")
stack.append("Data B")
stack.append("Data C")
print("Isi stack:", stack)
data_keluar = stack.pop()
print("Data yang keluar:", data_keluar)
print("Isi stack setelah pop:", stack)| Struktur Data | Karakteristik | Contoh Penggunaan |
|---|---|---|
| Array | Akses berdasarkan indeks | Data berukuran tetap dan berurutan |
| Linked List | Node saling terhubung | Data dinamis dan sering berubah |
| Stack | Prinsip LIFO | Undo, pemanggilan fungsi, dan parsing |
| Queue | Prinsip FIFO | Antrian layanan dan penjadwalan |
| Tree | Struktur hierarki | Folder, indeks, dan klasifikasi data |
| Graph | Hubungan antarvertex | Jaringan, peta, dan relasi sosial |
Setelah menyelesaikan mata kuliah ini, mahasiswa diharapkan mampu memahami, merancang, mengimplementasikan, dan menganalisis algoritma serta struktur data untuk menyelesaikan permasalahan komputasional.
Mahasiswa mampu memilih dan menggunakan struktur data serta algoritma yang tepat berdasarkan karakteristik masalah, kebutuhan efisiensi, dan ukuran data.
Kompetensi pembelajaran mencakup kemampuan teknis, analitis, dan pemecahan masalah yang dapat diterapkan pada pengembangan aplikasi serta pengolahan data.
| No. | Indikator | Kemampuan yang Diharapkan |
|---|---|---|
| 1 | Memahami konsep algoritma | Mahasiswa mampu menjelaskan pengertian, karakteristik, dan tahapan algoritma. |
| 2 | Memahami struktur data | Mahasiswa mampu membedakan struktur data linear, hierarki, dan graph. |
| 3 | Memilih struktur data | Mahasiswa mampu memilih struktur data sesuai dengan kebutuhan masalah. |
| 4 | Mengimplementasikan solusi | Mahasiswa mampu menerjemahkan algoritma ke dalam program. |
| 5 | Menganalisis kompleksitas | Mahasiswa mampu menghitung kompleksitas waktu dan ruang menggunakan notasi Big O. |
| 6 | Menguji program | Mahasiswa mampu menguji program menggunakan berbagai skenario input. |
| 7 | Mengevaluasi solusi | Mahasiswa mampu membandingkan beberapa solusi berdasarkan efisiensi dan ketepatan. |
Mempelajari array, linked list, stack, queue, tree, heap, dan graph.
Mempelajari searching, sorting, recursion, divide and conquer, BFS, dan DFS.
Menganalisis waktu eksekusi, penggunaan memori, dan performa algoritma.
Memahami teori, istilah, dan karakteristik algoritma serta struktur data.
Merancang langkah penyelesaian berdasarkan kebutuhan masalah.
Mengubah rancangan algoritma menjadi program yang dapat dijalankan.
Menguji dan membandingkan solusi berdasarkan ketepatan serta efisiensinya.
Latihan implementasi struktur data dan algoritma secara mandiri.
Pengembangan solusi berbasis masalah menggunakan struktur data tertentu.
Evaluasi teori, implementasi, analisis, dan pemecahan masalah.
Memori merupakan bagian penting dalam komputer yang digunakan untuk menyimpan instruksi, data, dan hasil pemrosesan program.
Memori adalah tempat penyimpanan data yang digunakan oleh komputer ketika menjalankan program. Setiap data yang diproses oleh program akan ditempatkan pada lokasi tertentu di dalam memori.
Dalam pemrograman, pemahaman terhadap memori membantu programmer mengetahui bagaimana variabel, array, objek, dan struktur data disimpan serta diakses oleh komputer.
Struktur data yang berbeda dapat menggunakan memori dengan cara yang berbeda. Oleh karena itu, pemilihan struktur data yang tepat berpengaruh terhadap performa dan efisiensi program.
Memori komputer memiliki tingkatan berdasarkan kecepatan, kapasitas, dan biaya. Memori yang paling dekat dengan prosesor biasanya memiliki kecepatan akses paling tinggi, tetapi kapasitasnya lebih kecil.
Memori tercepat yang berada di dalam prosesor dan digunakan untuk menyimpan data sementara.
Menyimpan data yang sering digunakan agar dapat diakses prosesor dengan lebih cepat.
Menyimpan program dan data yang sedang aktif digunakan oleh komputer.
Menyimpan data secara permanen meskipun komputer dimatikan.
Alokasi memori statis dilakukan ketika ukuran memori ditentukan sebelum program dijalankan. Ukuran data biasanya tetap selama program berjalan.
Alokasi memori dinamis dilakukan ketika program berjalan. Ukuran memori dapat bertambah atau berkurang sesuai dengan kebutuhan program.
Setiap lokasi penyimpanan di dalam memori memiliki alamat yang unik. Alamat tersebut digunakan oleh komputer untuk menemukan dan mengakses data.
| Alamat | Nilai |
|---|---|
| 1000 | 10 |
| 1004 | 20 |
| 1008 | 30 |
| 1012 | 40 |
Alamat memori dapat diibaratkan seperti nomor rumah. Nilai data adalah isi rumah tersebut, sedangkan alamat digunakan untuk menemukan lokasi data.
Variabel digunakan untuk menyimpan nilai yang dapat digunakan selama program berjalan. Dalam implementasinya, variabel memiliki nama, nilai, dan lokasi penyimpanan di dalam memori.
Ketika nilai variabel diubah, program dapat mengganti referensi atau isi data yang tersimpan di dalam memori, bergantung pada bahasa pemrograman yang digunakan.
nilai = 85
nama = "Andi"
status_lulus = True
print("Nama:", nama)
print("Nilai:", nilai)
print("Lulus:", status_lulus)Efisiensi memori menunjukkan seberapa baik program menggunakan ruang penyimpanan yang tersedia. Program yang efisien tidak hanya menghasilkan keluaran yang benar, tetapi juga menggunakan memori secara optimal.
Hindari menyimpan data yang sama secara berulang-ulang.
Gunakan struktur data sesuai kebutuhan operasi program.
Hapus data yang tidak lagi digunakan oleh program.
| Aspek | Statis | Dinamis |
|---|---|---|
| Waktu Alokasi | Sebelum program berjalan | Saat program berjalan |
| Ukuran Data | Tetap | Dapat berubah |
| Fleksibilitas | Lebih rendah | Lebih tinggi |
| Pengelolaan | Lebih sederhana | Lebih kompleks |
| Contoh | Array statis | Linked list dan tree |
Array adalah struktur data yang digunakan untuk menyimpan sekumpulan elemen dengan tipe data yang sama dalam lokasi memori yang berurutan.
Array adalah struktur data linear yang menyimpan beberapa nilai dalam satu variabel. Setiap elemen pada array dapat diakses menggunakan indeks.
Pada sebagian besar bahasa pemrograman, indeks array dimulai dari angka nol. Artinya, elemen pertama berada pada indeks 0, elemen kedua berada pada indeks 1, dan seterusnya.
Array cocok digunakan ketika jumlah data telah diketahui atau ketika program membutuhkan akses cepat berdasarkan posisi elemen.
Array dapat dibayangkan seperti sekumpulan kotak yang tersusun secara berurutan. Setiap kotak memiliki indeks dan menyimpan satu nilai.
| Indeks | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Nilai | 10 | 20 | 30 | 40 | 50 |
Deklarasi array dilakukan dengan menentukan nama variabel dan nilai-nilai yang akan disimpan. Dalam Python, array sederhana dapat dibuat menggunakan list.
Setiap elemen dapat diakses menggunakan tanda kurung siku dengan indeks elemen yang ingin diambil.
nilai = [80, 75, 90, 85, 95]
print("Array nilai:", nilai)
print("Elemen pertama:", nilai[0])
print("Elemen ketiga:", nilai[2])angka = [10, 20, 30, 40]
angka[1] = 25
print(angka)buah = ["Apel", "Mangga", "Jeruk"]
buah.append("Pisang")
print(buah)
Penelusuran atau traversal adalah proses mengunjungi setiap
elemen array secara berurutan. Dalam Python, penelusuran
dapat dilakukan menggunakan perulangan for.
angka = [10, 20, 30, 40, 50]
for nilai in angka:
print(nilai)Array dua dimensi digunakan untuk menyimpan data dalam bentuk baris dan kolom. Struktur ini sering digunakan untuk merepresentasikan tabel atau matriks.
Untuk mengakses data, diperlukan dua indeks, yaitu indeks baris dan indeks kolom.
matriks = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
print("Elemen baris 1 kolom 2:", matriks[0][1])
print("Matriks:")
for baris in matriks:
print(baris)| Operasi | Kompleksitas Umum | Keterangan |
|---|---|---|
| Akses berdasarkan indeks | $O(1)$ | Elemen dapat diakses langsung melalui indeks. |
| Pencarian linear | $O(n)$ | Elemen diperiksa satu per satu. |
| Penyisipan di akhir | $O(1)$ | Dapat berlangsung konstan jika ruang tersedia. |
| Penyisipan di tengah | $O(n)$ | Elemen lain mungkin perlu digeser. |
| Penghapusan di tengah | $O(n)$ | Elemen setelahnya perlu disesuaikan. |
Menyimpan kumpulan angka untuk proses perhitungan.
Merepresentasikan data dalam baris dan kolom.
Menyimpan data yang digunakan untuk visualisasi.
Menyimpan kumpulan data yang memiliki urutan.
Struct adalah tipe data bentukan yang digunakan untuk mengelompokkan beberapa data dengan tipe yang berbeda ke dalam satu kesatuan.
Struct atau structure merupakan tipe data yang dibuat oleh programmer untuk menggabungkan beberapa atribut yang saling berhubungan dalam satu objek.
Berbeda dengan array yang biasanya menyimpan data dengan tipe yang sama, struct dapat menyimpan beberapa data dengan tipe yang berbeda.
Sebagai contoh, data seorang mahasiswa dapat terdiri dari nama, nomor induk, umur, dan nilai. Semua data tersebut dapat dikelompokkan ke dalam satu struct bernama Mahasiswa.
Struct dapat digunakan untuk mengelompokkan informasi seorang mahasiswa seperti identitas, program studi, dan nilai akademik.
| Field | Tipe Data | Contoh Nilai |
|---|---|---|
| nama | String | Andi |
| nim | String | 231001 |
| umur | Integer | 20 |
| nilai | Float | 87.5 |
| aktif | Boolean | True |
Dalam bahasa C, struct dideklarasikan menggunakan kata
kunci struct. Setiap atribut di dalam struct
disebut sebagai member atau field.
Operator titik digunakan untuk mengakses field dari sebuah variabel struct.
#include <stdio.h>
#include <string.h>
struct Mahasiswa {
char nama[50];
int nim;
float nilai;
};
int main() {
struct Mahasiswa mhs;
strcpy(mhs.nama, "Andi");
mhs.nim = 231001;
mhs.nilai = 87.5;
printf("Nama: %s\n", mhs.nama);
printf("NIM: %d\n", mhs.nim);
printf("Nilai: %.2f\n", mhs.nilai);
return 0;
}Setiap field pada struct dapat diakses menggunakan nama variabel struct dan operator titik.
struct Mahasiswa {
char nama[50];
int umur;
float nilai;
};
struct Mahasiswa mahasiswa;
mahasiswa.umur = 20;
mahasiswa.nilai = 85.5;
printf("%d\n", mahasiswa.umur);
printf("%.2f\n", mahasiswa.nilai);Array of struct adalah kumpulan beberapa objek struct dengan tipe yang sama. Struktur ini berguna untuk menyimpan banyak data yang memiliki format serupa.
Contohnya adalah daftar mahasiswa, daftar produk, daftar pegawai, atau daftar buku.
#include <stdio.h>
struct Mahasiswa {
char nama[50];
int nim;
float nilai;
};
int main() {
struct Mahasiswa daftar[3] = {
{"Andi", 231001, 85.5},
{"Budi", 231002, 90.0},
{"Citra", 231003, 88.5}
};
for (int i = 0; i < 3; i++) {
printf("Nama: %s\n", daftar[i].nama);
printf("NIM: %d\n", daftar[i].nim);
printf("Nilai: %.2f\n\n", daftar[i].nilai);
}
return 0;
}Python tidak memiliki kata kunci struct seperti bahasa C. Namun, konsep struct dapat direpresentasikan menggunakan class atau dictionary.
Penggunaan class lebih sesuai jika data memiliki atribut dan perilaku yang ingin dikelompokkan.
class Mahasiswa:
def __init__(self, nama, nim, nilai):
self.nama = nama
self.nim = nim
self.nilai = nilai
mahasiswa = Mahasiswa(
"Andi",
"231001",
87.5
)
print("Nama:", mahasiswa.nama)
print("NIM:", mahasiswa.nim)
print("Nilai:", mahasiswa.nilai)| Aspek | Array | Struct |
|---|---|---|
| Jenis Data | Biasanya memiliki tipe yang sama | Dapat memiliki tipe yang berbeda |
| Akses Data | Menggunakan indeks | Menggunakan nama field |
| Tujuan | Menyimpan kumpulan data sejenis | Mengelompokkan atribut suatu objek |
| Contoh | Daftar nilai | Data mahasiswa |
| Representasi | Urutan elemen | Kumpulan atribut |
Menyimpan nama, NIM, program studi, dan nilai.
Menyimpan kode, nama, harga, dan stok produk.
Menyimpan nama, alamat, nomor telepon, dan email.
Menyimpan judul, penulis, ISBN, dan tahun terbit.
Tipe data statis adalah tipe data yang ukuran dan jenisnya ditentukan sebelum program dijalankan serta tidak berubah selama program berjalan.
Tipe data statis merupakan tipe data yang memiliki ukuran penyimpanan dan jenis data yang telah ditentukan sejak program dikompilasi atau sebelum program dijalankan.
Pada tipe data statis, sebuah variabel biasanya harus memiliki tipe data tertentu. Variabel tersebut hanya dapat menyimpan nilai yang sesuai dengan tipe data yang telah ditentukan.
Penggunaan tipe data statis membantu program menjadi lebih terstruktur, mudah dianalisis, dan dapat mendeteksi kesalahan tipe data lebih awal.
| Jenis Tipe Data | Fungsi | Contoh Nilai |
|---|---|---|
| Integer | Menyimpan bilangan bulat | 10, -5, 100 |
| Float | Menyimpan bilangan pecahan | 3.14, 75.5 |
| Character | Menyimpan satu karakter | 'A', 'B', '1' |
| String | Menyimpan kumpulan karakter | "Algoritma" |
| Boolean | Menyimpan nilai benar atau salah | True, False |
| Array | Menyimpan kumpulan data berurutan | [10, 20, 30] |
| Struct | Mengelompokkan beberapa atribut | Data mahasiswa |
Digunakan untuk menyimpan nilai bilangan tanpa angka di belakang koma.
int umur = 20;
Digunakan untuk menyimpan nilai yang memiliki angka desimal.
float nilai = 85.5;
Digunakan untuk menyimpan satu karakter atau kumpulan karakter.
char grade = 'A';
Pada bahasa C, setiap variabel harus dideklarasikan menggunakan tipe data tertentu sebelum digunakan.
Deklarasi tipe data membantu compiler mengetahui jumlah memori yang diperlukan dan jenis operasi yang dapat dilakukan terhadap variabel tersebut.
#include <stdio.h>
int main() {
int umur = 20;
float nilai = 87.5;
char grade = 'A';
printf("Umur: %d\n", umur);
printf("Nilai: %.2f\n", nilai);
printf("Grade: %c\n", grade);
return 0;
}Salah satu kelebihan tipe data statis adalah adanya pemeriksaan tipe data. Compiler dapat memeriksa apakah nilai yang diberikan sesuai dengan tipe variabelnya.
int jumlah = 10;
float harga = 25.5;int jumlah = "sepuluh";Setiap tipe data membutuhkan ruang memori yang berbeda. Besarnya memori bergantung pada bahasa pemrograman dan sistem komputer yang digunakan.
| Tipe Data | Contoh | Kebutuhan Memori Umum |
|---|---|---|
| Char | 'A' | 1 byte |
| Integer | 100 | Umumnya 4 byte |
| Float | 3.14 | Umumnya 4 byte |
| Double | 3.141592 | Umumnya 8 byte |
| Boolean | True | Bergantung implementasi |
Array statis memiliki jumlah elemen yang telah ditentukan sejak awal. Ukuran array tidak dapat bertambah atau berkurang selama program berjalan.
Array statis cocok digunakan ketika jumlah data sudah diketahui dan tidak sering berubah.
#include <stdio.h>
int main() {
int angka[5] = {10, 20, 30, 40, 50};
for (int i = 0; i < 5; i++) {
printf("%d\n", angka[i]);
}
return 0;
}| Aspek | Tipe Data Statis | Tipe Data Dinamis |
|---|---|---|
| Penentuan Tipe | Sebelum program berjalan | Saat program berjalan |
| Perubahan Tipe | Tidak mudah berubah | Dapat berubah sesuai nilai |
| Pemeriksaan | Banyak dilakukan oleh compiler | Banyak dilakukan saat runtime |
| Penggunaan Memori | Lebih mudah diperkirakan | Dapat berubah-ubah |
| Fleksibilitas | Lebih rendah | Lebih tinggi |
| Contoh Bahasa | C, C++, Java | Python, JavaScript, Ruby |
Menggunakan integer dan float untuk operasi aritmatika.
Menentukan tipe data setiap kolom dalam tabel.
Menyimpan skor, posisi, level, dan status pemain.
Menghemat memori pada perangkat dengan sumber daya terbatas.
Array-Based Sequence adalah struktur data berurutan yang menggunakan array sebagai media penyimpanan utama untuk mengelola sekumpulan elemen secara teratur.
Array-Based Sequence merupakan implementasi sequence menggunakan array yang menyimpan elemen-elemen secara berurutan di dalam memori.
Setiap elemen dapat diakses berdasarkan indeks. Karena elemen disimpan secara berurutan, pengaksesan berdasarkan posisi dapat dilakukan dengan cepat.
Struktur ini sesuai digunakan untuk data yang membutuhkan akses berdasarkan indeks, penelusuran berurutan, dan penyimpanan elemen dalam jumlah yang relatif teratur.
Setiap elemen sequence disimpan pada posisi tertentu. Posisi tersebut direpresentasikan menggunakan indeks.
| Indeks | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Elemen | 15 | 25 | 35 | 45 | 55 |
Dalam Python, konsep Array-Based Sequence dapat diimplementasikan menggunakan list. List menyediakan berbagai operasi untuk mengelola elemen secara berurutan.
Elemen dapat ditambahkan menggunakan
append(), dihapus menggunakan
pop(), dan diakses menggunakan indeks.
sequence = [10, 20, 30, 40]
# Mengakses elemen
print(sequence[0])
# Menambahkan elemen
sequence.append(50)
# Mengubah elemen
sequence[1] = 25
# Menghapus elemen terakhir
sequence.pop()
print(sequence)Penyisipan adalah proses menambahkan elemen baru ke posisi tertentu. Elemen setelah posisi tersebut dapat bergeser ke kanan.
angka = [10, 20, 40, 50]
angka.insert(2, 30)
print(angka)Hasil: [10, 20, 30, 40, 50]
Penghapusan adalah proses menghilangkan elemen dari posisi tertentu. Elemen setelahnya dapat bergeser ke kiri.
angka = [10, 20, 30, 40, 50]
del angka[2]
print(angka)Hasil: [10, 20, 40, 50]
Traversal adalah proses mengunjungi seluruh elemen sequence satu per satu. Traversal dapat dilakukan dengan menggunakan perulangan berdasarkan indeks atau langsung terhadap setiap nilai.
data = [5, 10, 15, 20]
for nilai in data:
print(nilai)data = [5, 10, 15, 20]
for indeks in range(len(data)):
print(data[indeks])Array-Based Sequence juga dapat dibuat sebagai class agar operasi seperti akses, penyisipan, penghapusan, dan pencarian dapat dikelola secara terstruktur.
class ArraySequence:
def __init__(self):
self.data = []
def add(self, value):
self.data.append(value)
def get(self, index):
return self.data[index]
def remove(self, index):
return self.data.pop(index)
sequence = ArraySequence()
sequence.add(10)
sequence.add(20)
sequence.add(30)
print(sequence.get(1))
sequence.remove(0)
print(sequence.data)| Operasi | Kompleksitas | Keterangan |
|---|---|---|
| Akses berdasarkan indeks | O(1) | Elemen dapat diambil langsung berdasarkan posisinya. |
| Pencarian linear | O(n) | Elemen diperiksa satu per satu. |
| Penyisipan di akhir | O(1) | Umumnya cepat jika kapasitas masih tersedia. |
| Penyisipan di tengah | O(n) | Elemen lain perlu digeser. |
| Penghapusan di akhir | O(1) | Elemen terakhir dapat dihapus langsung. |
| Penghapusan di tengah | O(n) | Elemen setelah posisi penghapusan bergeser. |
| Aspek | Array-Based Sequence | Linked List |
|---|---|---|
| Lokasi Memori | Berurutan | Tidak harus berurutan |
| Akses Indeks | Cepat | Harus menelusuri node |
| Penyisipan | Dapat membutuhkan pergeseran | Dapat dilakukan dengan mengubah tautan |
| Penghapusan | Dapat membutuhkan pergeseran | Dapat dilakukan dengan mengubah tautan |
| Penggunaan Memori | Lebih sederhana | Membutuhkan pointer tambahan |
| Cocok Untuk | Akses berdasarkan indeks | Data yang sering berubah |
Menyimpan nilai mahasiswa secara berurutan.
Menyimpan daftar barang dalam urutan tertentu.
Menyimpan jadwal kegiatan berdasarkan urutan waktu.
Menyimpan data dalam baris dan kolom.
Linked List adalah struktur data linear yang terdiri dari sekumpulan node. Setiap node menyimpan data dan alamat atau referensi menuju node berikutnya.
Linked List merupakan struktur data linear yang menyimpan elemen dalam node-node yang saling terhubung. Berbeda dengan array, elemen Linked List tidak harus berada pada lokasi memori yang berurutan.
Setiap node memiliki dua bagian utama, yaitu data dan pointer atau referensi. Pointer digunakan untuk menunjuk node berikutnya dalam rangkaian Linked List.
Linked List cocok digunakan ketika data sering mengalami penambahan dan penghapusan karena operasi tersebut tidak selalu membutuhkan pergeseran elemen seperti pada array.
Node merupakan bagian dasar dari Linked List. Setiap node memiliki data dan referensi yang menghubungkannya dengan node berikutnya.
Menyimpan nilai atau informasi.
Menunjuk node berikutnya.
Terhubung dalam rangkaian data.
None atau NULL yang menandakan
akhir dari Linked List.
Singly Linked List adalah Linked List yang setiap node-nya hanya memiliki satu referensi, yaitu referensi menuju node berikutnya.
Penelusuran Singly Linked List dilakukan dari node pertama menuju node terakhir secara satu arah.
Struktur ini sederhana dan menggunakan memori tambahan yang lebih sedikit dibandingkan Doubly Linked List.
class Node:
def __init__(self, data):
self.data = data
self.next = None
node1 = Node(10)
node2 = Node(20)
node3 = Node(30)
node1.next = node2
node2.next = node3
current = node1
while current is not None:
print(current.data)
current = current.nextDoubly Linked List adalah Linked List yang setiap node-nya memiliki dua referensi, yaitu referensi ke node sebelumnya dan referensi ke node berikutnya.
Dengan dua arah hubungan tersebut, penelusuran dapat dilakukan dari depan ke belakang maupun dari belakang ke depan.
Kekurangannya adalah setiap node membutuhkan memori tambahan untuk menyimpan dua referensi.
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
node1 = Node(10)
node2 = Node(20)
node1.next = node2
node2.prev = node1
print(node1.data)
print(node1.next.data)
print(node2.prev.data)
Circular Linked List adalah Linked List yang node terakhirnya
menunjuk kembali ke node pertama. Dengan demikian, tidak
terdapat referensi None pada akhir rangkaian.
Struktur ini dapat digunakan untuk sistem yang membutuhkan perulangan data secara terus-menerus, seperti penjadwalan proses dan sistem giliran.
class Node:
def __init__(self, data):
self.data = data
self.next = None
node1 = Node(10)
node2 = Node(20)
node3 = Node(30)
node1.next = node2
node2.next = node3
node3.next = node1
current = node1
for i in range(6):
print(current.data)
current = current.nextNode baru ditempatkan sebelum node pertama. Referensi node baru diarahkan ke head sebelumnya.
def insert_at_beginning(head, data):
new_node = Node(data)
new_node.next = head
return new_node
head = Node(20)
head.next = Node(30)
head = insert_at_beginning(head, 10)Node baru ditambahkan setelah node terakhir. Untuk menemukan node terakhir, Linked List perlu ditelusuri terlebih dahulu.
def insert_at_end(head, data):
new_node = Node(data)
if head is None:
return new_node
current = head
while current.next is not None:
current = current.next
current.next = new_node
return headPenghapusan node dilakukan dengan mengubah referensi node sebelumnya agar menunjuk ke node setelah node yang dihapus.
Jika node pertama dihapus, maka head harus dipindahkan ke node berikutnya.
def delete_node(head, data):
if head is None:
return None
if head.data == data:
return head.next
current = head
while current.next is not None:
if current.next.data == data:
current.next = current.next.next
break
current = current.next
return headclass Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insert_at_beginning(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def insert_at_end(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
current = self.head
while current.next is not None:
current = current.next
current.next = new_node
def delete(self, data):
if self.head is None:
return
if self.head.data == data:
self.head = self.head.next
return
current = self.head
while current.next is not None:
if current.next.data == data:
current.next = current.next.next
return
current = current.next
def display(self):
current = self.head
while current is not None:
print(current.data, end=" -> ")
current = current.next
print("None")
linked_list = LinkedList()
linked_list.insert_at_end(10)
linked_list.insert_at_end(20)
linked_list.insert_at_beginning(5)
linked_list.display()
linked_list.delete(10)
linked_list.display()| Operasi | Singly Linked List | Keterangan |
|---|---|---|
| Akses berdasarkan posisi | O(n) | Node harus ditelusuri dari head. |
| Pencarian | O(n) | Node diperiksa satu per satu. |
| Penyisipan di awal | O(1) | Head langsung dipindahkan ke node baru. |
| Penyisipan di akhir | O(n) | Harus menemukan node terakhir. |
| Penghapusan di awal | O(1) | Head dipindahkan ke node berikutnya. |
| Penghapusan berdasarkan nilai | O(n) | Node harus dicari terlebih dahulu. |
| Aspek | Linked List | Array |
|---|---|---|
| Lokasi Memori | Tidak harus berurutan | Berurutan |
| Ukuran | Dapat berubah | Umumnya ditentukan sejak awal |
| Akses Indeks | O(n) | O(1) |
| Penyisipan | Fleksibel | Dapat membutuhkan pergeseran |
| Penghapusan | Fleksibel | Dapat membutuhkan pergeseran |
| Memori Tambahan | Membutuhkan pointer | Tidak membutuhkan pointer tambahan |
Menyimpan riwayat perubahan pada aplikasi.
Mengatur daftar lagu yang dapat berpindah urutan.
Mengelola proses atau pekerjaan yang menunggu giliran.
Menyimpan hubungan antarvertex dalam graph.
None atau NULL.
Double Linked List atau Doubly Linked List adalah struktur data linear yang setiap node-nya memiliki referensi ke node sebelumnya dan node berikutnya.
Double Linked List adalah pengembangan dari Singly Linked List. Setiap node memiliki tiga bagian utama, yaitu data, pointer ke node sebelumnya, dan pointer ke node berikutnya.
Dengan adanya dua arah hubungan, penelusuran data dapat dilakukan dari awal ke akhir maupun dari akhir ke awal.
Double Linked List cocok digunakan pada aplikasi yang membutuhkan navigasi maju dan mundur, seperti playlist, riwayat halaman web, dan fitur undo serta redo.
Setiap node dalam Double Linked List memiliki tiga komponen utama.
Menunjuk node sebelumnya.
Menyimpan nilai node.
Menunjuk node berikutnya.
previous pada node pertama bernilai
None, sedangkan pointer next
pada node terakhir bernilai None.
Node Double Linked List dapat dibuat menggunakan class.
Setiap node memiliki atribut
data, previous, dan
next.
class Node:
def __init__(self, data):
self.data = data
self.previous = None
self.next = None
node1 = Node(10)
node2 = Node(20)
node1.next = node2
node2.previous = node1
print(node1.data)
print(node2.previous.data)
Double Linked List dapat ditelusuri menggunakan pointer
next untuk bergerak maju dan pointer
previous untuk bergerak mundur.
current = head
while current is not None:
print(current.data)
current = current.nextcurrent = tail
while current is not None:
print(current.data)
current = current.previous
Node baru ditempatkan sebelum head. Pointer
previous dan next harus
diperbarui agar hubungan tetap benar.
def insert_at_beginning(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
return
new_node.next = self.head
self.head.previous = new_node
self.head = new_node
Node baru ditambahkan setelah tail. Pointer
next pada tail lama dan pointer
previous pada node baru diperbarui.
def insert_at_end(self, data):
new_node = Node(data)
if self.tail is None:
self.head = new_node
self.tail = new_node
return
new_node.previous = self.tail
self.tail.next = new_node
self.tail = new_nodePenghapusan node dilakukan dengan menghubungkan node sebelumnya dengan node berikutnya.
Jika node yang dihapus adalah head atau tail, posisi head atau tail harus diperbarui.
def delete(self, data):
current = self.head
while current is not None:
if current.data == data:
if current.previous is not None:
current.previous.next = current.next
else:
self.head = current.next
if current.next is not None:
current.next.previous = current.previous
else:
self.tail = current.previous
return
current = current.next
Node baru dapat disisipkan setelah node tertentu dengan
mengatur empat hubungan pointer, yaitu pointer
previous dan next dari node baru
serta node di sekitarnya.
def insert_after(self, target, data):
current = self.head
while current is not None:
if current.data == target:
new_node = Node(data)
new_node.previous = current
new_node.next = current.next
if current.next is not None:
current.next.previous = new_node
else:
self.tail = new_node
current.next = new_node
return
current = current.nextclass Node:
def __init__(self, data):
self.data = data
self.previous = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def insert_at_beginning(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
return
new_node.next = self.head
self.head.previous = new_node
self.head = new_node
def insert_at_end(self, data):
new_node = Node(data)
if self.tail is None:
self.head = new_node
self.tail = new_node
return
new_node.previous = self.tail
self.tail.next = new_node
self.tail = new_node
def delete(self, data):
current = self.head
while current is not None:
if current.data == data:
if current.previous is not None:
current.previous.next = current.next
else:
self.head = current.next
if current.next is not None:
current.next.previous = current.previous
else:
self.tail = current.previous
return
current = current.next
def display_forward(self):
current = self.head
while current is not None:
print(current.data, end=" <-> ")
current = current.next
print("None")
def display_backward(self):
current = self.tail
while current is not None:
print(current.data, end=" <-> ")
current = current.previous
print("None")
linked_list = DoublyLinkedList()
linked_list.insert_at_end(10)
linked_list.insert_at_end(20)
linked_list.insert_at_end(30)
linked_list.insert_at_beginning(5)
print("Traversal maju:")
linked_list.display_forward()
print("Traversal mundur:")
linked_list.display_backward()
linked_list.delete(20)
print("Setelah menghapus 20:")
linked_list.display_forward()| Operasi | Kompleksitas | Keterangan |
|---|---|---|
| Akses berdasarkan posisi | O(n) | Node harus ditelusuri dari head atau tail. |
| Pencarian | O(n) | Node diperiksa satu per satu. |
| Penyisipan di awal | O(1) | Head langsung diperbarui. |
| Penyisipan di akhir | O(1) | Tail tersedia sehingga tidak perlu traversal. |
| Penghapusan node yang diketahui | O(1) | Pointer sekitar node langsung diperbarui. |
| Penghapusan berdasarkan nilai | O(n) | Node harus dicari terlebih dahulu. |
| Aspek | Singly Linked List | Double Linked List |
|---|---|---|
| Jumlah Pointer | Satu pointer | Dua pointer |
| Arah Traversal | Satu arah | Dua arah |
| Penggunaan Memori | Lebih kecil | Lebih besar |
| Penghapusan Node | Relatif lebih kompleks | Lebih mudah |
| Implementasi | Lebih sederhana | Lebih kompleks |
| Penerapan | Stack dan queue sederhana | Undo, redo, dan navigasi maju-mundur |
Bergerak maju dan mundur pada riwayat perubahan.
Berpindah ke halaman sebelumnya atau berikutnya.
Berpindah ke lagu berikutnya atau lagu sebelumnya.
Menampilkan gambar berikutnya dan sebelumnya.
Circular Linked List adalah struktur data linked list yang node terakhirnya menunjuk kembali ke node pertama sehingga membentuk sebuah siklus atau lingkaran.
Circular Linked List merupakan pengembangan dari Singly
Linked List atau Doubly Linked List. Perbedaannya,
node terakhir tidak menunjuk ke None atau
NULL, tetapi menunjuk kembali ke node pertama.
Karena membentuk siklus, proses penelusuran dapat dilakukan secara berulang dari node pertama hingga kembali ke node pertama.
Struktur ini sesuai digunakan untuk sistem yang membutuhkan proses bergiliran atau perulangan data secara terus-menerus.
None
Pada ilustrasi berikut, node terakhir kembali menunjuk ke node pertama.
Data: 10
Data: 20
Data: 30
Node 3 kembali menunjuk ke Node 1.
Node pada Circular Linked List memiliki data dan pointer
next. Pointer tersebut digunakan untuk
menunjuk node berikutnya dalam lingkaran.
Pada tahap awal, node baru dapat menunjuk dirinya sendiri sampai node lain ditambahkan.
class Node:
def __init__(self, data):
self.data = data
self.next = None
node = Node(10)
node.next = node
print(node.data)
print(node.next.data)
Setiap node hanya memiliki pointer
next. Node terakhir menunjuk
kembali ke node pertama.
Setiap node memiliki pointer
previous dan next.
Node pertama dan terakhir saling terhubung
dari dua arah.
Traversal harus berhenti ketika pointer kembali
ke node awal. Jika menggunakan kondisi
while current is not None, traversal
tidak akan berhenti.
def display(self):
if self.head is None:
return
current = self.head
while True:
print(current.data)
current = current.next
if current == self.head:
breakKarena berbentuk lingkaran, traversal dapat dilakukan beberapa kali menggunakan batas jumlah perulangan.
current = head
for i in range(8):
print(current.data)
current = current.nextdef insert_at_beginning(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
new_node.next = new_node
return
current = self.head
while current.next != self.head:
current = current.next
new_node.next = self.head
current.next = new_node
self.head = new_nodedef insert_at_end(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
new_node.next = new_node
return
current = self.head
while current.next != self.head:
current = current.next
current.next = new_node
new_node.next = self.headSaat menghapus node, hubungan antara node sebelumnya dan node berikutnya harus diperbarui. Kondisi khusus perlu diperhatikan ketika node yang dihapus adalah head.
def delete(self, data):
if self.head is None:
return
current = self.head
previous = None
while True:
if current.data == data:
if previous is None:
last = self.head
while last.next != self.head:
last = last.next
if self.head.next == self.head:
self.head = None
else:
self.head = self.head.next
last.next = self.head
else:
previous.next = current.next
return
previous = current
current = current.next
if current == self.head:
breakclass Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def insert_at_beginning(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
new_node.next = new_node
return
last = self.head
while last.next != self.head:
last = last.next
new_node.next = self.head
last.next = new_node
self.head = new_node
def insert_at_end(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
new_node.next = new_node
return
last = self.head
while last.next != self.head:
last = last.next
last.next = new_node
new_node.next = self.head
def delete(self, data):
if self.head is None:
return
current = self.head
previous = None
while True:
if current.data == data:
if previous is None:
last = self.head
while last.next != self.head:
last = last.next
if self.head.next == self.head:
self.head = None
else:
self.head = self.head.next
last.next = self.head
else:
previous.next = current.next
return
previous = current
current = current.next
if current == self.head:
break
def display(self):
if self.head is None:
print("Circular Linked List kosong")
return
current = self.head
while True:
print(current.data, end=" -> ")
current = current.next
if current == self.head:
break
print("(kembali ke head)")
circular_list = CircularLinkedList()
circular_list.insert_at_end(10)
circular_list.insert_at_end(20)
circular_list.insert_at_end(30)
circular_list.insert_at_beginning(5)
circular_list.display()
circular_list.delete(20)
circular_list.display()| Operasi | Kompleksitas | Keterangan |
|---|---|---|
| Traversal | O(n) | Setiap node dikunjungi satu kali. |
| Pencarian | O(n) | Node diperiksa sampai kembali ke head. |
| Penyisipan di awal | O(n) | O(n) jika hanya menggunakan pointer head dan harus mencari node terakhir. |
| Penyisipan di akhir | O(n) | Node terakhir harus ditemukan terlebih dahulu. |
| Penghapusan berdasarkan nilai | O(n) | Node perlu dicari sebelum dihapus. |
| Akses berdasarkan indeks | O(n) | Tidak tersedia akses langsung seperti array. |
None.
None.
| Aspek | Singly Linked List | Circular Linked List |
|---|---|---|
| Node Terakhir | Menunjuk ke None | Menunjuk ke head |
| Bentuk Struktur | Linear | Melingkar |
| Kondisi Berhenti | current menjadi None | current kembali ke head |
| Risiko Infinite Loop | Lebih kecil | Lebih besar |
| Penerapan | Data linear biasa | Data yang diproses berulang |
Membagi giliran proses secara berulang.
Memutar lagu kembali ke awal setelah lagu terakhir.
Mengatur giliran pemain secara berulang.
Mengatur proses dalam sistem berbasis antrian melingkar.
Array Structure adalah struktur data yang menyimpan elemen secara berurutan pada lokasi memori yang berdekatan.
Array Structure digunakan untuk menyimpan sekumpulan data dengan tipe yang sama atau memiliki karakteristik serupa dalam satu struktur data.
Setiap elemen array memiliki indeks yang digunakan untuk mengakses data. Pada sebagian besar bahasa pemrograman, indeks pertama dimulai dari angka nol.
Array memberikan akses langsung terhadap elemen sehingga sesuai digunakan untuk data yang membutuhkan akses cepat berdasarkan posisi.
Array dapat digambarkan sebagai kumpulan kotak yang tersusun berurutan. Setiap kotak menyimpan satu elemen.
| Indeks | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Nilai | 12 | 24 | 36 | 48 | 60 |
data = [12, 24, 36, 48, 60]
print(data[0])
print(data[3])data = [12, 24, 36, 48, 60]
data[2] = 40
print(data)| Operasi | Contoh | Kompleksitas |
|---|---|---|
| Akses | Mengambil data berdasarkan indeks | O(1) |
| Pencarian | Mencari nilai tertentu | O(n) |
| Penyisipan | Menambahkan elemen baru | O(n) |
| Penghapusan | Menghapus elemen tertentu | O(n) |
| Traversal | Mengunjungi seluruh elemen | O(n) |
Array Structure sangat sesuai digunakan ketika data memiliki urutan yang jelas dan akses berdasarkan indeks sering dilakukan. Namun, untuk data yang sering mengalami penyisipan dan penghapusan, linked structure dapat menjadi pilihan yang lebih fleksibel.
List dan pointer merupakan konsep penting dalam struktur data untuk menyimpan, menghubungkan, dan mengelola sekumpulan data secara fleksibel di dalam memori.
List adalah struktur data yang digunakan untuk menyimpan kumpulan elemen. Elemen-elemen tersebut dapat disimpan secara berurutan dan dikelola menggunakan operasi seperti penambahan, penghapusan, pencarian, dan penelusuran.
Pointer adalah variabel yang menyimpan alamat memori dari data atau variabel lain. Pointer banyak digunakan untuk menghubungkan node pada Linked List.
Kombinasi list dan pointer memungkinkan program membuat struktur data dinamis yang ukurannya dapat bertambah atau berkurang selama program berjalan.
List yang menyimpan elemen secara berurutan pada lokasi memori yang berdekatan.
List yang elemennya disimpan dalam node dan dihubungkan menggunakan pointer.
List yang node terakhirnya menunjuk kembali ke node pertama.
Pointer adalah variabel khusus yang menyimpan alamat memori dari variabel lain. Dengan pointer, program dapat mengakses atau mengubah data melalui alamatnya.
Dalam bahasa C, operator & digunakan untuk
mengambil alamat memori, sedangkan operator *
digunakan untuk mengakses nilai yang berada pada alamat
tersebut.
#include <stdio.h>
int main() {
int angka = 10;
int *pointer;
pointer = &angka;
printf("Nilai angka: %d\n", angka);
printf("Alamat angka: %p\n", (void*) pointer);
printf("Nilai melalui pointer: %d\n", *pointer);
return 0;
}| Operator | Nama | Fungsi |
|---|---|---|
| & | Address-of | Mengambil alamat memori suatu variabel. |
| * | Dereference | Mengakses nilai pada alamat yang ditunjuk pointer. |
| -> | Pointer Member | Mengakses field struct melalui pointer. |
| NULL | Null Pointer | Menunjukkan pointer yang tidak menunjuk ke objek tertentu. |
Pada Linked List, pointer digunakan untuk menghubungkan satu node dengan node lainnya. Setiap node memiliki data dan pointer yang menunjuk node berikutnya.
Node terakhir biasanya menunjuk ke NULL pada
Singly Linked List atau kembali ke head pada Circular
Linked List.
class Node:
def __init__(self, data):
self.data = data
self.next = None
node1 = Node(10)
node2 = Node(20)
node1.next = node2
print(node1.data)
print(node1.next.data)Node dapat berada pada alamat memori yang berbeda. Pointer menghubungkan alamat node tersebut sehingga terbentuk sebuah list.
| Alamat Node | Data | Pointer Next |
|---|---|---|
| 1000 | 10 | 2050 |
| 2050 | 20 | 3075 |
| 3075 | 30 | NULL |
Data baru dapat ditambahkan di awal, akhir, atau posisi tertentu pada list.
data = [10, 20, 30]
data.append(40)
print(data)Data dapat dihapus berdasarkan nilai atau posisi tertentu.
data = [10, 20, 30, 40]
data.remove(20)
print(data)Traversal adalah proses mengunjungi setiap elemen list secara berurutan. Pada linked list, traversal dilakukan dengan mengikuti pointer dari node pertama sampai node terakhir.
current = head
while current is not None:
print(current.data)
current = current.nextPointer harus digunakan secara hati-hati. Kesalahan penggunaan pointer dapat menyebabkan program mengalami crash, memory leak, atau mengakses alamat memori yang tidak valid.
Pastikan pointer memiliki nilai yang valid sebelum digunakan.
Periksa pointer sebelum melakukan dereference.
Lepaskan memori yang tidak lagi digunakan.
| Aspek | Array List | Linked List |
|---|---|---|
| Penyimpanan | Memori berurutan | Memori tidak harus berurutan |
| Akses Indeks | Cepat | Harus traversal |
| Penyisipan | Dapat membutuhkan pergeseran | Mengubah pointer |
| Penghapusan | Dapat membutuhkan pergeseran | Mengubah pointer |
| Memori Tambahan | Tidak membutuhkan pointer | Membutuhkan pointer |
| Fleksibilitas | Sedang | Tinggi |
Menyimpan data dengan prinsip LIFO.
Menyimpan data dengan prinsip FIFO.
Menghubungkan vertex dengan edge.
Membentuk struktur data bertingkat.
Stack adalah struktur data linear yang menggunakan prinsip LIFO, yaitu Last In First Out. Elemen yang terakhir masuk akan menjadi elemen pertama yang keluar.
Stack adalah struktur data yang proses penambahan dan penghapusannya dilakukan hanya pada satu ujung yang disebut top.
Prinsip kerja Stack dapat dianalogikan seperti tumpukan piring. Piring yang terakhir diletakkan di atas akan menjadi piring pertama yang diambil.
Stack dapat diimplementasikan menggunakan array, list, maupun Linked List.
LIFO adalah singkatan dari Last In First Out. Data yang terakhir dimasukkan akan dikeluarkan terlebih dahulu.
Top
Bottom
Dalam Python, Stack dapat dibuat menggunakan list.
Method append() digunakan untuk push,
sedangkan pop() digunakan untuk pop.
stack = []
# Push
stack.append(10)
stack.append(20)
stack.append(30)
print("Stack:", stack)
# Peek
print("Elemen teratas:", stack[-1])
# Pop
elemen = stack.pop()
print("Elemen keluar:", elemen)
print("Stack setelah pop:", stack)class Stack:
def __init__(self):
self.items = []
def push(self, data):
self.items.append(data)
def pop(self):
if self.is_empty():
return "Stack kosong"
return self.items.pop()
def peek(self):
if self.is_empty():
return "Stack kosong"
return self.items[-1]
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
print("Top:", stack.peek())
print("Pop:", stack.pop())
print("Size:", stack.size())Stack juga dapat dibuat menggunakan Linked List. Node paling awal digunakan sebagai top sehingga operasi push dan pop dapat dilakukan dengan cepat.
Implementasi ini bersifat dinamis karena ukuran Stack tidak ditentukan secara tetap sejak awal.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.top = None
def push(self, data):
new_node = Node(data)
new_node.next = self.top
self.top = new_node
def pop(self):
if self.top is None:
return "Stack kosong"
data = self.top.data
self.top = self.top.next
return data
def peek(self):
if self.top is None:
return "Stack kosong"
return self.top.dataStack Overflow terjadi ketika program mencoba menambahkan elemen ke Stack yang sudah penuh.
Stack Underflow terjadi ketika program mencoba menghapus elemen dari Stack yang kosong.
| Operasi | Kompleksitas | Keterangan |
|---|---|---|
| Push | O(1) | Menambahkan data pada bagian top. |
| Pop | O(1) | Menghapus data pada bagian top. |
| Peek | O(1) | Melihat data teratas. |
| isEmpty | O(1) | Memeriksa kondisi Stack. |
| Search | O(n) | Mencari data membutuhkan pemeriksaan elemen. |
Menyimpan riwayat perubahan pada aplikasi.
Memeriksa tanda kurung dan struktur ekspresi.
Mengelola halaman yang dikunjungi sebelumnya.
Mengubah infix menjadi postfix atau prefix.
Queue adalah struktur data linear yang menggunakan prinsip FIFO, yaitu First In First Out. Elemen yang pertama masuk akan menjadi elemen pertama yang keluar.
Queue adalah struktur data yang proses penambahan elemen dilakukan dari bagian belakang, sedangkan penghapusan elemen dilakukan dari bagian depan.
Prinsip Queue dapat dianalogikan seperti antrean di loket. Orang yang datang terlebih dahulu akan dilayani terlebih dahulu.
Queue dapat diimplementasikan menggunakan array, list, Linked List, maupun Circular Queue.
FIFO adalah singkatan dari First In First Out. Data yang pertama masuk akan dikeluarkan terlebih dahulu.
Elemen 10
Elemen 30
Queue dapat dibuat menggunakan modul
collections. Method append()
digunakan untuk enqueue, sedangkan
popleft() digunakan untuk dequeue.
from collections import deque
queue = deque()
# Enqueue
queue.append(10)
queue.append(20)
queue.append(30)
print("Queue:", queue)
# Melihat front
print("Front:", queue[0])
# Dequeue
elemen = queue.popleft()
print("Elemen keluar:", elemen)
print("Queue setelah dequeue:", queue)class Queue:
def __init__(self):
self.items = []
def enqueue(self, data):
self.items.append(data)
def dequeue(self):
if self.is_empty():
return "Queue kosong"
return self.items.pop(0)
def front(self):
if self.is_empty():
return "Queue kosong"
return self.items[0]
def rear(self):
if self.is_empty():
return "Queue kosong"
return self.items[-1]
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
queue = Queue()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
print("Front:", queue.front())
print("Rear:", queue.rear())
print("Dequeue:", queue.dequeue())
print("Size:", queue.size())
Queue dapat dibuat menggunakan Linked List dengan dua
pointer utama, yaitu front dan
rear.
Pointer front digunakan untuk menghapus data,
sedangkan pointer rear digunakan untuk
menambahkan data.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.front = None
self.rear = None
def enqueue(self, data):
new_node = Node(data)
if self.rear is None:
self.front = new_node
self.rear = new_node
return
self.rear.next = new_node
self.rear = new_node
def dequeue(self):
if self.front is None:
return "Queue kosong"
data = self.front.data
self.front = self.front.next
if self.front is None:
self.rear = None
return dataCircular Queue adalah Queue yang posisi rear dapat kembali ke posisi awal array ketika terdapat ruang kosong.
Circular Queue membantu menggunakan ruang array secara lebih efisien dibandingkan Queue linear biasa.
class CircularQueue:
def __init__(self, capacity):
self.queue = [None] * capacity
self.capacity = capacity
self.front = 0
self.rear = 0
self.size = 0
def enqueue(self, data):
if self.size == self.capacity:
return "Queue penuh"
self.queue[self.rear] = data
self.rear = (self.rear + 1) % self.capacity
self.size += 1
def dequeue(self):
if self.size == 0:
return "Queue kosong"
data = self.queue[self.front]
self.queue[self.front] = None
self.front = (self.front + 1) % self.capacity
self.size -= 1
return dataQueue Overflow terjadi ketika program mencoba menambahkan elemen ke Queue yang sudah penuh.
Queue Underflow terjadi ketika program mencoba menghapus elemen dari Queue yang kosong.
| Operasi | Kompleksitas | Keterangan |
|---|---|---|
| Enqueue | O(1) | Menambahkan elemen pada bagian rear. |
| Dequeue | O(1) | Menghapus elemen dari bagian front. |
| Front | O(1) | Melihat elemen paling depan. |
| Rear | O(1) | Melihat elemen paling belakang. |
| Searching | O(n) | Mencari data membutuhkan pemeriksaan elemen. |
| Aspek | Queue | Stack |
|---|---|---|
| Prinsip | FIFO | LIFO |
| Penambahan | Dari rear | Dari top |
| Penghapusan | Dari front | Dari top |
| Operasi Utama | Enqueue dan dequeue | Push dan pop |
| Contoh | Antrean loket | Tumpukan piring |
Mengatur dokumen yang akan dicetak.
Mengatur proses yang menunggu giliran eksekusi.
Menyimpan paket data yang menunggu diproses.
Mengelola pelanggan berdasarkan urutan kedatangan.
Deque memungkinkan penambahan dan penghapusan elemen dari kedua ujung.
Deque memungkinkan penambahan dan penghapusan elemen dari kedua ujung.
def proses(data):
# Implementasikan konsep Deque
return data
contoh = [3, 1, 2]
print(proses(contoh))Implementasi struktur data Stack dan Queue menggunakan Python dan Linked List.
Stack dan Queue merupakan struktur data linear yang banyak digunakan dalam pemrograman. Stack menggunakan prinsip LIFO, sedangkan Queue menggunakan prinsip FIFO.
Pada implementasi ini, kedua struktur data dibuat menggunakan Linked List agar ukuran penyimpanan dapat bertambah dan berkurang secara dinamis.
| Aspek | Stack | Queue |
|---|---|---|
| Prinsip | LIFO | FIFO |
| Penambahan Data | Push melalui top | Enqueue melalui rear |
| Penghapusan Data | Pop melalui top | Dequeue melalui front |
| Pointer | Top | Front dan rear |
| Contoh | Tumpukan piring | Antrean loket |
Stack dan Queue menggunakan class Node yang
sama. Setiap node menyimpan data dan referensi ke node
berikutnya.
class Node:
def __init__(self, data):
self.data = data
self.next = None
Stack menggunakan pointer top. Node baru
ditambahkan pada posisi top dan node pada posisi top
dihapus ketika operasi pop dilakukan.
class Stack:
def __init__(self):
self.top = None
self.count = 0
def is_empty(self):
return self.top is None
def push(self, data):
new_node = Node(data)
new_node.next = self.top
self.top = new_node
self.count += 1
def pop(self):
if self.is_empty():
return None
data = self.top.data
self.top = self.top.next
self.count -= 1
return data
def peek(self):
if self.is_empty():
return None
return self.top.data
def size(self):
return self.count
def display(self):
current = self.top
result = []
while current is not None:
result.append(current.data)
current = current.next
print("Stack:", result)push, pop,
peek, dan is_empty memiliki
kompleksitas waktu $O(1)$.
Queue menggunakan dua pointer, yaitu front
dan rear. Data ditambahkan melalui
rear dan dihapus melalui front.
class Queue:
def __init__(self):
self.front = None
self.rear = None
self.count = 0
def is_empty(self):
return self.front is None
def enqueue(self, data):
new_node = Node(data)
if self.rear is None:
self.front = new_node
self.rear = new_node
else:
self.rear.next = new_node
self.rear = new_node
self.count += 1
def dequeue(self):
if self.is_empty():
return None
data = self.front.data
self.front = self.front.next
self.count -= 1
if self.front is None:
self.rear = None
return data
def get_front(self):
if self.is_empty():
return None
return self.front.data
def get_rear(self):
if self.is_empty():
return None
return self.rear.data
def size(self):
return self.count
def display(self):
current = self.front
result = []
while current is not None:
result.append(current.data)
current = current.next
print("Queue:", result)enqueue, dequeue,
get_front, get_rear, dan
is_empty memiliki kompleksitas waktu $O(1)$.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.top = None
self.count = 0
def push(self, data):
new_node = Node(data)
new_node.next = self.top
self.top = new_node
self.count += 1
def pop(self):
if self.top is None:
return None
data = self.top.data
self.top = self.top.next
self.count -= 1
return data
def peek(self):
if self.top is None:
return None
return self.top.data
def display(self):
current = self.top
result = []
while current is not None:
result.append(current.data)
current = current.next
print("Stack:", result)
class Queue:
def __init__(self):
self.front = None
self.rear = None
self.count = 0
def enqueue(self, data):
new_node = Node(data)
if self.rear is None:
self.front = new_node
self.rear = new_node
else:
self.rear.next = new_node
self.rear = new_node
self.count += 1
def dequeue(self):
if self.front is None:
return None
data = self.front.data
self.front = self.front.next
self.count -= 1
if self.front is None:
self.rear = None
return data
def get_front(self):
if self.front is None:
return None
return self.front.data
def get_rear(self):
if self.rear is None:
return None
return self.rear.data
def display(self):
current = self.front
result = []
while current is not None:
result.append(current.data)
current = current.next
print("Queue:", result)
# Penggunaan Stack
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
stack.display()
print("Stack peek:", stack.peek())
print("Stack pop:", stack.pop())
stack.display()
# Penggunaan Queue
queue = Queue()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
queue.display()
print("Queue front:", queue.get_front())
print("Queue rear:", queue.get_rear())
print("Queue dequeue:", queue.dequeue())
queue.display()| Operasi | Stack | Queue |
|---|---|---|
| Menambahkan Data | Push: O(1) | Enqueue: O(1) |
| Menghapus Data | Pop: O(1) | Dequeue: O(1) |
| Melihat Elemen Utama | Peek: O(1) | Front: O(1) |
| Pencarian | O(n) | O(n) |
| Ukuran | O(1) dengan counter | O(1) dengan counter |
Stack cocok digunakan ketika data terakhir yang diproses harus menjadi data pertama yang keluar.
Queue cocok digunakan ketika data harus diproses berdasarkan urutan kedatangannya.
Stack menggunakan prinsip LIFO dengan operasi utama
push dan pop, sedangkan Queue
menggunakan prinsip FIFO dengan operasi utama
enqueue dan dequeue. Keduanya dapat
diimplementasikan dengan Linked List untuk memperoleh struktur
data yang fleksibel dan dinamis.
Algoritma adalah langkah-langkah sistematis untuk menyelesaikan masalah, sedangkan kompleksitas digunakan untuk mengukur efisiensi algoritma berdasarkan waktu dan penggunaan memori.
Algoritma adalah urutan langkah-langkah logis, terstruktur, dan terbatas yang digunakan untuk menyelesaikan suatu masalah.
Algoritma menerima input, memproses input tersebut, lalu menghasilkan output sesuai tujuan yang diharapkan.
Algoritma yang baik harus mudah dipahami, memiliki langkah yang jelas, menghasilkan solusi yang benar, dan dapat dijalankan secara efisien.
Data yang diberikan kepada algoritma.
Langkah pengolahan data.
Hasil yang diperoleh dari proses.
Kondisi yang menandakan algoritma selesai.
Berikut contoh algoritma untuk menghitung luas persegi panjang.
panjang = 10
lebar = 5
luas = panjang * lebar
print("Luas persegi panjang:", luas)Kompleksitas algoritma adalah ukuran yang digunakan untuk mengetahui seberapa banyak sumber daya yang dibutuhkan oleh suatu algoritma.
Sumber daya yang biasanya dianalisis adalah waktu eksekusi dan penggunaan memori.
Analisis kompleksitas membantu programmer memilih algoritma yang paling efisien untuk menyelesaikan masalah tertentu.
Mengukur waktu yang diperlukan algoritma.
Mengukur jumlah memori yang digunakan algoritma.
Notasi Big O digunakan untuk menggambarkan pertumbuhan waktu atau penggunaan memori algoritma terhadap ukuran input $n$.
Big O tidak berfokus pada waktu aktual dalam satuan detik, tetapi pada pola pertumbuhan algoritma ketika ukuran data semakin besar.
| Notasi | Nama | Contoh | Keterangan |
|---|---|---|---|
| $O(1)$ | Konstan | Akses indeks array | Waktu tidak bergantung pada ukuran input. |
| $O(\log n)$ | Logaritmik | Binary Search | Input berkurang secara bertahap. |
| $O(n)$ | Linear | Linear Search | Waktu bertambah sebanding dengan input. |
| $O(n \log n)$ | Linear-logaritmik | Merge Sort | Umum digunakan pada algoritma pengurutan efisien. |
| $O(n^2)$ | Kuadratik | Bubble Sort | Sering terjadi pada dua perulangan bersarang. |
| $O(2^n)$ | Eksponensial | Recursive Fibonacci | Pertumbuhan waktu sangat cepat. |
def get_first(data):
return data[0]
data = [10, 20, 30, 40]
print(get_first(data))def display_all(data):
for item in data:
print(item)
data = [10, 20, 30, 40]
display_all(data)Kompleksitas kuadratik biasanya muncul ketika terdapat dua perulangan yang saling bersarang.
Jika jumlah data bertambah, waktu proses akan meningkat secara kuadratik.
def print_pairs(data):
for i in data:
for j in data:
print(i, j)
data = [1, 2, 3]
print_pairs(data)Linear Search memeriksa elemen satu per satu dari awal hingga data ditemukan.
def linear_search(data, target):
for index in range(len(data)):
if data[index] == target:
return index
return -1Kompleksitas waktu: $O(n)$.
Binary Search membagi ruang pencarian menjadi dua bagian. Algoritma ini membutuhkan data yang sudah terurut.
def binary_search(data, target):
left = 0
right = len(data) - 1
while left <= right:
middle = (left + right) // 2
if data[middle] == target:
return middle
elif data[middle] < target:
left = middle + 1
else:
right = middle - 1
return -1Kompleksitas waktu: $O(\log n)$.
| Algoritma | Best Case | Average Case | Worst Case |
|---|---|---|---|
| Bubble Sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ |
| Selection Sort | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ |
| Insertion Sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ |
| Merge Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ |
| Quick Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n^2)$ |
Kondisi ketika algoritma memperoleh hasil paling cepat atau paling menguntungkan.
Kondisi rata-rata yang biasanya terjadi pada input umum.
Kondisi ketika algoritma membutuhkan waktu atau memori paling besar.
Kompleksitas ruang mengukur jumlah memori tambahan yang dibutuhkan algoritma saat dijalankan.
Algoritma menggunakan jumlah memori tambahan yang konstan.
Memori tambahan bertambah sesuai ukuran input.
Algoritma merupakan langkah-langkah untuk menyelesaikan masalah, sedangkan kompleksitas digunakan untuk menilai efisiensi algoritma. Notasi Big O membantu menggambarkan pertumbuhan waktu dan memori terhadap ukuran input. Semakin kecil pertumbuhan kompleksitasnya, semakin efisien algoritma tersebut untuk data berukuran besar.
Worst Case adalah kondisi ketika sebuah algoritma membutuhkan waktu eksekusi atau penggunaan memori paling besar untuk menyelesaikan suatu masalah.
Worst Case merupakan analisis terhadap kondisi terburuk yang mungkin dihadapi oleh suatu algoritma.
Analisis ini menunjukkan batas maksimum waktu atau memori yang dibutuhkan algoritma ketika menerima input tertentu.
Worst Case sangat penting karena membantu programmer memperkirakan performa terburuk program, terutama ketika ukuran data sangat besar.
Misalnya, terdapat data sebanyak $n$ elemen. Sebuah algoritma harus memeriksa seluruh elemen sebelum menemukan data yang dicari.
Linear Search memeriksa data satu per satu dari awal. Kondisi terburuk terjadi ketika target berada pada posisi terakhir atau tidak terdapat di dalam data.
Dalam kondisi tersebut, algoritma harus memeriksa seluruh elemen.
def linear_search(data, target):
for index in range(len(data)):
if data[index] == target:
return index
return -1
data = [10, 20, 30, 40, 50]
hasil = linear_search(data, 50)
print(hasil)Binary Search membagi data menjadi dua bagian pada setiap langkah. Algoritma ini hanya dapat digunakan pada data yang sudah terurut.
Pada worst case, pencarian terus dilakukan sampai ruang pencarian tersisa satu elemen atau target tidak ditemukan.
def binary_search(data, target):
left = 0
right = len(data) - 1
while left <= right:
middle = (left + right) // 2
if data[middle] == target:
return middle
if data[middle] < target:
left = middle + 1
else:
right = middle - 1
return -1| Algoritma | Kondisi Worst Case | Kompleksitas |
|---|---|---|
| Bubble Sort | Data tersusun terbalik. | $O(n^2)$ |
| Selection Sort | Tetap membandingkan seluruh elemen. | $O(n^2)$ |
| Insertion Sort | Data tersusun terbalik. | $O(n^2)$ |
| Merge Sort | Data dibagi dan digabungkan secara penuh. | $O(n \log n)$ |
| Quick Sort | Pivot selalu menjadi elemen terkecil atau terbesar. | $O(n^2)$ |
Nested loop adalah perulangan yang berada di dalam perulangan lain. Jika setiap perulangan berjalan sebanyak $n$ kali, total operasi yang dilakukan adalah $n \cdot n$.
Oleh karena itu, kompleksitasnya adalah $O(n^2)$.
def print_pairs(data):
for i in data:
for j in data:
print(i, j)
data = [1, 2, 3, 4]
print_pairs(data)Algoritma rekursif memanggil dirinya sendiri. Jika jumlah pemanggilan bertambah sangat cepat, waktu eksekusinya juga dapat meningkat secara signifikan.
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)Recursive Fibonacci tanpa optimasi memiliki kompleksitas waktu eksponensial, yaitu $O(2^n)$. Hal ini terjadi karena banyak pemanggilan fungsi yang sama dilakukan berulang kali.
| Algoritma atau Operasi | Worst Case | Penjelasan |
|---|---|---|
| Akses Array | $O(1)$ | Elemen dapat diakses langsung berdasarkan indeks. |
| Linear Search | $O(n)$ | Seluruh elemen harus diperiksa. |
| Binary Search | $O(\log n)$ | Ruang pencarian dibagi menjadi dua. |
| Bubble Sort | $O(n^2)$ | Banyak perbandingan dan pertukaran data. |
| Quick Sort | $O(n^2)$ | Pemilihan pivot tidak seimbang. |
| Merge Sort | $O(n \log n)$ | Data dibagi dan digabungkan secara teratur. |
| Kondisi | Pengertian | Contoh Linear Search |
|---|---|---|
| Best Case | Kondisi paling menguntungkan. | Target berada di indeks pertama. |
| Average Case | Kondisi rata-rata. | Target berada di posisi tengah. |
| Worst Case | Kondisi paling tidak menguntungkan. | Target berada di indeks terakhir atau tidak ditemukan. |
Worst Case menggambarkan performa terburuk sebuah algoritma ketika memproses input tertentu. Analisis ini digunakan untuk mengetahui batas maksimum waktu dan memori. Dengan memahami Worst Case, programmer dapat memilih algoritma yang lebih efisien, stabil, dan dapat diprediksi.
Average Case adalah analisis terhadap waktu eksekusi atau penggunaan memori rata-rata yang dibutuhkan algoritma untuk memproses input secara umum.
Average Case menggambarkan performa algoritma pada kondisi input yang umum atau paling sering terjadi.
Analisis ini tidak menggunakan kondisi terbaik maupun terburuk, tetapi memperkirakan jumlah operasi rata-rata yang dilakukan algoritma.
Average Case penting karena performa algoritma dalam penggunaan nyata biasanya berada di antara Best Case dan Worst Case.
| Kondisi | Penjelasan | Contoh Linear Search |
|---|---|---|
| Best Case | Kondisi paling cepat. | Target berada di indeks pertama. |
| Average Case | Kondisi rata-rata. | Target berada di posisi acak atau tengah. |
| Worst Case | Kondisi paling lambat. | Target berada di indeks terakhir atau tidak ditemukan. |
Pada Linear Search, data diperiksa satu per satu mulai dari elemen pertama.
Jika target memiliki kemungkinan yang sama untuk berada di setiap posisi, maka secara rata-rata algoritma memeriksa sekitar setengah dari jumlah elemen.
def linear_search(data, target):
for index in range(len(data)):
if data[index] == target:
return index
return -1
data = [10, 20, 30, 40, 50]
hasil = linear_search(data, 30)
print("Indeks:", hasil)Binary Search bekerja dengan membagi ruang pencarian menjadi dua bagian pada setiap langkah.
Pada Average Case, target biasanya ditemukan setelah beberapa kali pembagian. Kompleksitasnya tetap $O(\log n)$ karena jumlah data yang diperiksa berkurang secara logaritmik.
def binary_search(data, target):
left = 0
right = len(data) - 1
while left <= right:
middle = (left + right) // 2
if data[middle] == target:
return middle
if data[middle] < target:
left = middle + 1
else:
right = middle - 1
return -1| Algoritma | Average Case | Penjelasan |
|---|---|---|
| Bubble Sort | $O(n^2)$ | Tetap melakukan banyak perbandingan dan pertukaran. |
| Selection Sort | $O(n^2)$ | Seluruh elemen tetap diperiksa. |
| Insertion Sort | $O(n^2)$ | Data biasanya membutuhkan beberapa pergeseran. |
| Merge Sort | $O(n \log n)$ | Pembagian data selalu dilakukan secara seimbang. |
| Quick Sort | $O(n \log n)$ | Pivot secara rata-rata membagi data dengan cukup seimbang. |
Jika sebuah target memiliki kemungkinan yang sama untuk berada di setiap posisi dalam data, jumlah pemeriksaan rata-rata dapat dihitung menggunakan rumus:
Hasilnya adalah sekitar $\frac{n+1}{2}$ pemeriksaan. Dalam notasi Big O, konstanta dan faktor tetap diabaikan, sehingga kompleksitasnya menjadi $O(n)$.
Misalkan terdapat 5 elemen:
| Posisi Target | Jumlah Pemeriksaan |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 4 |
| 5 | 5 |
Rata-rata pemeriksaan adalah 3 kali.
| Algoritma atau Operasi | Average Case | Keterangan |
|---|---|---|
| Akses Array | $O(1)$ | Akses indeks tidak bergantung pada posisi data. |
| Linear Search | $O(n)$ | Rata-rata memeriksa sebagian elemen. |
| Binary Search | $O(\log n)$ | Data dibagi menjadi dua pada setiap langkah. |
| Bubble Sort | $O(n^2)$ | Banyak perbandingan dilakukan pada data umum. |
| Merge Sort | $O(n \log n)$ | Pembagian data berlangsung konsisten. |
| Quick Sort | $O(n \log n)$ | Pivot rata-rata membagi data secara cukup seimbang. |
Average Case menggambarkan performa rata-rata algoritma pada input yang umum. Analisis ini membantu memperkirakan performa program dalam penggunaan nyata. Namun, Average Case tetap perlu dipertimbangkan bersama Best Case dan Worst Case agar analisis algoritma menjadi lebih lengkap.
Best Case adalah kondisi ketika suatu algoritma menyelesaikan masalah dengan waktu eksekusi atau penggunaan memori paling sedikit.
Best Case merupakan kondisi paling menguntungkan yang dapat dialami oleh sebuah algoritma ketika memproses input.
Pada kondisi ini, algoritma dapat menghasilkan solusi dengan jumlah operasi paling sedikit.
Analisis Best Case digunakan untuk mengetahui performa minimum atau waktu tercepat yang mungkin dicapai oleh suatu algoritma.
Pada Linear Search, Best Case terjadi ketika data yang dicari berada pada posisi pertama.
Algoritma hanya membutuhkan satu kali pemeriksaan sehingga kompleksitas waktunya adalah $O(1)$.
def linear_search(data, target):
for index in range(len(data)):
if data[index] == target:
return index
return -1
data = [10, 20, 30, 40, 50]
hasil = linear_search(data, 10)
print("Indeks:", hasil)Binary Search memiliki Best Case ketika target berada tepat di posisi tengah pada pemeriksaan pertama.
Algoritma langsung menemukan target tanpa melakukan pembagian ruang pencarian lebih lanjut.
def binary_search(data, target):
left = 0
right = len(data) - 1
while left <= right:
middle = (left + right) // 2
if data[middle] == target:
return middle
if data[middle] < target:
left = middle + 1
else:
right = middle - 1
return -1
data = [10, 20, 30, 40, 50]
hasil = binary_search(data, 30)
print("Indeks:", hasil)| Algoritma | Kondisi Best Case | Kompleksitas |
|---|---|---|
| Bubble Sort | Data sudah terurut dan algoritma menggunakan pemeriksaan pertukaran. | $O(n)$ |
| Selection Sort | Tetap mencari elemen terkecil pada setiap iterasi. | $O(n^2)$ |
| Insertion Sort | Data sudah terurut. | $O(n)$ |
| Merge Sort | Data dibagi dan digabungkan. | $O(n \log n)$ |
| Quick Sort | Pivot membagi data secara seimbang. | $O(n \log n)$ |
Bubble Sort dapat memiliki kompleksitas $O(n)$ apabila data sudah terurut dan algoritma dapat mendeteksi bahwa tidak ada pertukaran yang dilakukan.
Pemeriksaan tetap dilakukan, tetapi tidak terjadi proses pertukaran elemen.
def bubble_sort(data):
n = len(data)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if data[j] > data[j + 1]:
data[j], data[j + 1] = data[j + 1], data[j]
swapped = True
if not swapped:
break
return data
data = [10, 20, 30, 40, 50]
print(bubble_sort(data))Analisis Best Case dilakukan dengan mencari kondisi input yang menyebabkan algoritma melakukan operasi paling sedikit.
Contohnya, pada Linear Search, jika data ditemukan pada posisi pertama, hanya satu operasi perbandingan yang dilakukan. Oleh karena itu, kompleksitas Best Case-nya adalah $O(1)$.
| Algoritma atau Operasi | Best Case | Kondisi |
|---|---|---|
| Akses Array | $O(1)$ | Elemen langsung diakses berdasarkan indeks. |
| Linear Search | $O(1)$ | Target berada pada elemen pertama. |
| Binary Search | $O(1)$ | Target berada tepat di posisi tengah. |
| Bubble Sort | $O(n)$ | Data sudah terurut. |
| Insertion Sort | $O(n)$ | Data sudah terurut. |
| Merge Sort | $O(n \log n)$ | Proses pembagian dan penggabungan tetap dilakukan. |
| Quick Sort | $O(n \log n)$ | Pivot membagi data secara seimbang. |
| Kondisi | Keadaan Input | Tujuan Analisis |
|---|---|---|
| Best Case | Input paling ideal. | Mengetahui performa tercepat. |
| Average Case | Input umum atau acak. | Memperkirakan performa rata-rata. |
| Worst Case | Input paling tidak menguntungkan. | Mengetahui batas performa terburuk. |
Best Case menggambarkan kondisi paling menguntungkan bagi sebuah algoritma. Analisis ini membantu mengetahui waktu eksekusi minimum, tetapi belum cukup untuk menggambarkan performa algoritma secara keseluruhan. Oleh karena itu, Best Case sebaiknya dianalisis bersama Average Case dan Worst Case.
Analisis kompleksitas digunakan untuk mengukur efisiensi algoritma berdasarkan waktu eksekusi dan penggunaan memori terhadap ukuran input.
Analisis kompleksitas adalah proses untuk mengetahui seberapa efisien suatu algoritma ketika memproses data.
Efisiensi algoritma dapat dilihat dari jumlah waktu yang diperlukan dan jumlah memori yang digunakan.
Analisis dilakukan berdasarkan ukuran input, yang biasanya dilambangkan dengan $n$.
Time Complexity mengukur jumlah waktu atau operasi yang diperlukan algoritma untuk menyelesaikan proses.
Space Complexity mengukur jumlah memori tambahan yang dibutuhkan algoritma selama proses berjalan.
Notasi Big O digunakan untuk menggambarkan pertumbuhan kompleksitas algoritma terhadap ukuran input $n$.
Dalam analisis Big O, konstanta dan bagian yang tidak dominan biasanya diabaikan. Contohnya, $O(2n + 5)$ disederhanakan menjadi $O(n)$.
| Notasi | Nama | Contoh | Tingkat Efisiensi |
|---|---|---|---|
| $O(1)$ | Konstan | Akses array | Sangat efisien |
| $O(\log n)$ | Logaritmik | Binary Search | Sangat efisien |
| $O(n)$ | Linear | Linear Search | Efisien |
| $O(n \log n)$ | Linear-logaritmik | Merge Sort | Baik untuk data besar |
| $O(n^2)$ | Kuadratik | Bubble Sort | Kurang efisien |
| $O(2^n)$ | Eksponensial | Recursive Fibonacci | Sangat tidak efisien |
Algoritma dengan kompleksitas $O(1)$ membutuhkan waktu yang tetap meskipun jumlah data bertambah.
Contohnya adalah mengakses elemen array berdasarkan indeks.
def get_data(data, index):
return data[index]
data = [10, 20, 30, 40]
print(get_data(data, 2))Algoritma linear melakukan proses sebanyak jumlah data yang tersedia.
Jika jumlah data menjadi dua kali lipat, jumlah operasi biasanya juga meningkat sekitar dua kali lipat.
def display_all(data):
for item in data:
print(item)
data = [10, 20, 30, 40]
display_all(data)Kompleksitas logaritmik terjadi ketika ukuran masalah berkurang secara bertahap, biasanya menjadi setengah pada setiap iterasi.
Binary Search adalah contoh algoritma dengan kompleksitas $O(\log n)$.
def binary_search(data, target):
left = 0
right = len(data) - 1
while left <= right:
middle = (left + right) // 2
if data[middle] == target:
return middle
if data[middle] < target:
left = middle + 1
else:
right = middle - 1
return -1Kompleksitas kuadratik biasanya muncul ketika terdapat dua perulangan bersarang.
Setiap elemen dibandingkan dengan elemen lainnya sehingga jumlah operasi dapat mencapai $n \cdot n$.
def print_pairs(data):
for i in data:
for j in data:
print(i, j)
data = [1, 2, 3]
print_pairs(data)Kompleksitas $O(n \log n)$ biasanya muncul pada algoritma yang membagi data menjadi beberapa bagian, kemudian memproses setiap bagian.
Merge Sort merupakan salah satu contoh algoritma yang memiliki kompleksitas $O(n \log n)$.
def merge_sort(data):
if len(data) <= 1:
return data
middle = len(data) // 2
left = merge_sort(data[:middle])
right = merge_sort(data[middle:])
return merge(left, right)| Kondisi | Pengertian | Contoh Linear Search |
|---|---|---|
| Best Case | Kondisi paling menguntungkan | Data ditemukan pada posisi pertama |
| Average Case | Kondisi rata-rata | Data ditemukan pada posisi acak |
| Worst Case | Kondisi paling tidak menguntungkan | Data berada di akhir atau tidak ditemukan |
| Algoritma | Time Complexity | Space Complexity |
|---|---|---|
| Akses Array | $O(1)$ | $O(1)$ |
| Linear Search | $O(n)$ | $O(1)$ |
| Binary Search | $O(\log n)$ | $O(1)$ |
| Bubble Sort | $O(n^2)$ | $O(1)$ |
| Merge Sort | $O(n \log n)$ | $O(n)$ |
Analisis kompleksitas membantu mengukur efisiensi algoritma berdasarkan waktu dan memori. Notasi Big O digunakan untuk menggambarkan pertumbuhan kompleksitas terhadap ukuran input. Algoritma dengan pertumbuhan kompleksitas yang lebih rendah umumnya lebih efisien untuk memproses data berukuran besar.
Rekursi adalah teknik pemrograman ketika sebuah fungsi memanggil dirinya sendiri untuk menyelesaikan masalah yang lebih kecil dari masalah awal.
Rekursi adalah metode penyelesaian masalah dengan cara memecah masalah menjadi submasalah yang lebih kecil dan sejenis.
Fungsi rekursif akan terus memanggil dirinya sendiri sampai mencapai kondisi tertentu yang menghentikan proses.
Kondisi penghentian tersebut disebut base case, sedangkan pemanggilan fungsi terhadap dirinya sendiri disebut recursive case.
Setiap fungsi rekursif minimal memiliki dua bagian utama, yaitu kondisi berhenti dan pemanggilan rekursif.
def fungsi_rekursif(parameter):
# Base case
if kondisi_berhenti:
return hasil
# Recursive case
return fungsi_rekursif(parameter_yang_lebih_kecil)Fungsi berikut mencetak angka dari $n$ hingga $1$. Setelah mencetak nilai sekarang, fungsi memanggil dirinya sendiri dengan nilai yang lebih kecil.
Ketika $n$ bernilai $0$, fungsi berhenti karena base case terpenuhi.
def countdown(n):
if n == 0:
print("Selesai")
return
print(n)
countdown(n - 1)
countdown(5)Faktorial dari $n$ ditulis sebagai $n!$ dan didefinisikan sebagai:
def factorial(n):
if n == 0 or n == 1:
return 1
return n * factorial(n - 1)
print(factorial(5))Deret Fibonacci adalah deret yang setiap elemennya merupakan hasil penjumlahan dua elemen sebelumnya.
Rumusnya adalah:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(6))Setiap pemanggilan fungsi rekursif disimpan dalam call stack. Pemanggilan terakhir akan diselesaikan terlebih dahulu sebelum kembali ke pemanggilan sebelumnya.
| Tahap | Pemanggilan |
|---|---|
| 1 | factorial(4) |
| 2 | 4 * factorial(3) |
| 3 | 4 * 3 * factorial(2) |
| 4 | 4 * 3 * 2 * factorial(1) |
| 5 | 4 * 3 * 2 * 1 = 24 |
| Aspek | Rekursi | Iterasi |
|---|---|---|
| Metode | Fungsi memanggil dirinya sendiri | Menggunakan perulangan |
| Memori | Dapat menggunakan call stack | Biasanya lebih hemat |
| Kode | Lebih ringkas pada masalah tertentu | Dapat lebih panjang |
| Risiko | Stack overflow | Infinite loop |
| Cocok untuk | Tree, graph, divide and conquer | Perulangan sederhana |
def factorial_recursive(n):
if n <= 1:
return 1
return n * factorial_recursive(n - 1)def factorial_iterative(n):
hasil = 1
for angka in range(2, n + 1):
hasil *= angka
return hasil| Algoritma | Time Complexity | Space Complexity |
|---|---|---|
| Countdown | $O(n)$ | $O(n)$ |
| Factorial | $O(n)$ | $O(n)$ |
| Binary Search Rekursif | $O(\log n)$ | $O(\log n)$ |
| Fibonacci Naif | $O(2^n)$ | $O(n)$ |
| Merge Sort | $O(n \log n)$ | $O(n)$ |
Menelusuri node pada struktur pohon.
Digunakan dalam DFS dan traversal graph.
Membagi masalah menjadi bagian yang lebih kecil.
Menghitung faktorial, Fibonacci, dan kombinasi.
Rekursi adalah teknik ketika sebuah fungsi memanggil dirinya sendiri untuk menyelesaikan submasalah yang lebih kecil. Fungsi rekursif harus memiliki base case dan recursive case. Rekursi sangat berguna pada tree, graph, divide and conquer, serta permasalahan matematika, tetapi harus digunakan dengan hati-hati agar tidak menyebabkan stack overflow atau penggunaan memori yang berlebihan.
Divide and Conquer adalah strategi algoritma dengan membagi masalah besar menjadi beberapa submasalah yang lebih kecil, menyelesaikannya, kemudian menggabungkan hasilnya.
Divide and Conquer merupakan pendekatan algoritmik yang memecah masalah menjadi submasalah yang lebih kecil dan sejenis dengan masalah utama.
Setiap submasalah diselesaikan secara mandiri. Setelah semua submasalah selesai, hasilnya digabungkan untuk memperoleh solusi akhir.
Strategi ini banyak digunakan pada algoritma pengurutan, pencarian, perkalian matriks, dan pemrosesan struktur data.
Satu masalah dengan ukuran input $n$.
Masalah dibagi menjadi submasalah lebih kecil.
Hasil submasalah digabungkan.
def divide_and_conquer(data):
# Base case
if ukuran_masalah_kecil:
return solusi_langsung
# Divide
bagian_kiri, bagian_kanan = bagi(data)
# Conquer
hasil_kiri = divide_and_conquer(bagian_kiri)
hasil_kanan = divide_and_conquer(bagian_kanan)
# Combine
return gabungkan(hasil_kiri, hasil_kanan)Merge Sort membagi array menjadi dua bagian secara berulang hingga setiap bagian hanya memiliki satu elemen.
Setelah itu, setiap bagian digabungkan kembali dalam kondisi terurut.
def merge_sort(data):
if len(data) <= 1:
return data
middle = len(data) // 2
left = merge_sort(data[:middle])
right = merge_sort(data[middle:])
return merge(left, right)
def merge(left, right):
result = []
i = 0
j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
data = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(data))Binary Search bekerja pada data yang sudah terurut. Pada setiap langkah, data dibagi menjadi dua bagian dan hanya bagian yang mungkin berisi target yang diproses.
def binary_search(data, target, left, right):
if left > right:
return -1
middle = (left + right) // 2
if data[middle] == target:
return middle
if target < data[middle]:
return binary_search(
data,
target,
left,
middle - 1
)
return binary_search(
data,
target,
middle + 1,
right
)
data = [10, 20, 30, 40, 50, 60, 70]
hasil = binary_search(
data,
50,
0,
len(data) - 1
)
print("Indeks:", hasil)Quick Sort memilih satu elemen sebagai pivot. Data kemudian dipisahkan menjadi elemen yang lebih kecil dan lebih besar dari pivot.
Proses tersebut dilakukan secara rekursif hingga seluruh data terurut.
def quick_sort(data):
if len(data) <= 1:
return data
pivot = data[0]
left = [
item for item in data[1:]
if item <= pivot
]
right = [
item for item in data[1:]
if item > pivot
]
return quick_sort(left) + [pivot] + quick_sort(right)
data = [8, 3, 1, 7, 0, 10, 2]
print(quick_sort(data))Kompleksitas algoritma Divide and Conquer sering dinyatakan menggunakan relasi rekurensi.
| Simbol | Arti |
|---|---|
| $T(n)$ | Waktu untuk menyelesaikan masalah ukuran $n$ |
| $a$ | Jumlah submasalah |
| $n/b$ | Ukuran setiap submasalah |
| $f(n)$ | Waktu untuk membagi dan menggabungkan |
Master Theorem digunakan untuk menganalisis relasi rekurensi berbentuk:
| Kondisi | Kompleksitas | Contoh |
|---|---|---|
| $f(n)$ lebih kecil | $O(n^{\log_b a})$ | Binary recursion |
| $f(n)$ seimbang | $O(n^{\log_b a}\log n)$ | Merge Sort |
| $f(n)$ lebih besar | $O(f(n))$ | Beberapa algoritma pembagian |
Mengurutkan data dengan membagi array.
Membagi data berdasarkan pivot.
Membagi ruang pencarian menjadi dua.
Perkalian matriks secara efisien.
| Algoritma | Best Case | Average Case | Worst Case |
|---|---|---|---|
| Merge Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ |
| Quick Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n^2)$ |
| Binary Search | $O(1)$ | $O(\log n)$ | $O(\log n)$ |
Divide and Conquer menyelesaikan masalah dengan tiga tahapan, yaitu membagi masalah, menyelesaikan submasalah, dan menggabungkan hasilnya. Strategi ini menjadi dasar bagi Merge Sort, Quick Sort, Binary Search, serta berbagai algoritma efisien lainnya.
Binary Search adalah algoritma pencarian yang bekerja dengan membagi ruang pencarian menjadi dua bagian secara berulang.
Binary Search digunakan untuk mencari data tertentu pada kumpulan data yang sudah terurut.
Algoritma ini membandingkan data yang dicari dengan elemen tengah. Jika data belum ditemukan, pencarian dilanjutkan hanya pada setengah bagian yang mungkin mengandung target.
Dengan cara ini, jumlah data yang diperiksa berkurang secara signifikan pada setiap langkah.
10, 20, 30, 40, 50, 60, 70
40
60
Implementasi iteratif menggunakan perulangan
while untuk mempersempit batas pencarian.
def binary_search(data, target):
left = 0
right = len(data) - 1
while left <= right:
middle = (left + right) // 2
if data[middle] == target:
return middle
elif data[middle] < target:
left = middle + 1
else:
right = middle - 1
return -1
data = [10, 20, 30, 40, 50, 60, 70]
hasil = binary_search(data, 60)
if hasil != -1:
print("Data ditemukan pada indeks:", hasil)
else:
print("Data tidak ditemukan")Binary Search juga dapat diimplementasikan menggunakan rekursi. Setiap pemanggilan fungsi memproses setengah bagian data.
def binary_search_recursive(data, target, left, right):
if left > right:
return -1
middle = (left + right) // 2
if data[middle] == target:
return middle
if target < data[middle]:
return binary_search_recursive(
data,
target,
left,
middle - 1
)
return binary_search_recursive(
data,
target,
middle + 1,
right
)
data = [10, 20, 30, 40, 50, 60, 70]
hasil = binary_search_recursive(
data,
30,
0,
len(data) - 1
)
print("Indeks:", hasil)Misalkan data yang digunakan adalah $[10, 20, 30, 40, 50, 60, 70]$ dan target yang dicari adalah $60$.
| Langkah | Left | Right | Middle | Nilai Tengah | Keputusan |
|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 40 | Target lebih besar, ke kanan |
| 2 | 4 | 6 | 5 | 60 | Target ditemukan |
| Kondisi | Kompleksitas Waktu | Penjelasan |
|---|---|---|
| Best Case | $O(1)$ | Target langsung berada di elemen tengah. |
| Average Case | $O(\log n)$ | Target ditemukan setelah beberapa pembagian. |
| Worst Case | $O(\log n)$ | Target ditemukan pada tahap terakhir atau tidak ditemukan. |
| Aspek | Binary Search | Linear Search |
|---|---|---|
| Syarat Data | Harus terurut | Tidak harus terurut |
| Best Case | $O(1)$ | $O(1)$ |
| Average Case | $O(\log n)$ | $O(n)$ |
| Worst Case | $O(\log n)$ | $O(n)$ |
| Metode | Membagi data menjadi dua | Memeriksa satu per satu |
Mencari buku berdasarkan nomor atau kode terurut.
Mencari data berdasarkan kunci yang terurut.
Menemukan nilai dalam daftar numerik.
Menentukan nilai pada rentang tertentu.
Binary Search adalah algoritma pencarian yang efisien dengan cara membagi data menjadi dua bagian pada setiap langkah. Algoritma ini memiliki kompleksitas waktu rata-rata dan terburuk sebesar $O(\log n)$, tetapi hanya dapat digunakan pada data yang sudah terurut.
Merge Sort adalah algoritma pengurutan yang menggunakan strategi Divide and Conquer dengan membagi data menjadi beberapa bagian, mengurutkannya, lalu menggabungkannya kembali.
Merge Sort bekerja dengan membagi array menjadi dua bagian secara berulang sampai setiap bagian hanya memiliki satu elemen.
Bagian-bagian tersebut kemudian digabungkan kembali dalam keadaan terurut hingga membentuk array yang lengkap.
Merge Sort memiliki kompleksitas waktu $O(n \log n)$ pada Best Case, Average Case, maupun Worst Case.
Membagi array menjadi dua bagian secara berulang.
Mengurutkan setiap bagian secara rekursif.
Menggabungkan bagian-bagian yang sudah terurut.
Misalkan terdapat data berikut:
| Tahap | Proses | Hasil |
|---|---|---|
| 1 | Membagi array | [38, 27, 43] dan [3, 9, 82, 10] |
| 2 | Membagi kembali | [38], [27, 43], [3, 9], [82, 10] |
| 3 | Mengurutkan bagian kecil | [27, 43], [3, 9], [10, 82] |
| 4 | Menggabungkan bagian | [27, 38, 43] dan [3, 9, 10, 82] |
| 5 | Hasil akhir | [3, 9, 10, 27, 38, 43, 82] |
Implementasi berikut menggunakan fungsi rekursif untuk
membagi array dan fungsi merge() untuk
menggabungkan dua array yang sudah terurut.
def merge_sort(data):
if len(data) <= 1:
return data
middle = len(data) // 2
left = merge_sort(data[:middle])
right = merge_sort(data[middle:])
return merge(left, right)
def merge(left, right):
result = []
i = 0
j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
data = [38, 27, 43, 3, 9, 82, 10]
hasil = merge_sort(data)
print("Data terurut:", hasil)
Fungsi merge() bertugas membandingkan elemen
dari array kiri dan array kanan, kemudian mengambil elemen
terkecil untuk dimasukkan ke array hasil.
def merge(left, right):
result = []
i = 0
j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return resultPada setiap tahap, data dibagi menjadi dua bagian. Pembagian berlangsung sebanyak $\log n$ tingkat, sedangkan proses penggabungan pada setiap tingkat membutuhkan waktu $O(n)$.
| Kondisi | Time Complexity | Space Complexity |
|---|---|---|
| Best Case | $O(n \log n)$ | $O(n)$ |
| Average Case | $O(n \log n)$ | $O(n)$ |
| Worst Case | $O(n \log n)$ | $O(n)$ |
| Algoritma | Best Case | Average Case | Worst Case | Space |
|---|---|---|---|---|
| Bubble Sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ |
| Insertion Sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ |
| Quick Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n^2)$ | $O(\log n)$ |
| Merge Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ |
Mengurutkan data dalam jumlah besar.
Mengurutkan data yang tidak seluruhnya berada di memori.
Mengurutkan node pada Linked List.
Mengolah data secara terstruktur dan stabil.
Merge Sort adalah algoritma pengurutan berbasis Divide and Conquer. Algoritma ini membagi data menjadi bagian-bagian kecil, mengurutkannya, lalu menggabungkan kembali hasilnya. Merge Sort memiliki kompleksitas waktu $O(n \log n)$ pada semua kondisi, tetapi membutuhkan memori tambahan sebesar $O(n)$.
Bubble Sort adalah algoritma pengurutan yang membandingkan elemen yang berdekatan dan menukarnya apabila urutannya salah.
Bubble Sort bekerja dengan membandingkan dua elemen yang bersebelahan. Jika elemen di sebelah kiri lebih besar daripada elemen di sebelah kanan, kedua elemen tersebut ditukar.
Proses ini dilakukan berulang kali sampai seluruh data berada dalam urutan yang benar.
Elemen terbesar secara bertahap akan berpindah ke bagian paling kanan, seperti gelembung yang naik ke permukaan. Karena itu, algoritma ini disebut Bubble Sort.
Misalkan terdapat data:
| Langkah | Perbandingan | Hasil |
|---|---|---|
| 1 | 5 dibandingkan dengan 3 | [3, 5, 8, 4, 2] |
| 2 | 5 dibandingkan dengan 8 | [3, 5, 8, 4, 2] |
| 3 | 8 dibandingkan dengan 4 | [3, 5, 4, 8, 2] |
| 4 | 8 dibandingkan dengan 2 | [3, 5, 4, 2, 8] |
| 5 | 5 dibandingkan dengan 4 | [3, 4, 5, 2, 8] |
| 6 | 5 dibandingkan dengan 2 | [3, 4, 2, 5, 8] |
| 7 | 4 dibandingkan dengan 2 | [3, 2, 4, 5, 8] |
| 8 | 3 dibandingkan dengan 2 | [2, 3, 4, 5, 8] |
Implementasi dasar menggunakan dua perulangan. Perulangan pertama menentukan jumlah putaran, sedangkan perulangan kedua membandingkan elemen yang berdekatan.
def bubble_sort(data):
n = len(data)
for i in range(n):
for j in range(0, n - i - 1):
if data[j] > data[j + 1]:
data[j], data[j + 1] = \
data[j + 1], data[j]
return data
data = [5, 3, 8, 4, 2]
hasil = bubble_sort(data)
print("Data terurut:", hasil)
Bubble Sort dapat dioptimalkan dengan variabel
swapped. Variabel ini digunakan untuk
mengetahui apakah terjadi pertukaran pada suatu putaran.
Jika tidak ada pertukaran, berarti data sudah terurut dan algoritma dapat berhenti lebih awal.
def bubble_sort_optimized(data):
n = len(data)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if data[j] > data[j + 1]:
data[j], data[j + 1] = \
data[j + 1], data[j]
swapped = True
if not swapped:
break
return data
data = [1, 2, 3, 4, 5]
print(bubble_sort_optimized(data))| Kondisi | Kompleksitas Waktu | Keterangan |
|---|---|---|
| Best Case | $O(n)$ |
Data sudah terurut dan menggunakan
optimasi swapped.
|
| Average Case | $O(n^2)$ | Data berada dalam urutan acak. |
| Worst Case | $O(n^2)$ | Data tersusun terbalik. |
Bubble Sort melakukan pengurutan langsung pada array yang tersedia. Algoritma ini tidak membutuhkan array tambahan dengan ukuran yang bergantung pada jumlah data.
Pertukaran dilakukan langsung pada posisi elemen:
data[j], data[j + 1] = \
data[j + 1], data[j]Hanya diperlukan beberapa variabel sementara, sehingga ruang tambahan tetap konstan.
| Algoritma | Best Case | Average Case | Worst Case | Space |
|---|---|---|---|---|
| Bubble Sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ |
| Insertion Sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ |
| Merge Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ |
| Quick Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n^2)$ | $O(\log n)$ |
Memahami konsep dasar algoritma pengurutan.
Mengurutkan data dengan jumlah elemen sedikit.
Digunakan pada latihan pemrograman dasar.
Digunakan untuk menguji konsep sorting.
swapped untuk optimasi.
Bubble Sort adalah algoritma pengurutan sederhana yang bekerja dengan membandingkan dan menukar elemen yang bersebelahan. Algoritma ini memiliki kompleksitas rata-rata dan terburuk $O(n^2)$, sedangkan Best Case-nya dapat mencapai $O(n)$ jika menggunakan optimasi dan data sudah terurut. Bubble Sort mudah dipahami, tetapi kurang sesuai untuk data berukuran besar.
Selection Sort adalah algoritma pengurutan yang mencari elemen terkecil atau terbesar dari bagian data yang belum terurut, kemudian menempatkannya pada posisi yang sesuai.
Selection Sort bekerja dengan membagi data menjadi dua bagian, yaitu bagian yang sudah terurut dan bagian yang belum terurut.
Pada setiap putaran, algoritma mencari elemen terkecil dari bagian yang belum terurut, lalu menukarnya dengan elemen pertama pada bagian tersebut.
Proses dilakukan berulang hingga seluruh data berada dalam urutan yang benar.
Misalkan terdapat data:
| Putaran | Elemen Terkecil | Proses Pertukaran | Hasil |
|---|---|---|---|
| 1 | 11 | 64 ditukar dengan 11 | [11, 25, 12, 22, 64] |
| 2 | 12 | 25 ditukar dengan 12 | [11, 12, 25, 22, 64] |
| 3 | 22 | 25 ditukar dengan 22 | [11, 12, 22, 25, 64] |
| 4 | 25 | Tidak ada pertukaran penting | [11, 12, 22, 25, 64] |
Pada setiap putaran, variabel min_index
digunakan untuk menyimpan posisi elemen terkecil.
Setelah pencarian selesai, elemen terkecil ditukar dengan elemen pada posisi awal bagian yang belum terurut.
def selection_sort(data):
n = len(data)
for i in range(n - 1):
min_index = i
for j in range(i + 1, n):
if data[j] < data[min_index]:
min_index = j
data[i], data[min_index] = \
data[min_index], data[i]
return data
data = [64, 25, 12, 22, 11]
hasil = selection_sort(data)
print("Data terurut:", hasil)Untuk mengurutkan data dari terbesar ke terkecil, pencarian dilakukan terhadap elemen terbesar.
def selection_sort_descending(data):
n = len(data)
for i in range(n - 1):
max_index = i
for j in range(i + 1, n):
if data[j] > data[max_index]:
max_index = j
data[i], data[max_index] = \
data[max_index], data[i]
return data
data = [64, 25, 12, 22, 11]
print(selection_sort_descending(data))Selection Sort tetap mencari elemen terkecil pada seluruh bagian data yang belum terurut. Oleh karena itu, jumlah perbandingan hampir selalu sama untuk berbagai kondisi input.
| Kondisi | Kompleksitas Waktu | Keterangan |
|---|---|---|
| Best Case | $O(n^2)$ | Data sudah terurut, tetapi perbandingan tetap dilakukan. |
| Average Case | $O(n^2)$ | Data berada dalam urutan acak. |
| Worst Case | $O(n^2)$ | Data tersusun terbalik. |
Selection Sort melakukan pertukaran elemen langsung pada array yang sama. Algoritma ini tidak membutuhkan array tambahan dengan ukuran $n$.
Pertukaran dilakukan menggunakan beberapa variabel sementara saja:
data[i], data[min_index] = \
data[min_index], data[i]Karena tidak membuat array baru, kebutuhan ruang tambahannya tetap konstan.
Selection Sort standar umumnya tidak bersifat stable sorting. Pertukaran elemen dapat mengubah urutan relatif data yang memiliki nilai sama.
| Algoritma | Best Case | Average Case | Worst Case | Space |
|---|---|---|---|---|
| Selection Sort | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ |
| Bubble Sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ |
| Insertion Sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ |
| Merge Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ |
| Quick Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n^2)$ | $O(\log n)$ |
Memahami konsep dasar algoritma sorting.
Mengurutkan data dengan jumlah elemen sedikit.
Digunakan ketika jumlah pertukaran perlu dikurangi.
Cocok untuk latihan pemrograman.
Selection Sort adalah algoritma pengurutan sederhana yang mencari elemen terkecil dari bagian data yang belum terurut, kemudian menempatkannya pada posisi yang tepat. Algoritma ini memiliki kompleksitas waktu $O(n^2)$ pada semua kondisi dan kompleksitas ruang $O(1)$. Selection Sort mudah dipahami dan hemat memori, tetapi kurang efisien untuk data berukuran besar.
Insertion Sort adalah algoritma pengurutan yang menyusun data satu per satu dengan memasukkan setiap elemen ke posisi yang tepat pada bagian data yang sudah terurut.
Insertion Sort bekerja dengan membagi data menjadi dua bagian, yaitu bagian yang sudah terurut dan bagian yang belum terurut.
Setiap elemen dari bagian yang belum terurut diambil, kemudian dibandingkan dengan elemen pada bagian terurut.
Elemen tersebut digeser sampai ditemukan posisi yang tepat, lalu dimasukkan ke posisi tersebut.
Misalkan terdapat data:
| Putaran | Key | Proses | Hasil |
|---|---|---|---|
| 1 | 3 | 3 dimasukkan sebelum 5 | [3, 5, 8, 4, 2] |
| 2 | 8 | 8 tetap setelah 5 | [3, 5, 8, 4, 2] |
| 3 | 4 | 4 dimasukkan antara 3 dan 5 | [3, 4, 5, 8, 2] |
| 4 | 2 | 2 dimasukkan di posisi pertama | [2, 3, 4, 5, 8] |
Variabel key menyimpan elemen yang sedang
diproses. Elemen yang lebih besar dari key
akan digeser ke kanan.
Setelah posisi yang tepat ditemukan, key
dimasukkan ke dalam array.
def insertion_sort(data):
for i in range(1, len(data)):
key = data[i]
j = i - 1
while j >= 0 and data[j] > key:
data[j + 1] = data[j]
j -= 1
data[j + 1] = key
return data
data = [5, 3, 8, 4, 2]
hasil = insertion_sort(data)
print("Data terurut:", hasil)Untuk mengurutkan data dari terbesar ke terkecil, kondisi perbandingan diubah dari tanda lebih besar menjadi tanda lebih kecil.
def insertion_sort_descending(data):
for i in range(1, len(data)):
key = data[i]
j = i - 1
while j >= 0 and data[j] < key:
data[j + 1] = data[j]
j -= 1
data[j + 1] = key
return data
data = [5, 3, 8, 4, 2]
print(insertion_sort_descending(data))| Kondisi | Kompleksitas Waktu | Keterangan |
|---|---|---|
| Best Case | $O(n)$ | Data sudah terurut sehingga hampir tidak ada pergeseran. |
| Average Case | $O(n^2)$ | Data berada dalam urutan acak. |
| Worst Case | $O(n^2)$ | Data tersusun terbalik sehingga setiap elemen harus digeser. |
Insertion Sort mengurutkan data langsung pada array yang sama dan hanya menggunakan beberapa variabel tambahan.
Insertion Sort termasuk stable sorting karena elemen yang memiliki nilai sama tidak perlu berpindah melewati satu sama lain.
| Algoritma | Best Case | Average Case | Worst Case | Space |
|---|---|---|---|---|
| Insertion Sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ |
| Selection Sort | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ |
| Bubble Sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ |
| Merge Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ |
| Quick Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n^2)$ | $O(\log n)$ |
Memahami dasar algoritma pengurutan.
Menyusun data yang hanya mengalami sedikit perubahan.
Menambahkan elemen baru ke data yang sudah terurut.
Digunakan dalam latihan pemrograman dasar.
key untuk menyimpan elemen
yang sedang diproses.
key setelah posisi yang tepat ditemukan.
Insertion Sort adalah algoritma pengurutan yang memasukkan setiap elemen ke posisi yang tepat pada bagian data yang sudah terurut. Algoritma ini memiliki Best Case $O(n)$ untuk data yang sudah terurut, Average Case dan Worst Case $O(n^2)$, serta kompleksitas ruang $O(1)$. Insertion Sort sangat cocok untuk data berukuran kecil atau data yang hampir terurut.
Shell Sort adalah pengembangan dari Insertion Sort yang membandingkan elemen-elemen dengan jarak tertentu sebelum akhirnya melakukan pengurutan berjarak satu.
Shell Sort mengurutkan data dengan membandingkan elemen yang memiliki jarak tertentu atau disebut gap.
Pada awal proses, nilai gap biasanya besar. Nilai tersebut kemudian dikurangi secara bertahap hingga menjadi satu.
Ketika gap bernilai satu, proses pengurutan menyerupai Insertion Sort, tetapi data sudah lebih dekat dengan kondisi terurut.
Gap adalah jarak antara dua elemen yang dibandingkan. Misalnya, jika gap bernilai $4$, maka elemen pada indeks $0$ dibandingkan dengan elemen pada indeks $4$.
| Gap | Pasangan Indeks | Tujuan |
|---|---|---|
| 4 | (0, 4), (1, 5), (2, 6) | Memindahkan elemen secara cepat |
| 2 | (0, 2), (1, 3), (2, 4) | Memperbaiki urutan data |
| 1 | Elemen bersebelahan | Menyelesaikan pengurutan akhir |
Misalkan terdapat data:
| Tahap | Gap | Proses | Hasil Sementara |
|---|---|---|---|
| 1 | 2 | Membandingkan elemen berjarak dua | [3, 2, 12, 34, 54] |
| 2 | 1 | Mengurutkan elemen bersebelahan | [2, 3, 12, 34, 54] |
Implementasi berikut menggunakan metode pembagian dua untuk menentukan nilai gap.
Proses pengurutan pada setiap gap menggunakan pola yang mirip dengan Insertion Sort.
def shell_sort(data):
n = len(data)
gap = n // 2
while gap > 0:
for i in range(gap, n):
temp = data[i]
j = i
while j >= gap and data[j - gap] > temp:
data[j] = data[j - gap]
j -= gap
data[j] = temp
gap //= 2
return data
data = [12, 34, 54, 2, 3]
hasil = shell_sort(data)
print("Data terurut:", hasil)Performa Shell Sort dipengaruhi oleh urutan nilai gap yang digunakan. Beberapa urutan gap yang umum adalah sebagai berikut:
| Nama Urutan | Contoh Urutan Gap | Keterangan |
|---|---|---|
| Shell Original | $n/2, n/4, \ldots, 1$ | Sederhana dan mudah digunakan |
| Knuth | $1, 4, 13, 40, \ldots$ | Sering memberikan performa yang baik |
| Hibbard | $1, 3, 7, 15, \ldots$ | Menggunakan bentuk $2^k - 1$ |
| Tokuda | Urutan berdasarkan rasio tertentu | Digunakan untuk optimasi tertentu |
Kompleksitas Shell Sort bergantung pada urutan gap yang digunakan. Oleh karena itu, tidak ada satu nilai kompleksitas yang berlaku untuk semua implementasi.
| Kondisi | Kompleksitas Umum | Keterangan |
|---|---|---|
| Best Case | $O(n \log n)$ | Dapat terjadi pada urutan data dan gap tertentu. |
| Average Case | Sekitar $O(n^{3/2})$ | Bergantung pada urutan gap yang digunakan. |
| Worst Case | $O(n^2)$ | Dapat terjadi pada urutan gap yang kurang baik. |
Shell Sort melakukan pengurutan langsung pada array dan hanya membutuhkan beberapa variabel tambahan.
Shell Sort umumnya tidak bersifat stable sorting karena elemen yang sama dapat berpindah melewati satu sama lain akibat perbandingan dengan gap tertentu.
| Algoritma | Best Case | Average Case | Worst Case | Space |
|---|---|---|---|---|
| Shell Sort | $O(n \log n)$ | Sekitar $O(n^{3/2})$ | $O(n^2)$ | $O(1)$ |
| Insertion Sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ |
| Selection Sort | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ |
| Merge Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ |
| Quick Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n^2)$ | $O(\log n)$ |
Mengurutkan data dengan ukuran menengah.
Cocok ketika penggunaan memori tambahan harus diminimalkan.
Dapat digunakan pada sistem dengan sumber daya terbatas.
Digunakan untuk memahami konsep gap dan insertion.
Shell Sort adalah pengembangan dari Insertion Sort yang menggunakan jarak atau gap untuk membandingkan elemen. Nilai gap dikurangi secara bertahap hingga menjadi satu. Shell Sort menggunakan ruang tambahan $O(1), tetapi kompleksitas waktunya bergantung pada urutan gap yang digunakan. Algoritma ini umumnya lebih cepat daripada Insertion Sort untuk data berukuran sedang.
Quick Sort adalah algoritma pengurutan berbasis Divide and Conquer yang menggunakan elemen pivot untuk membagi data.
Quick Sort memilih satu elemen sebagai pivot. Elemen lain kemudian dibagi menjadi dua kelompok, yaitu elemen yang lebih kecil dan lebih besar dari pivot.
Setiap kelompok diurutkan kembali secara rekursif hingga seluruh data berada pada posisi yang benar.
Performa Quick Sort sangat dipengaruhi oleh pemilihan pivot.
Data awal:
| Tahap | Pivot | Bagian Kiri | Bagian Kanan |
|---|---|---|---|
| 1 | 8 | [3, 1, 7, 0, 2] | [10] |
| 2 | 3 | [1, 0, 2] | [7] |
| 3 | 1 | [0] | [2] |
| 4 | - | [0, 1, 2, 3, 7, 8, 10] | |
Contoh berikut memilih elemen pertama sebagai pivot, lalu membuat bagian kiri dan kanan berdasarkan nilai pivot.
def quick_sort(data):
if len(data) <= 1:
return data
pivot = data[0]
left = [
item for item in data[1:]
if item <= pivot
]
right = [
item for item in data[1:]
if item > pivot
]
return (
quick_sort(left)
+ [pivot]
+ quick_sort(right)
)
data = [8, 3, 1, 7, 0, 10, 2]
hasil = quick_sort(data)
print("Data terurut:", hasil)Partition adalah proses menempatkan pivot pada posisi yang benar. Setelah proses ini selesai, semua elemen di sebelah kiri pivot lebih kecil dan semua elemen di sebelah kanan pivot lebih besar.
def partition(data, low, high):
pivot = data[high]
i = low - 1
for j in range(low, high):
if data[j] <= pivot:
i += 1
data[i], data[j] = \
data[j], data[i]
data[i + 1], data[high] = \
data[high], data[i + 1]
return i + 1Versi in-place melakukan pertukaran langsung pada array tanpa membuat array kiri dan kanan baru.
Cara ini lebih hemat memori dibandingkan implementasi yang menggunakan array tambahan.
def quick_sort_in_place(data, low, high):
if low < high:
pivot_index = partition(
data,
low,
high
)
quick_sort_in_place(
data,
low,
pivot_index - 1
)
quick_sort_in_place(
data,
pivot_index + 1,
high
)
data = [8, 3, 1, 7, 0, 10, 2]
quick_sort_in_place(
data,
0,
len(data) - 1
)
print(data)| Strategi | Penjelasan | Keterangan |
|---|---|---|
| Elemen Pertama | Pivot dipilih dari indeks pertama. | Sederhana, tetapi berisiko tidak seimbang. |
| Elemen Terakhir | Pivot dipilih dari indeks terakhir. | Mudah diterapkan. |
| Elemen Tengah | Pivot dipilih dari posisi tengah. | Dapat menghasilkan pembagian lebih baik. |
| Random Pivot | Pivot dipilih secara acak. | Mengurangi risiko pola terburuk. |
| Median-of-Three | Memilih median dari tiga elemen. | Pivot cenderung lebih representatif. |
| Kondisi | Kompleksitas Waktu | Keterangan |
|---|---|---|
| Best Case | $O(n \log n)$ | Pivot membagi data secara seimbang. |
| Average Case | $O(n \log n)$ | Pembagian data relatif seimbang. |
| Worst Case | $O(n^2)$ | Pivot selalu menjadi elemen terkecil atau terbesar. |
Quick Sort in-place tidak membutuhkan array kiri dan kanan tambahan. Namun, pemanggilan rekursif tetap menggunakan call stack.
Quick Sort standar umumnya tidak bersifat stable sorting karena proses partition dapat mengubah urutan relatif elemen yang memiliki nilai sama.
| Algoritma | Best Case | Average Case | Worst Case | Space |
|---|---|---|---|---|
| Quick Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n^2)$ | $O(\log n)$ |
| Merge Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ |
| Heap Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(1)$ |
| Insertion Sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ |
Mengurutkan data berdasarkan nilai tertentu.
Membantu menyiapkan data sebelum pencarian.
Mengurutkan data numerik dan statistik.
Digunakan sebagai algoritma sorting umum.
Quick Sort adalah algoritma pengurutan berbasis Divide and Conquer yang menggunakan pivot untuk membagi data. Algoritma ini memiliki kompleksitas Average Case $O(n \log n)$ dan Worst Case $O(n^2)$. Pemilihan pivot yang baik sangat penting untuk menjaga performa Quick Sort. Algoritma ini cepat dalam praktik dan dapat dilakukan secara in-place, tetapi umumnya tidak stable sorting.
Heap Sort adalah algoritma pengurutan yang menggunakan struktur data Heap untuk menentukan elemen terbesar atau terkecil secara efisien.
Heap Sort bekerja dengan mengubah array menjadi struktur Heap, kemudian mengambil elemen terbesar atau terkecil secara bertahap untuk ditempatkan pada posisi yang tepat.
Untuk pengurutan menaik, Heap Sort biasanya menggunakan Max Heap. Elemen terbesar ditempatkan di bagian akhir array.
Heap Sort memiliki kompleksitas waktu $O(n \log n)$ pada Best Case, Average Case, dan Worst Case.
Heap adalah struktur data berbentuk pohon biner lengkap yang biasanya direpresentasikan menggunakan array.
Nilai parent selalu lebih besar atau sama dengan nilai child. Elemen terbesar berada di root.
Nilai parent selalu lebih kecil atau sama dengan nilai child. Elemen terkecil berada di root.
Jika sebuah node berada pada indeks $i$, posisi node lainnya dapat dihitung menggunakan rumus berikut:
| Node | Indeks | Child Kiri | Child Kanan |
|---|---|---|---|
| Root | $0$ | $1$ | $2$ |
| Node Indeks $1$ | $1$ | $3$ | $4$ |
| Node Indeks $2$ | $2$ | $5$ | $6$ |
heapify pada root.
Misalkan terdapat data:
| Tahap | Proses | Hasil |
|---|---|---|
| 1 | Membangun Max Heap | [10, 5, 3, 4, 1] |
| 2 | Tukar root dengan elemen terakhir | [1, 5, 3, 4, 10] |
| 3 | Heapify bagian yang belum terurut | [5, 4, 3, 1, 10] |
| 4 | Tukar root berikutnya | [1, 4, 3, 5, 10] |
| 5 | Hasil akhir | [1, 3, 4, 5, 10] |
Heapify digunakan untuk menjaga aturan Heap setelah terjadi pertukaran elemen.
Fungsi ini membandingkan node dengan child kiri dan child kanan, lalu menempatkan nilai terbesar pada posisi parent.
def heapify(data, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and data[left] > data[largest]:
largest = left
if right < n and data[right] > data[largest]:
largest = right
if largest != i:
data[i], data[largest] = \
data[largest], data[i]
heapify(data, n, largest)def heapify(data, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and data[left] > data[largest]:
largest = left
if right < n and data[right] > data[largest]:
largest = right
if largest != i:
data[i], data[largest] = \
data[largest], data[i]
heapify(data, n, largest)
def heap_sort(data):
n = len(data)
# Membangun Max Heap
for i in range(n // 2 - 1, -1, -1):
heapify(data, n, i)
# Memindahkan elemen terbesar
for end in range(n - 1, 0, -1):
data[0], data[end] = \
data[end], data[0]
heapify(data, end, 0)
return data
data = [4, 10, 3, 5, 1]
hasil = heap_sort(data)
print("Data terurut:", hasil)
Membangun Heap membutuhkan waktu $O(n)$. Setelah itu, setiap
elemen dikeluarkan dari Heap dengan proses
heapify yang membutuhkan waktu $O(\log n)$.
| Kondisi | Kompleksitas Waktu | Kompleksitas Ruang |
|---|---|---|
| Best Case | $O(n \log n)$ | $O(1)$ |
| Average Case | $O(n \log n)$ | $O(1)$ |
| Worst Case | $O(n \log n)$ | $O(1)$ |
| Algoritma | Best Case | Average Case | Worst Case | Space |
|---|---|---|---|---|
| Heap Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(1)$ |
| Quick Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n^2)$ | $O(\log n)$ |
| Merge Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ |
| Insertion Sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ |
Mengurutkan data dengan batas performa yang terjamin.
Heap menjadi dasar implementasi Priority Queue.
Digunakan dalam algoritma seperti Heap-based processing.
Cocok ketika algoritma harus bekerja secara in-place.
heapify untuk menjaga aturan
Heap.
Heap Sort adalah algoritma pengurutan yang menggunakan struktur data Heap. Untuk pengurutan menaik, Max Heap digunakan agar elemen terbesar dapat ditempatkan di akhir array. Heap Sort memiliki kompleksitas waktu $O(n \log n)$ pada semua kondisi, kompleksitas ruang $O(1)$, dan dapat dilakukan secara in-place. Namun, algoritma ini umumnya tidak stable sorting.
Radix Sort adalah algoritma pengurutan non-comparison yang mengurutkan data berdasarkan setiap digit atau posisi angka, mulai dari digit paling rendah hingga digit paling tinggi.
Radix Sort mengurutkan bilangan dengan memproses digit pada setiap posisi. Proses biasanya dimulai dari digit satuan, kemudian puluhan, ratusan, dan seterusnya.
Pada setiap tahap, data dikelompokkan berdasarkan digit yang sedang diproses menggunakan algoritma stabil, seperti Counting Sort.
Radix Sort cocok digunakan untuk bilangan bulat dengan jumlah digit yang tidak terlalu besar.
Misalkan terdapat data:
| Tahap | Digit | Hasil Pengurutan |
|---|---|---|
| 1 | Satuan | [170, 90, 802, 2, 24, 45, 75, 66] |
| 2 | Puluhan | [802, 2, 24, 45, 66, 170, 75, 90] |
| 3 | Ratusan | [2, 24, 45, 66, 75, 90, 170, 802] |
Implementasi berikut menggunakan Counting Sort untuk mengurutkan data berdasarkan digit tertentu.
def counting_sort_by_digit(data, place):
n = len(data)
output = [0] * n
count = [0] * 10
for number in data:
digit = (number // place) % 10
count[digit] += 1
for i in range(1, 10):
count[i] += count[i - 1]
for i in range(n - 1, -1, -1):
digit = (data[i] // place) % 10
output[count[digit] - 1] = data[i]
count[digit] -= 1
for i in range(n):
data[i] = output[i]
def radix_sort(data):
maximum = max(data)
place = 1
while maximum // place > 0:
counting_sort_by_digit(data, place)
place *= 10
return data
data = [170, 45, 75, 90, 802, 24, 2, 66]
hasil = radix_sort(data)
print("Data terurut:", hasil)Counting Sort digunakan pada setiap tahap untuk mengurutkan data berdasarkan digit tertentu.
Proses harus stabil agar urutan hasil pengurutan dari digit sebelumnya tetap dipertahankan.
Misalkan $d$ adalah jumlah digit, $n$ adalah jumlah elemen, dan $k$ adalah basis bilangan yang digunakan.
| Aspek | Kompleksitas | Keterangan |
|---|---|---|
| Time Complexity | $O(d(n + k))$ | Bergantung pada jumlah digit dan basis angka. |
| Space Complexity | $O(n + k)$ | Membutuhkan array output dan count. |
| Basis Desimal | $k = 10$ | Menggunakan digit 0 sampai 9. |
| Algoritma | Average Case | Worst Case | Space |
|---|---|---|---|
| Radix Sort | $O(d(n + k))$ | $O(d(n + k))$ | $O(n + k)$ |
| Quick Sort | $O(n \log n)$ | $O(n^2)$ | $O(\log n)$ |
| Merge Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ |
| Heap Sort | $O(n \log n)$ | $O(n \log n)$ | $O(1)$ |
Mengurutkan bilangan dengan jumlah digit tertentu.
Mengurutkan kode atau nomor yang memiliki format seragam.
Mengurutkan data numerik dengan panjang terbatas.
Mengolah data numerik dalam jumlah besar.
Radix Sort adalah algoritma pengurutan non-comparison yang mengurutkan data berdasarkan digit dari posisi paling rendah hingga paling tinggi. Dengan kompleksitas $O(d(n + k))$, Radix Sort dapat bekerja sangat cepat pada data numerik dengan jumlah digit terbatas. Namun, algoritma ini membutuhkan memori tambahan dan harus menggunakan algoritma sorting yang stabil pada setiap tahap.
Linear Search adalah algoritma pencarian yang memeriksa setiap elemen secara berurutan mulai dari elemen pertama hingga data yang dicari ditemukan atau seluruh elemen selesai diperiksa.
Linear Search, atau Sequential Search, merupakan algoritma pencarian yang membandingkan target dengan setiap elemen data secara berurutan.
Pencarian dimulai dari indeks pertama. Jika elemen tersebut bukan target, algoritma berpindah ke elemen berikutnya.
Linear Search dapat digunakan pada data yang sudah terurut maupun belum terurut.
Misalkan terdapat data berikut dan target yang dicari adalah $40$:
| Langkah | Indeks | Nilai | Perbandingan | Hasil |
|---|---|---|---|---|
| 1 | 0 | 15 | 15 dibandingkan dengan 40 | Belum ditemukan |
| 2 | 1 | 8 | 8 dibandingkan dengan 40 | Belum ditemukan |
| 3 | 2 | 23 | 23 dibandingkan dengan 40 | Belum ditemukan |
| 4 | 3 | 40 | 40 dibandingkan dengan 40 | Data ditemukan |
Program melakukan perulangan dari indeks pertama sampai indeks terakhir.
Fungsi mengembalikan indeks ketika target ditemukan dan mengembalikan $-1$ jika target tidak ada.
def linear_search(data, target):
for index in range(len(data)):
if data[index] == target:
return index
return -1
data = [15, 8, 23, 40, 12]
hasil = linear_search(data, 40)
if hasil != -1:
print("Data ditemukan pada indeks:", hasil)
else:
print("Data tidak ditemukan")Linear Search juga dapat dibuat menggunakan rekursi. Fungsi memeriksa satu indeks pada setiap pemanggilan.
def linear_search_recursive(data, target, index):
if index >= len(data):
return -1
if data[index] == target:
return index
return linear_search_recursive(
data,
target,
index + 1
)
data = [15, 8, 23, 40, 12]
hasil = linear_search_recursive(
data,
23,
0
)
print("Indeks:", hasil)Jika terdapat beberapa elemen yang memiliki nilai sama, Linear Search dapat digunakan untuk menemukan seluruh indeks kemunculannya.
def find_all(data, target):
indexes = []
for index, value in enumerate(data):
if value == target:
indexes.append(index)
return indexes
data = [10, 20, 10, 30, 10]
hasil = find_all(data, 10)
print("Indeks target:", hasil)| Kondisi | Kompleksitas Waktu | Keterangan |
|---|---|---|
| Best Case | $O(1)$ | Target berada pada elemen pertama. |
| Average Case | $O(n)$ | Target berada di bagian tengah data. |
| Worst Case | $O(n)$ | Target berada di elemen terakhir atau tidak ditemukan. |
| Aspek | Linear Search | Binary Search |
|---|---|---|
| Syarat Data | Tidak harus terurut | Harus terurut |
| Best Case | $O(1)$ | $O(1)$ |
| Average Case | $O(n)$ | $O(\log n)$ |
| Worst Case | $O(n)$ | $O(\log n)$ |
| Metode | Memeriksa data satu per satu | Membagi data menjadi dua |
| Struktur Data | Array, Linked List, dan lainnya | Lebih cocok untuk array |
Mencari nama dalam daftar kontak sederhana.
Mencari nilai pada daftar yang belum terurut.
Menelusuri node satu per satu.
Digunakan untuk memahami konsep pencarian.
Linear Search adalah algoritma pencarian sederhana yang memeriksa elemen satu per satu dari awal hingga akhir. Algoritma ini tidak membutuhkan data terurut dan dapat digunakan pada berbagai struktur data. Kompleksitas waktu Average Case dan Worst Case adalah $O(n)$, sedangkan Best Case adalah $O(1)$. Linear Search cocok untuk data berukuran kecil atau data yang belum terurut.
Binary search efektif pada data terurut dengan kompleksitas waktu O(log n).
Binary search efektif pada data terurut dengan kompleksitas waktu O(log n).
def proses(data):
# Implementasikan konsep Binary Search Lanjutan
return data
contoh = [3, 1, 2]
print(proses(contoh))Studi kasus algoritma membantu memahami cara menerapkan algoritma untuk menyelesaikan masalah nyata secara sistematis dan efisien.
Studi kasus algoritma adalah contoh permasalahan yang digunakan untuk menganalisis kebutuhan, merancang solusi, memilih struktur data, dan menentukan algoritma yang tepat.
Dalam menyelesaikan sebuah studi kasus, program tidak hanya harus menghasilkan jawaban yang benar, tetapi juga perlu memperhatikan efisiensi waktu dan penggunaan memori.
Contoh studi kasus pada materi ini adalah membuat program untuk mengelola nilai mahasiswa dan menentukan nilai tertinggi, terendah, rata-rata, serta status kelulusan.
Sebuah kelas memiliki beberapa nilai mahasiswa. Buatlah program untuk melakukan hal-hal berikut:
| Komponen | Keterangan |
|---|---|
| Input | Daftar nilai mahasiswa |
| Proses | Perhitungan, pencarian, pengurutan, dan pengecekan kelulusan |
| Output | Rata-rata, nilai maksimum, nilai minimum, data terurut, dan status kelulusan |
| Struktur Data | Array atau List |
Pseudocode digunakan untuk menjelaskan langkah penyelesaian tanpa bergantung pada bahasa pemrograman tertentu.
Mulai
Masukkan daftar nilai
Hitung jumlah seluruh nilai
Hitung rata-rata
Cari nilai terbesar
Cari nilai terkecil
Urutkan daftar nilai
Masukkan nilai yang ingin dicari
Jika nilai ditemukan:
Tampilkan posisi nilai
Jika tidak:
Tampilkan pesan tidak ditemukan
Untuk setiap nilai:
Jika nilai >= 75:
Tampilkan "Lulus"
Jika tidak:
Tampilkan "Tidak Lulus"
Selesaidef analisis_nilai(data, target, batas_lulus=75):
total = sum(data)
rata_rata = total / len(data)
nilai_tertinggi = max(data)
nilai_terendah = min(data)
data_terurut = sorted(data)
posisi_target = []
for index, nilai in enumerate(data):
if nilai == target:
posisi_target.append(index)
status = []
for nilai in data:
if nilai >= batas_lulus:
status.append("Lulus")
else:
status.append("Tidak Lulus")
return {
"rata_rata": rata_rata,
"nilai_tertinggi": nilai_tertinggi,
"nilai_terendah": nilai_terendah,
"data_terurut": data_terurut,
"posisi_target": posisi_target,
"status": status
}
nilai_mahasiswa = [80, 65, 90, 75, 60, 85, 70]
hasil = analisis_nilai(
nilai_mahasiswa,
target=75
)
print("Rata-rata:", hasil["rata_rata"])
print("Nilai tertinggi:", hasil["nilai_tertinggi"])
print("Nilai terendah:", hasil["nilai_terendah"])
print("Data terurut:", hasil["data_terurut"])
print("Posisi target:", hasil["posisi_target"])
print("Status:", hasil["status"])$75$
$90$
$60$
$4$ mahasiswa
Beberapa proses pada studi kasus dapat dilakukan secara manual menggunakan algoritma dasar.
| Kebutuhan | Algoritma yang Digunakan | Kompleksitas |
|---|---|---|
| Menghitung total nilai | Perulangan | $O(n)$ |
| Mencari nilai tertinggi | Linear Scan | $O(n)$ |
| Mencari nilai terendah | Linear Scan | $O(n)$ |
| Mengurutkan data | Selection Sort | $O(n^2)$ |
| Mencari nilai tertentu | Linear Search | $O(n)$ |
Nilai maksimum dan minimum dapat dicari dengan memeriksa setiap elemen satu per satu.
def cari_maksimum_minimum(data):
maksimum = data[0]
minimum = data[0]
for nilai in data[1:]:
if nilai > maksimum:
maksimum = nilai
if nilai < minimum:
minimum = nilai
return maksimum, minimum
data = [80, 65, 90, 75, 60, 85, 70]
maksimum, minimum = cari_maksimum_minimum(data)
print("Maksimum:", maksimum)
print("Minimum:", minimum)| Skenario | Input | Hasil yang Diharapkan |
|---|---|---|
| Data normal | [80, 65, 90] | Rata-rata berhasil dihitung |
| Data kosong | [] | Menampilkan pesan data kosong |
| Target ditemukan | Target 75 | Indeks target ditampilkan |
| Target tidak ditemukan | Target 100 | Pesan tidak ditemukan |
| Nilai batas lulus | Nilai 75 | Status Lulus |
Studi kasus algoritma membantu menerapkan konsep algoritma dan struktur data pada permasalahan nyata. Dalam kasus pengolahan nilai mahasiswa, digunakan perulangan untuk menghitung data, Linear Search untuk pencarian, algoritma sorting untuk pengurutan, serta percabangan untuk menentukan kelulusan. Penyelesaian masalah yang baik harus menghasilkan output yang benar, efisien, dan mampu menangani berbagai kondisi input.
Penugasan UTS dirancang untuk menguji pemahaman mahasiswa terhadap konsep algoritma, struktur data, analisis kompleksitas, serta implementasi program.
Individu
Laporan dan Implementasi Program
Sesuai jadwal UTS
Buatlah sebuah program sederhana yang menerapkan algoritma dan struktur data untuk menyelesaikan permasalahan nyata.
Setiap mahasiswa memilih satu studi kasus, kemudian melakukan analisis masalah, membuat algoritma, menuliskan pseudocode, mengimplementasikan program, dan melakukan pengujian.
| No. | Studi Kasus | Algoritma yang Disarankan | Struktur Data |
|---|---|---|---|
| 1 | Sistem Pengolahan Nilai Mahasiswa | Searching dan Sorting | Array atau List |
| 2 | Sistem Data Buku Perpustakaan | Linear Search atau Binary Search | Array atau List |
| 3 | Sistem Antrian Pelanggan | Queue | Queue |
| 4 | Sistem Riwayat Aktivitas | Stack | Stack |
| 5 | Sistem Data Kontak | Searching dan Sorting | Array atau Linked List |
| 6 | Sistem Rekomendasi Sederhana | Searching dan Filtering | Array atau Dictionary |
Program harus dibuat berdasarkan studi kasus yang dipilih dan memenuhi ketentuan berikut.
| Bagian | Isi Laporan |
|---|---|
| Halaman Judul | Judul tugas, nama, NIM, kelas, dan mata kuliah. |
| BAB I Pendahuluan | Latar belakang, rumusan masalah, dan tujuan. |
| BAB II Analisis Masalah | Deskripsi masalah, input, proses, dan output. |
| BAB III Perancangan | Flowchart, pseudocode, algoritma, dan struktur data. |
| BAB IV Implementasi | Source code dan penjelasan program. |
| BAB V Pengujian | Skenario pengujian dan hasil program. |
| BAB VI Penutup | Kesimpulan dan saran. |
Program digunakan untuk menyimpan dan mengolah nilai mahasiswa. Pengguna dapat menambahkan data, menampilkan data, mencari mahasiswa, mengurutkan nilai, serta menentukan status kelulusan.
Nama mahasiswa, NIM, dan nilai.
Searching, sorting, rata-rata, dan validasi.
Daftar mahasiswa dan status kelulusan.
data_mahasiswa = []
def tambah_mahasiswa(nama, nim, nilai):
mahasiswa = {
"nama": nama,
"nim": nim,
"nilai": nilai
}
data_mahasiswa.append(mahasiswa)
def tampilkan_data():
for mahasiswa in data_mahasiswa:
status = (
"Lulus"
if mahasiswa["nilai"] >= 75
else "Tidak Lulus"
)
print(
mahasiswa["nim"],
mahasiswa["nama"],
mahasiswa["nilai"],
status
)
def cari_mahasiswa(nim):
for mahasiswa in data_mahasiswa:
if mahasiswa["nim"] == nim:
return mahasiswa
return None
def urutkan_nilai():
data_mahasiswa.sort(
key=lambda mahasiswa: mahasiswa["nilai"],
reverse=True
)
tambah_mahasiswa("Andi", "A001", 85)
tambah_mahasiswa("Budi", "A002", 70)
tambah_mahasiswa("Citra", "A003", 90)
urutkan_nilai()
tampilkan_data()
hasil = cari_mahasiswa("A002")
if hasil:
print("Data ditemukan:", hasil)
else:
print("Data tidak ditemukan")Pseudocode berikut menggambarkan alur utama program pengelolaan data mahasiswa.
Mulai
Buat list data mahasiswa
Tampilkan menu:
1. Tambah data
2. Tampilkan data
3. Cari data
4. Urutkan data
5. Hapus data
6. Keluar
Jika pengguna memilih tambah:
Masukkan data mahasiswa
Simpan data
Jika pengguna memilih tampil:
Tampilkan seluruh data
Jika pengguna memilih cari:
Masukkan NIM
Cari NIM pada data
Jika pengguna memilih urutkan:
Urutkan berdasarkan nilai
Jika pengguna memilih hapus:
Masukkan NIM
Hapus data sesuai NIM
Ulangi menu sampai pengguna memilih keluar
Selesai| No. | Skenario | Input | Hasil yang Diharapkan |
|---|---|---|---|
| 1 | Menambahkan data | Data mahasiswa valid | Data berhasil disimpan |
| 2 | Mencari data | NIM terdaftar | Data ditemukan |
| 3 | Mencari data | NIM tidak terdaftar | Data tidak ditemukan |
| 4 | Mengurutkan data | Beberapa data mahasiswa | Data terurut berdasarkan nilai |
| 5 | Validasi nilai | Nilai di luar rentang 0 sampai 100 | Input ditolak |
| 6 | Data kosong | Tidak ada data | Pesan data kosong ditampilkan |
| Komponen | Bobot |
|---|---|
| Analisis masalah | 20% |
| Perancangan algoritma | 20% |
| Implementasi program | 25% |
| Pengujian program | 15% |
| Dokumentasi laporan | 10% |
| Presentasi | 10% |
| Total | 100% |
NIM_Nama_PenugasanUTS.
Penugasan UTS bertujuan mengukur kemampuan mahasiswa dalam menerapkan konsep algoritma dan struktur data pada permasalahan nyata. Tugas harus mencakup analisis masalah, perancangan algoritma, implementasi program, pengujian, dan dokumentasi. Program yang baik tidak hanya menghasilkan output yang benar, tetapi juga memiliki struktur kode yang jelas dan efisien.
Uji pemahaman materi Algoritma dan Struktur Data dari pertemuan pertama sampai pertemuan ketujuh.
15 Soal Pilihan Ganda
Pertemuan 1 sampai 7
30 Menit
Sistem Pengolahan Nilai Mahasiswa menggunakan algoritma searching, sorting, array, perulangan, dan percabangan.
| No. | NIM | Nama | Kelas | Algoritma | Struktur Data | Project | Nilai Akhir | Status | Aksi |
|---|
Tree adalah struktur data non-linear yang menyimpan data dalam bentuk hubungan hierarki antara parent dan child.
Tree atau pohon adalah struktur data non-linear yang terdiri dari kumpulan node. Setiap node dapat memiliki hubungan dengan node lain melalui edge.
Tree digunakan untuk merepresentasikan struktur hierarki, seperti struktur folder, organisasi perusahaan, sistem keluarga, dan struktur menu.
Node paling atas disebut root, sedangkan node yang tidak memiliki child disebut leaf.
A
/ \
B C
/ \ \
D E FNode A
A, B, dan C
D, E, dan F
| Istilah | Pengertian |
|---|---|
| Node | Elemen yang menyimpan data. |
| Root | Node paling atas pada tree. |
| Edge | Hubungan antara dua node. |
| Parent | Node yang memiliki child. |
| Child | Node yang berada di bawah parent. |
| Sibling | Node yang memiliki parent sama. |
| Leaf | Node yang tidak memiliki child. |
| Degree | Jumlah child yang dimiliki sebuah node. |
| Height | Jarak terpanjang dari node ke leaf. |
| Depth | Jarak sebuah node dari root. |
Binary Tree adalah tree yang setiap nodenya memiliki maksimal dua child.
Kedua child tersebut biasanya disebut left child dan right child.
50
/ \
30 70
/ \ / \
20 40 60 80Binary Search Tree atau BST adalah Binary Tree dengan aturan tertentu.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
root = Node(50)
root.left = Node(30)
root.right = Node(70)
root.left.left = Node(20)
root.left.right = Node(40)
root.right.left = Node(60)
root.right.right = Node(80)Traversal adalah proses mengunjungi setiap node pada tree dengan urutan tertentu.
| Traversal | Urutan | Hasil Contoh |
|---|---|---|
| Preorder | Root - Left - Right | 50, 30, 20, 40, 70, 60, 80 |
| Inorder | Left - Root - Right | 20, 30, 40, 50, 60, 70, 80 |
| Postorder | Left - Right - Root | 20, 40, 30, 60, 80, 70, 50 |
| Level Order | Berdasarkan level | 50, 30, 70, 20, 40, 60, 80 |
def inorder(node):
if node is not None:
inorder(node.left)
print(node.value)
inorder(node.right)def preorder(node):
if node is not None:
print(node.value)
preorder(node.left)
preorder(node.right)def postorder(node):
if node is not None:
postorder(node.left)
postorder(node.right)
print(node.value)def search(node, target):
if node is None:
return False
if node.value == target:
return True
if target < node.value:
return search(node.left, target)
return search(node.right, target)
print(search(root, 60))
print(search(root, 100))| Operasi | Average Case | Worst Case |
|---|---|---|
| Pencarian BST | $O(\log n)$ | $O(n)$ |
| Insertion BST | $O(\log n)$ | $O(n)$ |
| Deletion BST | $O(\log n)$ | $O(n)$ |
| Traversal | $O(n)$ | $O(n)$ |
Menyimpan folder dan subfolder.
Menampilkan struktur jabatan.
Membentuk syntax tree.
Mengelola indeks dan pencarian data.
Tree merupakan struktur data non-linear yang digunakan untuk menyimpan data secara hierarkis. Konsep penting pada tree meliputi node, root, parent, child, leaf, edge, height, dan depth. Salah satu jenis tree yang banyak digunakan adalah Binary Search Tree karena mendukung proses pencarian, penambahan, dan penghapusan data secara efisien.
Binary Tree adalah struktur data tree yang setiap nodenya memiliki maksimal dua child, yaitu left child dan right child.
Binary Tree merupakan salah satu jenis tree yang setiap nodenya dapat memiliki paling banyak dua anak.
Anak pertama disebut left child dan anak kedua disebut right child. Sebuah node juga dapat memiliki hanya satu child atau tidak memiliki child sama sekali.
A
/ \
B C
/ \ \
D E F| Komponen | Penjelasan | Contoh |
|---|---|---|
| Root | Node paling atas. | A |
| Left Child | Node anak yang berada di sebelah kiri. | B dari A |
| Right Child | Node anak yang berada di sebelah kanan. | C dari A |
| Leaf | Node yang tidak memiliki anak. | D, E, dan F |
| Subtree | Bagian tree yang dianggap sebagai tree kecil. | Subtree B |
Setiap node memiliki tepat nol atau dua child. Tidak ada node yang hanya memiliki satu child.
A
/ \
B C
/ \
D ESemua level terisi penuh, kecuali level terakhir. Pengisian dilakukan dari kiri ke kanan.
A
/ \
B C
/ \
D ESemua node internal memiliki dua child dan seluruh leaf berada pada level yang sama.
A
/ \
B C
/ \ / \
D E F GTree yang setiap node-nya hanya memiliki satu child sehingga menyerupai linked list.
A
\
B
\
C
\
Dclass Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
root = Node("A")
root.left = Node("B")
root.right = Node("C")
root.left.left = Node("D")
root.left.right = Node("E")
root.right.right = Node("F")Traversal adalah proses mengunjungi semua node dalam Binary Tree. Terdapat tiga traversal rekursif utama.
| Traversal | Urutan Kunjungan | Contoh Hasil |
|---|---|---|
| Preorder | Root - Left - Right | A, B, D, E, C, F |
| Inorder | Left - Root - Right | D, B, E, A, C, F |
| Postorder | Left - Right - Root | D, E, B, F, C, A |
def preorder(node):
if node is not None:
print(node.data)
preorder(node.left)
preorder(node.right)def inorder(node):
if node is not None:
inorder(node.left)
print(node.data)
inorder(node.right)def postorder(node):
if node is not None:
postorder(node.left)
postorder(node.right)
print(node.data)root = Node("A")
root.left = Node("B")
root.right = Node("C")
root.left.left = Node("D")
root.left.right = Node("E")
root.right.right = Node("F")
print("Preorder:")
preorder(root)
print("Inorder:")
inorder(root)
print("Postorder:")
postorder(root)Tinggi tree adalah jumlah edge pada jalur terpanjang dari root menuju leaf.
Pada implementasi rekursif, tinggi tree dihitung dengan mencari tinggi subtree kiri dan subtree kanan, kemudian mengambil nilai terbesar.
def height(node):
if node is None:
return -1
left_height = height(node.left)
right_height = height(node.right)
return 1 + max(
left_height,
right_height
)
print("Tinggi tree:", height(root))| Operasi | Kompleksitas Waktu | Kompleksitas Ruang |
|---|---|---|
| Preorder | $O(n)$ | $O(h)$ |
| Inorder | $O(n)$ | $O(h)$ |
| Postorder | $O(n)$ | $O(h)$ |
| Menghitung tinggi | $O(n)$ | $O(h)$ |
Dengan $n$ sebagai jumlah node dan $h$ sebagai tinggi tree, setiap node dikunjungi satu kali dalam proses traversal.
Menyimpan folder dan subfolder.
Menggambarkan hubungan jabatan.
Membentuk syntax tree.
Membantu proses indeks dan pencarian data.
Binary Tree adalah struktur data hierarkis yang setiap nodenya memiliki maksimal dua child. Pemahaman Binary Tree mencakup struktur node, jenis-jenis tree, traversal preorder, inorder, postorder, serta perhitungan tinggi tree. Traversal memiliki kompleksitas waktu $O(n)$ karena setiap node dikunjungi satu kali.
Tree traversal adalah proses mengunjungi setiap node pada tree dengan urutan tertentu.
Traversal digunakan untuk membaca, mencari, mencetak, atau memproses seluruh node pada struktur tree.
Pada Binary Tree terdapat tiga traversal rekursif utama, yaitu Preorder, Inorder, dan Postorder. Selain itu terdapat Level Order Traversal yang mengunjungi node berdasarkan level.
A
/ \
B C
/ \ \
D E F| Jenis | Urutan | Hasil Traversal |
|---|---|---|
| Preorder | Root - Left - Right | A, B, D, E, C, F |
| Inorder | Left - Root - Right | D, B, E, A, C, F |
| Postorder | Left - Right - Root | D, E, B, F, C, A |
| Level Order | Level demi level | A, B, C, D, E, F |
Pada Preorder, node root dikunjungi terlebih dahulu, kemudian subtree kiri, lalu subtree kanan.
def preorder(node):
if node is not None:
print(node.data, end=" ")
preorder(node.left)
preorder(node.right)Pada Inorder, subtree kiri dikunjungi terlebih dahulu, kemudian root, lalu subtree kanan.
def inorder(node):
if node is not None:
inorder(node.left)
print(node.data, end=" ")
inorder(node.right)Pada Postorder, subtree kiri dikunjungi terlebih dahulu, kemudian subtree kanan, dan root dikunjungi terakhir.
def postorder(node):
if node is not None:
postorder(node.left)
postorder(node.right)
print(node.data, end=" ")Level Order mengunjungi node berdasarkan tingkat atau level. Traversal ini biasanya menggunakan struktur data Queue.
from collections import deque
def level_order(root):
if root is None:
return
queue = deque([root])
while queue:
node = queue.popleft()
print(node.data, end=" ")
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)from collections import deque
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def preorder(node):
if node is not None:
print(node.data, end=" ")
preorder(node.left)
preorder(node.right)
def inorder(node):
if node is not None:
inorder(node.left)
print(node.data, end=" ")
inorder(node.right)
def postorder(node):
if node is not None:
postorder(node.left)
postorder(node.right)
print(node.data, end=" ")
def level_order(root):
if root is None:
return
queue = deque([root])
while queue:
node = queue.popleft()
print(node.data, end=" ")
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
root = Node("A")
root.left = Node("B")
root.right = Node("C")
root.left.left = Node("D")
root.left.right = Node("E")
root.right.right = Node("F")
print("Preorder:")
preorder(root)
print("\\nInorder:")
inorder(root)
print("\\nPostorder:")
postorder(root)
print("\\nLevel Order:")
level_order(root)Preorder:
A B D E C F
Inorder:
D B E A C F
Postorder:
D E B F C A
Level Order:
A B C D E F| Traversal | Kelebihan | Contoh Penggunaan |
|---|---|---|
| Preorder | Memproses root sebelum child. | Menyalin struktur tree. |
| Inorder | Menghasilkan data terurut pada BST. | Menampilkan data terurut. |
| Postorder | Memproses child sebelum root. | Menghapus tree. |
| Level Order | Memproses data berdasarkan level. | Pencarian berdasarkan jarak level. |
| Operasi | Kompleksitas Waktu | Kompleksitas Ruang |
|---|---|---|
| Preorder | $O(n)$ | $O(h)$ |
| Inorder | $O(n)$ | $O(h)$ |
| Postorder | $O(n)$ | $O(h)$ |
| Level Order | $O(n)$ | $O(n)$ |
Keterangan: $n$ adalah jumlah node dan $h$ adalah tinggi tree.
Perhatikan Binary Tree berikut:
50
/ \
30 70
/ \ / \
20 40 60 80Tree Traversal digunakan untuk mengunjungi seluruh node pada Binary Tree. Preorder menggunakan urutan Root, Left, Right. Inorder menggunakan urutan Left, Root, Right. Postorder menggunakan urutan Left, Right, Root, sedangkan Level Order memproses node berdasarkan level dengan bantuan Queue. Setiap traversal memiliki kompleksitas waktu $O(n)$.
Tiga metode traversal untuk mengunjungi seluruh node pada Binary Tree.
A
/ \
B C
/ \ \
D E FPada Preorder, root dikunjungi terlebih dahulu, kemudian subtree kiri, dan terakhir subtree kanan.
A, B, D, E, C, F
def preorder(node):
if node is not None:
print(node.data, end=" ")
preorder(node.left)
preorder(node.right)Pada Inorder, subtree kiri dikunjungi terlebih dahulu, kemudian root, dan terakhir subtree kanan.
D, B, E, A, C, F
def inorder(node):
if node is not None:
inorder(node.left)
print(node.data, end=" ")
inorder(node.right)Pada Postorder, subtree kiri dikunjungi terlebih dahulu, dilanjutkan subtree kanan, kemudian root dikunjungi terakhir.
D, E, B, F, C, A
def postorder(node):
if node is not None:
postorder(node.left)
postorder(node.right)
print(node.data, end=" ")| Traversal | Urutan | Hasil | Kegunaan |
|---|---|---|---|
| Preorder | Root - Left - Right | A, B, D, E, C, F | Menyalin struktur tree |
| Inorder | Left - Root - Right | D, B, E, A, C, F | Menampilkan BST terurut |
| Postorder | Left - Right - Root | D, E, B, F, C, A | Menghapus tree |
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def preorder(node, result):
if node is not None:
result.append(node.data)
preorder(node.left, result)
preorder(node.right, result)
def inorder(node, result):
if node is not None:
inorder(node.left, result)
result.append(node.data)
inorder(node.right, result)
def postorder(node, result):
if node is not None:
postorder(node.left, result)
postorder(node.right, result)
result.append(node.data)
root = Node("A")
root.left = Node("B")
root.right = Node("C")
root.left.left = Node("D")
root.left.right = Node("E")
root.right.right = Node("F")
preorder_result = []
inorder_result = []
postorder_result = []
preorder(root, preorder_result)
inorder(root, inorder_result)
postorder(root, postorder_result)
print("Preorder:", preorder_result)
print("Inorder:", inorder_result)
print("Postorder:", postorder_result)Preorder: ['A', 'B', 'D', 'E', 'C', 'F']
Inorder: ['D', 'B', 'E', 'A', 'C', 'F']
Postorder: ['D', 'E', 'B', 'F', 'C', 'A']Tentukan hasil traversal dari Binary Search Tree berikut:
50
/ \
30 70
/ \ / \
20 40 60 80Preorder mengunjungi root sebelum subtree, Inorder mengunjungi root di antara subtree kiri dan kanan, sedangkan Postorder mengunjungi root setelah kedua subtree selesai diproses. Ketiga metode tersebut memiliki kompleksitas waktu $O(n)$.
Heap adalah struktur data berbentuk Complete Binary Tree yang digunakan untuk mengatur elemen berdasarkan prioritas.
Heap adalah struktur data berbentuk Complete Binary Tree yang memenuhi aturan hubungan antara parent dan child.
Heap biasanya digunakan pada Priority Queue, Heap Sort, sistem penjadwalan, dan algoritma Graph seperti Dijkstra serta Prim.
Semua level penuh, kecuali level terakhir yang diisi dari kiri ke kanan.
Parent harus memenuhi aturan nilai tertentu terhadap child.
Heap dapat disimpan secara efisien menggunakan array.
Pada Min Heap, nilai parent harus lebih kecil atau sama dengan nilai child.
10
/ \
20 15
/ \ /
30 40 25Pada Max Heap, nilai parent harus lebih besar atau sama dengan nilai child.
50
/ \
40 45
/ \ /
20 30 35 50
/ \
30 40
/ \ /
10 20 35
Array:
[50, 30, 40, 10, 20, 35]Jika index parent adalah $i$, maka posisi child dapat dihitung dengan rumus berikut:
| Operasi | Penjelasan | Kompleksitas |
|---|---|---|
| Insert | Menambahkan elemen baru ke heap. | $O(\log n)$ |
| Extract Root | Menghapus root dari heap. | $O(\log n)$ |
| Peek | Melihat nilai root tanpa menghapusnya. | $O(1)$ |
| Heapify | Memperbaiki struktur heap. | $O(\log n)$ |
| Build Heap | Membentuk heap dari array. | $O(n)$ |
import heapq
min_heap = []
heapq.heappush(min_heap, 30)
heapq.heappush(min_heap, 10)
heapq.heappush(min_heap, 20)
heapq.heappush(min_heap, 5)
print("Heap:", min_heap)
print("Nilai terkecil:", min_heap[0])
nilai = heapq.heappop(min_heap)
print("Nilai yang dihapus:", nilai)
print("Heap setelah pop:", min_heap)import heapq
max_heap = []
heapq.heappush(max_heap, -30)
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -20)
heapq.heappush(max_heap, -5)
nilai_terbesar = -heapq.heappop(max_heap)
print("Nilai terbesar:", nilai_terbesar)def heapify_max(data, n, i):
terbesar = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and data[left] > data[terbesar]:
terbesar = left
if right < n and data[right] > data[terbesar]:
terbesar = right
if terbesar != i:
data[i], data[terbesar] = \
data[terbesar], data[i]
heapify_max(data, n, terbesar)
data = [10, 30, 20, 5, 40, 35]
n = len(data)
for i in range(n // 2 - 1, -1, -1):
heapify_max(data, n, i)
print(data)Heap Sort adalah algoritma sorting yang menggunakan struktur data Heap. Untuk sorting menaik, biasanya digunakan Max Heap.
def heap_sort(data):
n = len(data)
def heapify(data, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and data[left] > data[largest]:
largest = left
if right < n and data[right] > data[largest]:
largest = right
if largest != i:
data[i], data[largest] = \
data[largest], data[i]
heapify(data, n, largest)
for i in range(n // 2 - 1, -1, -1):
heapify(data, n, i)
for i in range(n - 1, 0, -1):
data[0], data[i] = \
data[i], data[0]
heapify(data, i, 0)
return data
angka = [40, 10, 30, 50, 20]
print(heap_sort(angka))[10, 20, 30, 40, 50]Memproses data berdasarkan prioritas.
Mengurutkan data secara efisien.
Mencari jalur terpendek.
Mengatur proses berdasarkan prioritas.
Heap adalah Complete Binary Tree yang memiliki aturan prioritas antara parent dan child. Min Heap menempatkan nilai terkecil pada root, sedangkan Max Heap menempatkan nilai terbesar pada root. Heap digunakan pada Priority Queue, Heap Sort, sistem penjadwalan, dan algoritma pencarian jalur terpendek.
Min Heap adalah Complete Binary Tree yang memiliki nilai parent lebih kecil atau sama dengan nilai child.
Min Heap adalah struktur data berbentuk Complete Binary Tree yang menempatkan nilai terkecil pada root.
Setiap parent pada Min Heap harus memiliki nilai yang lebih kecil atau sama dengan child-nya.
5
/ \
10 15
/ \ / \
20 30 25 40Nilai 5
Nilainya lebih kecil dari child.
20, 30, 25, dan 40
Min Heap dapat disimpan dalam array tanpa menggunakan pointer secara eksplisit.
Index:
0 1 2 3 4 5 6
Data:
[5, 10, 15, 20, 30, 25, 40]Jika posisi parent berada pada index $i$, maka posisi child dapat ditentukan menggunakan rumus berikut:
| Elemen | Rumus |
|---|---|
| Left Child | $2i + 1$ |
| Right Child | $2i + 2$ |
| Parent | $\left\lfloor \frac{i - 1}{2} \right\rfloor$ |
Insert digunakan untuk menambahkan nilai baru ke dalam Min Heap.
Sebelum insert:
[5, 10, 15, 20, 30, 25, 40]
Insert nilai 3:
[5, 10, 15, 20, 30, 25, 40, 3]
Setelah sift up:
[3, 5, 15, 10, 30, 25, 40, 20]Extract Minimum digunakan untuk mengambil sekaligus menghapus nilai terkecil yang berada pada root.
Sebelum extract:
[5, 10, 15, 20, 30, 25, 40]
Nilai yang dihapus: 5
Setelah sift down:
[10, 20, 15, 40, 30, 25]import heapq
min_heap = []
heapq.heappush(min_heap, 20)
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 15)
heapq.heappush(min_heap, 10)
heapq.heappush(min_heap, 30)
print("Isi Min Heap:", min_heap)
print("Nilai terkecil:", min_heap[0])
nilai = heapq.heappop(min_heap)
print("Nilai yang dihapus:", nilai)
print("Heap setelah penghapusan:", min_heap)class MinHeap:
def __init__(self):
self.heap = []
def insert(self, value):
self.heap.append(value)
self.sift_up(
len(self.heap) - 1
)
def sift_up(self, index):
while index > 0:
parent = (index - 1) // 2
if self.heap[parent] <= self.heap[index]:
break
self.heap[parent], self.heap[index] = \
self.heap[index], self.heap[parent]
index = parent
def peek(self):
if len(self.heap) == 0:
return None
return self.heap[0]
def extract_min(self):
if len(self.heap) == 0:
return None
if len(self.heap) == 1:
return self.heap.pop()
minimum = self.heap[0]
self.heap[0] = self.heap.pop()
self.sift_down(0)
return minimum
def sift_down(self, index):
size = len(self.heap)
while True:
smallest = index
left = 2 * index + 1
right = 2 * index + 2
if left < size and \
self.heap[left] < self.heap[smallest]:
smallest = left
if right < size and \
self.heap[right] < self.heap[smallest]:
smallest = right
if smallest == index:
break
self.heap[index], self.heap[smallest] = \
self.heap[smallest], self.heap[index]
index = smallest
min_heap = MinHeap()
min_heap.insert(30)
min_heap.insert(10)
min_heap.insert(20)
min_heap.insert(5)
print(min_heap.heap)
print("Minimum:", min_heap.peek())
print("Extract:", min_heap.extract_min())
print(min_heap.heap)[5, 10, 20, 30]
Minimum: 5
Extract: 5
[10, 30, 20]| Operasi | Kompleksitas | Keterangan |
|---|---|---|
| Peek | $O(1)$ | Mengakses root. |
| Insert | $O(\log n)$ | Menggunakan sift up. |
| Extract Minimum | $O(\log n)$ | Menggunakan sift down. |
| Build Heap | $O(n)$ | Membentuk heap dari array. |
Sebuah rumah sakit ingin melayani pasien berdasarkan tingkat urgensi. Semakin kecil angka prioritas, semakin tinggi prioritas pasien.
| Pasien | Prioritas |
|---|---|
| Pasien A | 3 |
| Pasien B | 1 |
| Pasien C | 2 |
Dengan Min Heap, pasien yang memiliki prioritas 1 akan diproses terlebih dahulu, kemudian prioritas 2, lalu prioritas 3.
Min Heap adalah Complete Binary Tree yang menyimpan nilai terkecil pada root. Operasi utama Min Heap adalah insert, peek, extract minimum, sift up, dan sift down. Insert dan extract minimum memiliki kompleksitas $O(\log n)$, sedangkan peek memiliki kompleksitas $O(1)$.
Max Heap adalah Complete Binary Tree yang menempatkan nilai terbesar pada root.
Max Heap adalah struktur data berbentuk Complete Binary Tree yang memiliki aturan bahwa nilai parent harus lebih besar atau sama dengan nilai child.
Karena nilai terbesar selalu berada di root, Max Heap cocok digunakan untuk sistem prioritas dengan nilai terbesar diproses terlebih dahulu.
90
/ \
70 80
/ \ / \
40 60 30 50Nilai 90
Selalu lebih besar dari child.
40, 60, 30, dan 50
Max Heap dapat disimpan dalam array berdasarkan urutan level dari tree.
Index:
0 1 2 3 4 5 6
Data:
[90, 70, 80, 40, 60, 30, 50]| Elemen | Rumus |
|---|---|
| Left Child | $2i + 1$ |
| Right Child | $2i + 2$ |
| Parent | $\left\lfloor \frac{i - 1}{2} \right\rfloor$ |
Insert digunakan untuk menambahkan elemen baru. Setelah elemen ditambahkan, dilakukan proses sift up.
Sebelum insert:
[90, 70, 80, 40, 60, 30, 50]
Insert nilai 100:
[90, 70, 80, 40, 60, 30, 50, 100]
Setelah sift up:
[100, 90, 80, 70, 60, 30, 50, 40]Extract Maximum digunakan untuk mengambil dan menghapus nilai terbesar pada root.
Sebelum extract:
[90, 70, 80, 40, 60, 30, 50]
Nilai yang dihapus: 90
Setelah sift down:
[80, 70, 50, 40, 60, 30]class MaxHeap:
def __init__(self):
self.heap = []
def insert(self, value):
self.heap.append(value)
self.sift_up(
len(self.heap) - 1
)
def sift_up(self, index):
while index > 0:
parent = (index - 1) // 2
if self.heap[parent] >= self.heap[index]:
break
self.heap[parent], self.heap[index] = \
self.heap[index], self.heap[parent]
index = parent
def peek(self):
if len(self.heap) == 0:
return None
return self.heap[0]
def extract_max(self):
if len(self.heap) == 0:
return None
if len(self.heap) == 1:
return self.heap.pop()
maximum = self.heap[0]
self.heap[0] = self.heap.pop()
self.sift_down(0)
return maximum
def sift_down(self, index):
size = len(self.heap)
while True:
largest = index
left = 2 * index + 1
right = 2 * index + 2
if left < size and \
self.heap[left] > self.heap[largest]:
largest = left
if right < size and \
self.heap[right] > self.heap[largest]:
largest = right
if largest == index:
break
self.heap[index], self.heap[largest] = \
self.heap[largest], self.heap[index]
index = largest
max_heap = MaxHeap()
max_heap.insert(50)
max_heap.insert(30)
max_heap.insert(70)
max_heap.insert(90)
max_heap.insert(40)
print("Isi Max Heap:", max_heap.heap)
print("Nilai terbesar:", max_heap.peek())
print("Extract:", max_heap.extract_max())
print("Heap setelah extract:", max_heap.heap)import heapq
max_heap = []
heapq.heappush(max_heap, -50)
heapq.heappush(max_heap, -30)
heapq.heappush(max_heap, -70)
heapq.heappush(max_heap, -90)
nilai_terbesar = -max_heap[0]
print("Nilai terbesar:", nilai_terbesar)
nilai = -heapq.heappop(max_heap)
print("Data yang dihapus:", nilai)| Operasi | Kompleksitas | Proses |
|---|---|---|
| Peek Maximum | $O(1)$ | Mengakses root. |
| Insert | $O(\log n)$ | Sift up. |
| Extract Maximum | $O(\log n)$ | Sift down. |
| Build Heap | $O(n)$ | Membangun heap dari array. |
Max Heap dapat digunakan untuk mengatur proses berdasarkan nilai prioritas terbesar.
| Proses | Prioritas |
|---|---|
| Proses A | 3 |
| Proses B | 10 |
| Proses C | 7 |
Dengan Max Heap, Proses B dengan prioritas 10 akan diproses terlebih dahulu.
Max Heap adalah Complete Binary Tree yang menempatkan nilai terbesar pada root. Operasi insert menggunakan sift up, sedangkan extract maximum menggunakan sift down. Peek memiliki kompleksitas $O(1)$, sementara insert dan extract maximum memiliki kompleksitas $O(\log n)$.
Operasi utama pada Heap meliputi insert, peek, extract, heapify, build heap, dan heap sort.
Operasi Heap adalah proses untuk menambah, menghapus, mengambil, atau memperbaiki data pada struktur Heap.
Setiap operasi harus tetap menjaga dua aturan Heap, yaitu bentuk Complete Binary Tree dan Heap Property.
| Operasi | Fungsi | Kompleksitas |
|---|---|---|
| Insert | Menambahkan elemen baru. | $O(\log n)$ |
| Peek | Melihat root tanpa menghapus. | $O(1)$ |
| Extract | Menghapus root dari Heap. | $O(\log n)$ |
| Heapify | Memperbaiki struktur Heap. | $O(\log n)$ |
| Build Heap | Membuat Heap dari array. | $O(n)$ |
| Heap Sort | Mengurutkan data menggunakan Heap. | $O(n \log n)$ |
Insert digunakan untuk menambahkan elemen baru ke dalam Heap.
Heap awal:
[50, 30, 40, 10, 20]
Tambahkan nilai 60:
[50, 30, 40, 10, 20, 60]
Bandingkan 60 dengan parent 40:
[50, 30, 60, 10, 20, 40]
Bandingkan 60 dengan parent 50:
[60, 30, 50, 10, 20, 40]Peek digunakan untuk melihat nilai root tanpa menghapusnya.
Pada Min Heap, Peek menghasilkan nilai terkecil. Pada Max Heap, Peek menghasilkan nilai terbesar.
Max Heap:
[90, 70, 80, 40, 60]
Peek:
90Extract digunakan untuk mengambil dan menghapus root dari Heap.
Max Heap awal:
[90, 70, 80, 40, 60, 30]
Hapus root 90:
[30, 70, 80, 40, 60]
Setelah sift down:
[80, 70, 30, 40, 60]
Hasil akhir:
[80, 70, 60, 40, 30]Sift Up adalah proses menggeser elemen ke atas ketika elemen baru melanggar aturan Heap terhadap parent-nya.
Sift Up biasanya digunakan setelah operasi Insert.
def sift_up(heap, index):
while index > 0:
parent = (index - 1) // 2
if heap[parent] >= heap[index]:
break
heap[parent], heap[index] = \
heap[index], heap[parent]
index = parentSift Down adalah proses menggeser elemen ke bawah ketika elemen pada root melanggar aturan Heap.
Sift Down biasanya digunakan setelah operasi Extract.
def sift_down(heap, index):
size = len(heap)
while True:
largest = index
left = 2 * index + 1
right = 2 * index + 2
if left < size and \
heap[left] > heap[largest]:
largest = left
if right < size and \
heap[right] > heap[largest]:
largest = right
if largest == index:
break
heap[index], heap[largest] = \
heap[largest], heap[index]
index = largestHeapify adalah proses mengubah array biasa menjadi struktur Heap yang valid.
Proses ini dilakukan dengan memeriksa node internal dari posisi paling bawah menuju root.
def build_max_heap(data):
n = len(data)
for i in range(n // 2 - 1, -1, -1):
heapify(data, n, i)
return dataclass MaxHeap:
def __init__(self):
self.heap = []
def peek(self):
if not self.heap:
return None
return self.heap[0]
def insert(self, value):
self.heap.append(value)
self.sift_up(
len(self.heap) - 1
)
def sift_up(self, index):
while index > 0:
parent = (index - 1) // 2
if self.heap[parent] >= self.heap[index]:
break
self.heap[parent], self.heap[index] = \
self.heap[index], self.heap[parent]
index = parent
def extract_max(self):
if not self.heap:
return None
if len(self.heap) == 1:
return self.heap.pop()
maximum = self.heap[0]
self.heap[0] = self.heap.pop()
self.sift_down(0)
return maximum
def sift_down(self, index):
size = len(self.heap)
while True:
largest = index
left = 2 * index + 1
right = 2 * index + 2
if left < size and \
self.heap[left] > self.heap[largest]:
largest = left
if right < size and \
self.heap[right] > self.heap[largest]:
largest = right
if largest == index:
break
self.heap[index], self.heap[largest] = \
self.heap[largest], self.heap[index]
index = largest
heap = MaxHeap()
heap.insert(40)
heap.insert(20)
heap.insert(70)
heap.insert(10)
heap.insert(90)
print("Heap:", heap.heap)
print("Peek:", heap.peek())
print("Extract:", heap.extract_max())
print("Setelah extract:", heap.heap)Heap: [90, 70, 40, 10, 20]
Peek: 90
Extract: 90
Setelah extract: [70, 20, 40, 10]Sebuah sistem memiliki beberapa proses dengan nilai prioritas. Proses dengan prioritas tertinggi harus dijalankan terlebih dahulu.
| Proses | Prioritas |
|---|---|
| Proses A | 5 |
| Proses B | 10 |
| Proses C | 7 |
Dengan Max Heap, proses yang memiliki prioritas 10 akan diproses pertama.
Operasi pada Heap digunakan untuk mengelola data berdasarkan prioritas. Insert menambahkan data dengan bantuan Sift Up, sedangkan Extract menghapus root dengan bantuan Sift Down. Peek digunakan untuk membaca root, dan Heapify digunakan untuk membentuk atau memperbaiki struktur Heap. Operasi Insert dan Extract memiliki kompleksitas $O(\log n)$.
Priority Queue adalah struktur data Queue yang memproses data berdasarkan tingkat prioritas, bukan berdasarkan urutan masuk.
Pada Queue biasa, data yang masuk terlebih dahulu akan diproses terlebih dahulu menggunakan konsep FIFO.
Pada Priority Queue, data diproses berdasarkan prioritas. Data dengan prioritas lebih tinggi akan diproses terlebih dahulu meskipun datang belakangan.
| Jenis | Dasar Pemrosesan | Contoh Urutan |
|---|---|---|
| Queue Biasa | Urutan kedatangan | A, B, C |
| Min Priority Queue | Nilai prioritas terkecil | Prioritas 1, 2, 3 |
| Max Priority Queue | Nilai prioritas terbesar | Prioritas 10, 7, 5 |
Elemen dengan angka prioritas paling kecil diproses terlebih dahulu.
Pasien A: Prioritas 3
Pasien B: Prioritas 1
Pasien C: Prioritas 2
Urutan:
Pasien B
Pasien C
Pasien AElemen dengan angka prioritas paling besar diproses terlebih dahulu.
Proses A: Prioritas 5
Proses B: Prioritas 10
Proses C: Prioritas 7
Urutan:
Proses B
Proses C
Proses A| Operasi | Fungsi | Kompleksitas |
|---|---|---|
| Enqueue | Menambahkan data ke Priority Queue. | $O(\log n)$ |
| Peek | Melihat data prioritas tertinggi. | $O(1)$ |
| Dequeue | Menghapus data prioritas tertinggi. | $O(\log n)$ |
| Is Empty | Memeriksa apakah Queue kosong. | $O(1)$ |
import heapq
priority_queue = []
heapq.heappush(
priority_queue,
(3, "Pasien A")
)
heapq.heappush(
priority_queue,
(1, "Pasien B")
)
heapq.heappush(
priority_queue,
(2, "Pasien C")
)
while priority_queue:
priority, name = heapq.heappop(
priority_queue
)
print(
name,
"dengan prioritas",
priority
)Pasien B dengan prioritas 1
Pasien C dengan prioritas 2
Pasien A dengan prioritas 3class PriorityQueue:
def __init__(self):
self.data = []
def enqueue(self, priority, value):
self.data.append(
(priority, value)
)
self.data.sort(
key=lambda item: item[0]
)
def dequeue(self):
if len(self.data) == 0:
return None
return self.data.pop(0)
def peek(self):
if len(self.data) == 0:
return None
return self.data[0]
def is_empty(self):
return len(self.data) == 0
queue = PriorityQueue()
queue.enqueue(3, "Pasien A")
queue.enqueue(1, "Pasien B")
queue.enqueue(2, "Pasien C")
while not queue.is_empty():
print(queue.dequeue())Pasien darurat diproses lebih dahulu.
Dokumen prioritas dicetak lebih dahulu.
Proses dengan prioritas tinggi dijalankan terlebih dahulu.
heapq.
Priority Queue adalah struktur data yang memproses elemen berdasarkan prioritas. Min Priority Queue menggunakan nilai terkecil sebagai prioritas tertinggi, sedangkan Max Priority Queue menggunakan nilai terbesar. Heap digunakan karena operasi enqueue dan dequeue dapat dilakukan dengan kompleksitas $O(\log n)$.
Binary Search Tree atau BST adalah Binary Tree yang menyimpan data berdasarkan aturan nilai kiri lebih kecil dan nilai kanan lebih besar.
Binary Search Tree merupakan struktur data berbentuk Binary Tree yang digunakan untuk menyimpan data secara terurut.
Setiap node pada BST memiliki aturan bahwa semua nilai pada subtree kiri lebih kecil dari node, sedangkan semua nilai pada subtree kanan lebih besar dari node.
50
/ \
30 70
/ \ / \
20 40 60 80Semua data di sebelah kiri 50 lebih kecil, sedangkan semua data di sebelah kanan 50 lebih besar.
Berisi nilai yang lebih kecil dari parent.
Menyimpan satu nilai dan dua kemungkinan child.
Berisi nilai yang lebih besar dari parent.
| Operasi | Fungsi | Average Case | Worst Case |
|---|---|---|---|
| Search | Mencari nilai pada BST. | $O(\log n)$ | $O(n)$ |
| Insert | Menambahkan node baru. | $O(\log n)$ | $O(n)$ |
| Delete | Menghapus node. | $O(\log n)$ | $O(n)$ |
| Traversal | Mengunjungi semua node. | $O(n)$ | $O(n)$ |
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = NoneOperasi Insert digunakan untuk menambahkan nilai baru ke dalam BST.
def insert(node, value):
if node is None:
return Node(value)
if value < node.value:
node.left = insert(node.left, value)
elif value > node.value:
node.right = insert(node.right, value)
return nodePencarian BST lebih cepat dibandingkan pencarian linear jika tree berada dalam kondisi seimbang.
def search(node, target):
if node is None:
return False
if node.value == target:
return True
if target < node.value:
return search(node.left, target)
return search(node.right, target)Penghapusan node pada BST memiliki tiga kondisi.
| Kondisi | Tindakan |
|---|---|
| Node tidak memiliki child | Node langsung dihapus. |
| Node memiliki satu child | Child menggantikan posisi node. |
| Node memiliki dua child | Diganti dengan inorder successor atau inorder predecessor. |
def find_min(node):
current = node
while current.left is not None:
current = current.left
return current
def delete(node, value):
if node is None:
return node
if value < node.value:
node.left = delete(node.left, value)
elif value > node.value:
node.right = delete(node.right, value)
else:
if node.left is None:
return node.right
if node.right is None:
return node.left
successor = find_min(node.right)
node.value = successor.value
node.right = delete(
node.right,
successor.value
)
return nodeInorder Traversal pada BST menghasilkan data dalam urutan menaik.
def inorder(node):
if node is not None:
inorder(node.left)
print(node.value, end=" ")
inorder(node.right)
Hasil:
20 30 40 50 60 70 80class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(node, value):
if node is None:
return Node(value)
if value < node.value:
node.left = insert(node.left, value)
elif value > node.value:
node.right = insert(node.right, value)
return node
def search(node, target):
if node is None:
return False
if node.value == target:
return True
if target < node.value:
return search(node.left, target)
return search(node.right, target)
def inorder(node):
if node is not None:
inorder(node.left)
print(node.value, end=" ")
inorder(node.right)
root = None
data = [50, 30, 70, 20, 40, 60, 80]
for value in data:
root = insert(root, value)
print("Inorder:")
inorder(root)
print("\\nCari 60:", search(root, 60))
print("Cari 100:", search(root, 100))Inorder:
20 30 40 50 60 70 80
Cari 60: True
Cari 100: FalseBinary Search Tree adalah struktur data yang menyimpan nilai lebih kecil pada subtree kiri dan nilai lebih besar pada subtree kanan. Operasi utama BST adalah search, insert, delete, dan traversal. Pada kondisi seimbang, operasi BST memiliki kompleksitas $O(\log n)$, tetapi pada kondisi terburuk dapat mencapai $O(n)$.
Algoritma pencarian pada BST memanfaatkan aturan nilai kiri lebih kecil dan nilai kanan lebih besar.
Pencarian pada Binary Search Tree dilakukan dengan membandingkan nilai target dengan nilai pada node saat ini.
None, data tidak ditemukan.
50
/ \
30 70
/ \ / \
20 40 60 80Pada contoh ini, nilai 60 berada di subtree kanan karena nilainya lebih besar dari 50 dan lebih kecil dari 70.
| Langkah | Node Saat Ini | Perbandingan | Arah |
|---|---|---|---|
| 1 | 50 | 60 lebih besar dari 50 | Ke kanan |
| 2 | 70 | 60 lebih kecil dari 70 | Ke kiri |
| 3 | 60 | 60 sama dengan 60 | Ditemukan |
def search_recursive(node, target):
if node is None:
return False
if node.value == target:
return True
if target < node.value:
return search_recursive(
node.left,
target
)
return search_recursive(
node.right,
target
)def search_iterative(root, target):
current = root
while current is not None:
if current.value == target:
return True
if target < current.value:
current = current.left
else:
current = current.right
return Falseclass Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(node, value):
if node is None:
return Node(value)
if value < node.value:
node.left = insert(node.left, value)
elif value > node.value:
node.right = insert(node.right, value)
return node
def search(node, target):
if node is None:
return False
if node.value == target:
return True
if target < node.value:
return search(node.left, target)
return search(node.right, target)
root = None
data = [50, 30, 70, 20, 40, 60, 80]
for value in data:
root = insert(root, value)
target = 60
if search(root, target):
print(target, "ditemukan")
else:
print(target, "tidak ditemukan")
target = 100
if search(root, target):
print(target, "ditemukan")
else:
print(target, "tidak ditemukan")60 ditemukan
100 tidak ditemukan| Metode | Kelebihan | Kekurangan |
|---|---|---|
| Rekursif | Kode lebih singkat dan mudah dipahami. | Menggunakan call stack tambahan. |
| Iteratif | Lebih hemat penggunaan call stack. | Kode sedikit lebih panjang. |
| Kondisi Tree | Kompleksitas |
|---|---|
| Tree seimbang | $O(\log n)$ |
| Tree miring | $O(n)$ |
| Tree kosong | $O(1)$ |
Kinerja pencarian sangat bergantung pada tinggi tree. Semakin rendah tinggi tree, semakin cepat proses pencarian.
Gunakan BST berikut:
50
/ \
30 70
/ \ / \
20 40 60 80Pencarian pada BST dilakukan dengan membandingkan target terhadap nilai node. Jika target lebih kecil, pencarian bergerak ke kiri, sedangkan jika target lebih besar, pencarian bergerak ke kanan. Pada tree seimbang, kompleksitas pencarian adalah $O(\log n)$, sedangkan pada tree miring kompleksitasnya dapat menjadi $O(n)$.
Penyisipan atau insertion adalah proses menambahkan node baru ke dalam Binary Search Tree dengan tetap mempertahankan aturan BST.
Pada BST, setiap nilai baru dibandingkan dengan node yang sedang diperiksa.
BST awal:
50
/ \
30 70
/ \ / \
20 40 60 80Nilai 25 dibandingkan dengan root 50. Karena 25 lebih kecil, pencarian bergerak ke kiri menuju 30.
Nilai 25 lebih kecil dari 30, sehingga bergerak ke kiri menuju 20.
Nilai 25 lebih besar dari 20, sehingga ditempatkan sebagai right child dari 20.
BST setelah insert 25:
50
/ \
30 70
/ \ / \
20 40 60 80
\
25def insert_recursive(node, value):
if node is None:
return Node(value)
if value < node.value:
node.left = insert_recursive(
node.left,
value
)
elif value > node.value:
node.right = insert_recursive(
node.right,
value
)
return nodedef insert_iterative(root, value):
new_node = Node(value)
if root is None:
return new_node
current = root
while True:
if value < current.value:
if current.left is None:
current.left = new_node
break
current = current.left
elif value > current.value:
if current.right is None:
current.right = new_node
break
current = current.right
else:
break
return rootNilai duplikat perlu ditangani dengan aturan yang konsisten. Salah satu pendekatan yang umum digunakan adalah mengabaikan nilai yang sudah ada.
elif value == node.value:
print("Data sudah tersedia")
return nodeclass Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(node, value):
if node is None:
return Node(value)
if value < node.value:
node.left = insert(
node.left,
value
)
elif value > node.value:
node.right = insert(
node.right,
value
)
else:
print("Nilai", value, "sudah tersedia")
return node
def inorder(node):
if node is not None:
inorder(node.left)
print(node.value, end=" ")
inorder(node.right)
root = None
data = [50, 30, 70, 20, 40, 60, 80]
for value in data:
root = insert(root, value)
print("BST awal:")
inorder(root)
root = insert(root, 25)
print("\\nBST setelah insert 25:")
inorder(root)
root = insert(root, 70)BST awal:
20 30 40 50 60 70 80
BST setelah insert 25:
20 25 30 40 50 60 70 80
Nilai 70 sudah tersedia| Kondisi BST | Kompleksitas Waktu | Keterangan |
|---|---|---|
| BST seimbang | $O(\log n)$ | Tinggi tree relatif kecil. |
| BST miring | $O(n)$ | Tree menyerupai linked list. |
| Tree kosong | $O(1)$ | Node langsung menjadi root. |
Jika data dimasukkan dalam urutan menaik, tree dapat menjadi miring ke kanan.
Data:
10, 20, 30, 40, 50
Hasil BST:
10
\
20
\
30
\
40
\
50Pada kondisi ini, pencarian dan penyisipan dapat memiliki kompleksitas $O(n)$.
Penyisipan pada BST dilakukan dengan membandingkan nilai baru terhadap node yang ada. Nilai yang lebih kecil diarahkan ke kiri, sedangkan nilai yang lebih besar diarahkan ke kanan. Proses dilakukan sampai menemukan posisi kosong. Kompleksitas rata-rata adalah $O(\log n)$, sedangkan pada BST yang miring dapat mencapai $O(n)$.
Penghapusan atau deletion adalah proses menghapus node dari BST dengan tetap mempertahankan aturan Binary Search Tree.
Sebelum menghapus node, program harus mencari node yang sesuai dengan nilai target.
Setelah node ditemukan, proses penghapusan dibedakan berdasarkan jumlah child yang dimiliki node tersebut.
| Kondisi | Penjelasan | Tindakan |
|---|---|---|
| Leaf Node | Node tidak memiliki child. | Node langsung dihapus. |
| Satu Child | Node hanya memiliki satu child. | Child menggantikan posisi node. |
| Dua Child | Node memiliki child kiri dan kanan. | Gunakan inorder successor atau predecessor. |
BST awal:
50
/ \
30 70
/ \ / \
20 40 60 80Node 20 tidak memiliki child. Oleh karena itu, node 20 dapat langsung dihapus.
Setelah menghapus 20:
50
/ \
30 70
\ / \
40 60 80BST awal:
30
\
40
\
45Node 40 hanya memiliki satu child, yaitu 45. Ketika node 40 dihapus, node 45 menggantikan posisi node 40.
Setelah menghapus 40:
30
\
45BST awal:
50
/ \
30 70
/ \ / \
20 40 60 80Node 50 memiliki dua child. Node tersebut tidak dapat langsung dihapus karena struktur BST harus tetap valid.
Salah satu cara adalah mengganti nilai 50 dengan inorder successor, yaitu nilai terkecil pada subtree kanan.
Nilai terkecil pada subtree kanan adalah 60.
Setelah mengganti 50 dengan 60:
60
/ \
30 70
/ \ \
20 40 80Nilai terkecil pada subtree kanan node yang akan dihapus.
Biasanya digunakan untuk menggantikan node yang memiliki dua child.
Nilai terbesar pada subtree kiri node yang akan dihapus.
Dapat digunakan sebagai alternatif successor.
def find_min(node):
current = node
while current.left is not None:
current = current.left
return currentdef delete(node, value):
if node is None:
return None
if value < node.value:
node.left = delete(
node.left,
value
)
elif value > node.value:
node.right = delete(
node.right,
value
)
else:
# Kondisi node tanpa child
if node.left is None and node.right is None:
return None
# Kondisi node hanya memiliki child kanan
if node.left is None:
return node.right
# Kondisi node hanya memiliki child kiri
if node.right is None:
return node.left
# Kondisi node memiliki dua child
successor = find_min(node.right)
node.value = successor.value
node.right = delete(
node.right,
successor.value
)
return nodeclass Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(node, value):
if node is None:
return Node(value)
if value < node.value:
node.left = insert(node.left, value)
elif value > node.value:
node.right = insert(node.right, value)
return node
def find_min(node):
current = node
while current.left is not None:
current = current.left
return current
def delete(node, value):
if node is None:
return None
if value < node.value:
node.left = delete(node.left, value)
elif value > node.value:
node.right = delete(node.right, value)
else:
if node.left is None:
return node.right
if node.right is None:
return node.left
successor = find_min(node.right)
node.value = successor.value
node.right = delete(
node.right,
successor.value
)
return node
def inorder(node):
if node is not None:
inorder(node.left)
print(node.value, end=" ")
inorder(node.right)
root = None
data = [50, 30, 70, 20, 40, 60, 80]
for value in data:
root = insert(root, value)
print("BST awal:")
inorder(root)
root = delete(root, 20)
print("\\nSetelah menghapus 20:")
inorder(root)
root = delete(root, 30)
print("\\nSetelah menghapus 30:")
inorder(root)
root = delete(root, 50)
print("\\nSetelah menghapus 50:")
inorder(root)BST awal:
20 30 40 50 60 70 80
Setelah menghapus 20:
30 40 50 60 70 80
Setelah menghapus 30:
40 50 60 70 80
Setelah menghapus 50:
40 60 70 80| Kondisi BST | Kompleksitas |
|---|---|
| BST seimbang | $O(\log n)$ |
| BST miring | $O(n)$ |
Kompleksitas penghapusan bergantung pada tinggi BST. Pada tree seimbang proses lebih cepat, sedangkan tree miring dapat menyerupai linked list.
Gunakan BST berikut:
50
/ \
30 70
/ \ / \
20 40 60 80Penghapusan pada BST memiliki tiga kondisi. Leaf node dapat langsung dihapus, node dengan satu child digantikan oleh child-nya, sedangkan node dengan dua child digantikan oleh inorder successor atau inorder predecessor. Kompleksitas penghapusan adalah $O(\log n)$ pada BST seimbang dan $O(n)$ pada BST yang miring.
Traversal adalah proses mengunjungi seluruh node pada Binary Search Tree dengan urutan tertentu.
Traversal digunakan untuk membaca, mencetak, atau memproses seluruh node dalam tree.
Pada BST terdapat tiga traversal utama, yaitu Preorder, Inorder, dan Postorder.
50
/ \
30 70
/ \ / \
20 40 60 80| Traversal | Urutan | Hasil |
|---|---|---|
| Preorder | Root - Left - Right | 50, 30, 20, 40, 70, 60, 80 |
| Inorder | Left - Root - Right | 20, 30, 40, 50, 60, 70, 80 |
| Postorder | Left - Right - Root | 20, 40, 30, 60, 80, 70, 50 |
Preorder mengunjungi root terlebih dahulu, kemudian subtree kiri dan subtree kanan.
def preorder(node):
if node is not None:
print(node.value, end=" ")
preorder(node.left)
preorder(node.right)
Hasil:
50 30 20 40 70 60 80Inorder mengunjungi subtree kiri, root, kemudian subtree kanan.
def inorder(node):
if node is not None:
inorder(node.left)
print(node.value, end=" ")
inorder(node.right)
Hasil:
20 30 40 50 60 70 80Postorder mengunjungi subtree kiri, subtree kanan, kemudian root.
def postorder(node):
if node is not None:
postorder(node.left)
postorder(node.right)
print(node.value, end=" ")
Hasil:
20 40 30 60 80 70 50class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(node, value):
if node is None:
return Node(value)
if value < node.value:
node.left = insert(node.left, value)
elif value > node.value:
node.right = insert(node.right, value)
return node
def preorder(node, result):
if node is not None:
result.append(node.value)
preorder(node.left, result)
preorder(node.right, result)
def inorder(node, result):
if node is not None:
inorder(node.left, result)
result.append(node.value)
inorder(node.right, result)
def postorder(node, result):
if node is not None:
postorder(node.left, result)
postorder(node.right, result)
result.append(node.value)
root = None
data = [50, 30, 70, 20, 40, 60, 80]
for value in data:
root = insert(root, value)
preorder_result = []
inorder_result = []
postorder_result = []
preorder(root, preorder_result)
inorder(root, inorder_result)
postorder(root, postorder_result)
print("Preorder:", preorder_result)
print("Inorder:", inorder_result)
print("Postorder:", postorder_result)Preorder: [50, 30, 20, 40, 70, 60, 80]
Inorder: [20, 30, 40, 50, 60, 70, 80]
Postorder: [20, 40, 30, 60, 80, 70, 50]| Operasi | Kompleksitas Waktu | Kompleksitas Ruang |
|---|---|---|
| Preorder | $O(n)$ | $O(h)$ |
| Inorder | $O(n)$ | $O(h)$ |
| Postorder | $O(n)$ | $O(h)$ |
Simbol $n$ adalah jumlah node, sedangkan $h$ adalah tinggi tree.
Gunakan BST berikut:
50
/ \
30 70
/ \ / \
20 40 60 80Traversal pada BST terdiri dari Preorder, Inorder, dan Postorder. Preorder menggunakan urutan Root - Left - Right, Inorder menggunakan Left - Root - Right, sedangkan Postorder menggunakan Left - Right - Root. Setiap traversal mengunjungi seluruh node dengan kompleksitas waktu $O(n)$.
AVL Tree adalah Binary Search Tree yang selalu menjaga keseimbangan tinggi subtree kiri dan subtree kanan.
AVL Tree adalah jenis Self-Balancing Binary Search Tree. Nama AVL berasal dari nama penemunya, yaitu Adelson-Velsky dan Landis.
Setiap node pada AVL Tree memiliki nilai Balance Factor yang harus berada pada rentang $-1$ sampai $1$.
Balance Factor digunakan untuk menentukan apakah sebuah node masih seimbang.
| Balance Factor | Status |
|---|---|
| $-1$ | Masih seimbang. |
| $0$ | Seimbang sempurna. |
| $1$ | Masih seimbang. |
| $<-1$ atau $>1$ | Tidak seimbang dan perlu rotasi. |
30
/ \
20 40Tinggi subtree kiri dan kanan hampir sama.
30
\
40
\
50Subtree kanan terlalu tinggi sehingga perlu rotasi.
| Kasus | Kondisi | Rotasi |
|---|---|---|
| LL | Berat di subtree kiri bagian kiri. | Rotasi kanan. |
| RR | Berat di subtree kanan bagian kanan. | Rotasi kiri. |
| LR | Berat di kiri lalu kanan. | Rotasi kiri, kemudian kanan. |
| RL | Berat di kanan lalu kiri. | Rotasi kanan, kemudian kiri. |
Sebelum rotasi:
30
/
20
/
10
Sesudah rotasi kanan:
20
/ \
10 30Kasus LL terjadi ketika node baru masuk ke subtree kiri dari child kiri.
Sebelum rotasi:
10
\
20
\
30
Sesudah rotasi kiri:
20
/ \
10 30Kasus RR terjadi ketika node baru masuk ke subtree kanan dari child kanan.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
self.height = 1def height(node):
if node is None:
return 0
return node.height
def get_balance(node):
if node is None:
return 0
return height(node.left) - height(node.right)
def update_height(node):
node.height = 1 + max(
height(node.left),
height(node.right)
)def rotate_right(y):
x = y.left
temp = x.right
x.right = y
y.left = temp
update_height(y)
update_height(x)
return xdef rotate_left(x):
y = x.right
temp = y.left
y.left = x
x.right = temp
update_height(x)
update_height(y)
return ydef insert(node, value):
if node is None:
return Node(value)
if value < node.value:
node.left = insert(node.left, value)
elif value > node.value:
node.right = insert(node.right, value)
else:
return node
update_height(node)
balance = get_balance(node)
# Kasus LL
if balance > 1 and value < node.left.value:
return rotate_right(node)
# Kasus RR
if balance < -1 and value > node.right.value:
return rotate_left(node)
# Kasus LR
if balance > 1 and value > node.left.value:
node.left = rotate_left(node.left)
return rotate_right(node)
# Kasus RL
if balance < -1 and value < node.right.value:
node.right = rotate_right(node.right)
return rotate_left(node)
return nodeclass Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
self.height = 1
def height(node):
if node is None:
return 0
return node.height
def update_height(node):
node.height = 1 + max(
height(node.left),
height(node.right)
)
def get_balance(node):
if node is None:
return 0
return height(node.left) - height(node.right)
def rotate_right(y):
x = y.left
temp = x.right
x.right = y
y.left = temp
update_height(y)
update_height(x)
return x
def rotate_left(x):
y = x.right
temp = y.left
y.left = x
x.right = temp
update_height(x)
update_height(y)
return y
def insert(node, value):
if node is None:
return Node(value)
if value < node.value:
node.left = insert(node.left, value)
elif value > node.value:
node.right = insert(node.right, value)
else:
return node
update_height(node)
balance = get_balance(node)
if balance > 1 and value < node.left.value:
return rotate_right(node)
if balance < -1 and value > node.right.value:
return rotate_left(node)
if balance > 1 and value > node.left.value:
node.left = rotate_left(node.left)
return rotate_right(node)
if balance < -1 and value < node.right.value:
node.right = rotate_right(node.right)
return rotate_left(node)
return node
def inorder(node):
if node is not None:
inorder(node.left)
print(node.value, end=" ")
inorder(node.right)
root = None
data = [30, 20, 10, 40, 50, 25]
for value in data:
root = insert(root, value)
print("Inorder AVL Tree:")
inorder(root)Inorder AVL Tree:
10 20 25 30 40 50Hasil Inorder tetap terurut karena AVL Tree masih mengikuti aturan Binary Search Tree.
| Operasi | Kompleksitas |
|---|---|
| Search | $O(\log n)$ |
| Insert | $O(\log n)$ |
| Delete | $O(\log n)$ |
| Rotasi | $O(1)$ |
AVL Tree menjaga tinggi tree tetap $O(\log n)$ sehingga operasi pencarian, penyisipan, dan penghapusan tetap efisien.
AVL Tree adalah Binary Search Tree yang menjaga keseimbangan secara otomatis. Keseimbangan diukur menggunakan Balance Factor. Jika nilai Balance Factor berada di luar rentang $-1$ sampai $1$, AVL Tree melakukan rotasi. Dengan mekanisme tersebut, operasi search, insert, dan delete memiliki kompleksitas $O(\log n)$.
Balance Factor digunakan untuk mengukur keseimbangan subtree kiri dan subtree kanan pada setiap node AVL Tree.
Balance Factor adalah nilai yang menunjukkan perbedaan tinggi antara subtree kiri dan subtree kanan dari sebuah node.
AVL Tree dikatakan seimbang jika nilai Balance Factor setiap node berada pada rentang $-1$ sampai $1$.
| Nilai BF | Kondisi | Keterangan |
|---|---|---|
| $0$ | Seimbang | Tinggi subtree kiri dan kanan sama. |
| $1$ | Seimbang | Subtree kiri lebih tinggi satu tingkat. |
| $-1$ | Seimbang | Subtree kanan lebih tinggi satu tingkat. |
| $>1$ | Tidak seimbang | Terlalu berat ke kiri. |
| $<-1$ | Tidak seimbang | Terlalu berat ke kanan. |
30
/ \
20 40Node 30 memiliki Balance Factor 0 sehingga kondisinya seimbang.
30
/
20
/
10Pada node 30, subtree kiri memiliki tinggi 2, sedangkan subtree kanan memiliki tinggi 0.
Karena Balance Factor bernilai 2, tree tidak seimbang dan membutuhkan rotasi kanan.
10
\
20
\
30Pada node 10, subtree kiri memiliki tinggi 0, sedangkan subtree kanan memiliki tinggi 2.
Karena Balance Factor bernilai $-2$, tree tidak seimbang dan membutuhkan rotasi kiri.
def height(node):
if node is None:
return 0
return node.height
def get_balance(node):
if node is None:
return 0
return (
height(node.left)
- height(node.right)
)def is_balanced(node):
if node is None:
return True
balance = get_balance(node)
if balance < -1 or balance > 1:
return False
return (
is_balanced(node.left)
and is_balanced(node.right)
)| Kondisi | Syarat | Rotasi |
|---|---|---|
| LL | $BF > 1$ dan data masuk ke kiri | Rotasi kanan |
| RR | $BF < -1$ dan data masuk ke kanan | Rotasi kiri |
| LR | $BF > 1$ dan data masuk ke kanan | Rotasi kiri lalu kanan |
| RL | $BF < -1$ dan data masuk ke kiri | Rotasi kanan lalu kiri |
Balance Factor digunakan untuk mengukur keseimbangan AVL Tree. Rumusnya adalah tinggi subtree kiri dikurangi tinggi subtree kanan. Nilai yang valid adalah $-1$, $0$, dan $1$. Jika nilainya lebih besar dari $1$ atau lebih kecil dari $-1$, AVL Tree harus diperbaiki menggunakan rotasi.
Right Rotation adalah rotasi ke kanan yang digunakan untuk memperbaiki AVL Tree yang terlalu berat pada subtree kiri.
Right Rotation memindahkan node kiri ke posisi parent baru, sedangkan node yang sebelumnya menjadi parent dipindahkan ke sebelah kanan.
Rotasi ini digunakan ketika Balance Factor sebuah node lebih besar dari $1$.
Sebelum rotasi:
30
/
20
/
10Node 30 terlalu berat ke kiri. Nilai 20 menjadi child kiri dari 30, kemudian nilai 10 menjadi child kiri dari 20.
Sesudah Right Rotation:
20
/ \
10 30Sebelum:
y
/ \
x C
/ \
A B
Sesudah:
x
/ \
A y
/ \
B CSubtree $B$ dipindahkan menjadi subtree kiri dari node $y$.
def height(node):
if node is None:
return 0
return node.height
def update_height(node):
node.height = 1 + max(
height(node.left),
height(node.right)
)
def rotate_right(y):
# x menjadi root baru
x = y.left
# Simpan subtree kanan x
temp = x.right
# Lakukan rotasi
x.right = y
y.left = temp
# Perbarui height
update_height(y)
update_height(x)
# Kembalikan root baru
return xclass Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
self.height = 1
def height(node):
if node is None:
return 0
return node.height
def update_height(node):
node.height = 1 + max(
height(node.left),
height(node.right)
)
def rotate_right(y):
x = y.left
temp = x.right
x.right = y
y.left = temp
update_height(y)
update_height(x)
return x
root = Node(30)
root.left = Node(20)
root.left.left = Node(10)
print("Sebelum rotasi:")
print(root.value)
print(root.left.value)
print(root.left.left.value)
root = rotate_right(root)
print("\\nSetelah Right Rotation:")
print("Root:", root.value)
print("Child kiri:", root.left.value)
print("Child kanan:", root.right.value)Sebelum rotasi:
30
20
10
Setelah Right Rotation:
Root: 20
Child kiri: 10
Child kanan: 30Right Rotation dilakukan ketika sebuah node memiliki Balance Factor lebih besar dari $1$.
Jika nilai baru masuk ke subtree kiri dari child kiri, maka kondisi tersebut disebut kasus LL dan cukup diperbaiki dengan satu Right Rotation.
| Operasi | Kompleksitas | Keterangan |
|---|---|---|
| Right Rotation | $O(1)$ | Hanya melibatkan beberapa pointer. |
| Update Height | $O(1)$ | Menghitung tinggi dua node. |
Right Rotation digunakan untuk memperbaiki AVL Tree yang berat ke kiri, khususnya kasus LL. Node kiri menjadi root baru, node sebelumnya menjadi child kanan, dan subtree kanan dari node kiri dipindahkan menjadi subtree kiri node sebelumnya. Kompleksitas Right Rotation adalah $O(1)$.
Left Rotation adalah rotasi ke kiri yang digunakan untuk memperbaiki AVL Tree yang terlalu berat pada subtree kanan.
Left Rotation memindahkan node kanan ke posisi root baru, sedangkan node yang sebelumnya menjadi root dipindahkan ke sebelah kiri.
Rotasi ini digunakan ketika Balance Factor sebuah node lebih kecil dari $-1$.
Sebelum rotasi:
10
\
20
\
30Node 10 terlalu berat ke kanan. Nilai 20 menjadi child kanan dari 10, kemudian nilai 30 menjadi child kanan dari 20.
Sesudah Left Rotation:
20
/ \
10 30Sebelum:
x
/ \
A y
/ \
B C
Sesudah:
y
/ \
x C
/ \
A BSubtree $B$ dipindahkan menjadi subtree kanan dari node $x$.
def height(node):
if node is None:
return 0
return node.height
def update_height(node):
node.height = 1 + max(
height(node.left),
height(node.right)
)
def rotate_left(x):
# y menjadi root baru
y = x.right
# Simpan subtree kiri y
temp = y.left
# Lakukan rotasi
y.left = x
x.right = temp
# Perbarui height
update_height(x)
update_height(y)
# Kembalikan root baru
return yclass Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
self.height = 1
def height(node):
if node is None:
return 0
return node.height
def update_height(node):
node.height = 1 + max(
height(node.left),
height(node.right)
)
def rotate_left(x):
y = x.right
temp = y.left
y.left = x
x.right = temp
update_height(x)
update_height(y)
return y
root = Node(10)
root.right = Node(20)
root.right.right = Node(30)
print("Sebelum rotasi:")
print(root.value)
print(root.right.value)
print(root.right.right.value)
root = rotate_left(root)
print("\\nSetelah Left Rotation:")
print("Root:", root.value)
print("Child kiri:", root.left.value)
print("Child kanan:", root.right.value)Sebelum rotasi:
10
20
30
Setelah Left Rotation:
Root: 20
Child kiri: 10
Child kanan: 30Left Rotation dilakukan ketika sebuah node memiliki Balance Factor lebih kecil dari $-1$.
Jika nilai baru masuk ke subtree kanan dari child kanan, maka kondisi tersebut disebut kasus RR dan cukup diperbaiki dengan satu Left Rotation.
| Rotasi | Digunakan untuk | Kasus |
|---|---|---|
| Right Rotation | Tree berat ke kiri | LL |
| Left Rotation | Tree berat ke kanan | RR |
| Operasi | Kompleksitas |
|---|---|
| Left Rotation | $O(1)$ |
| Update Height | $O(1)$ |
Left Rotation hanya mengubah beberapa hubungan antar-node, sehingga kompleksitas waktunya adalah $O(1)$.
Left Rotation digunakan untuk memperbaiki AVL Tree yang berat ke kanan, khususnya kasus RR. Node kanan menjadi root baru, node sebelumnya menjadi child kiri, dan subtree kiri node kanan dipindahkan menjadi subtree kanan node sebelumnya. Kompleksitas Left Rotation adalah $O(1)$.
AVL Tree mendukung operasi search, insert, delete, dan traversal dengan tetap menjaga keseimbangan tree.
| Operasi | Fungsi | Kompleksitas |
|---|---|---|
| Search | Mencari nilai pada AVL Tree. | $O(\log n)$ |
| Insert | Menambahkan node baru. | $O(\log n)$ |
| Delete | Menghapus node dari tree. | $O(\log n)$ |
| Traversal | Mengunjungi seluruh node. | $O(n)$ |
Operasi Search pada AVL Tree sama seperti pencarian pada BST. Perbedaannya, AVL Tree selalu menjaga tinggi tree tetap kecil.
def search(node, target):
if node is None:
return False
if node.value == target:
return True
if target < node.value:
return search(node.left, target)
return search(node.right, target)Insert pada AVL Tree dilakukan seperti BST. Setelah node ditambahkan, tinggi node diperbarui dan Balance Factor diperiksa.
def insert(node, value):
if node is None:
return Node(value)
if value < node.value:
node.left = insert(node.left, value)
elif value > node.value:
node.right = insert(node.right, value)
else:
return node
update_height(node)
balance = get_balance(node)
# Kasus LL
if balance > 1 and value < node.left.value:
return rotate_right(node)
# Kasus RR
if balance < -1 and value > node.right.value:
return rotate_left(node)
# Kasus LR
if balance > 1 and value > node.left.value:
node.left = rotate_left(node.left)
return rotate_right(node)
# Kasus RL
if balance < -1 and value < node.right.value:
node.right = rotate_right(node.right)
return rotate_left(node)
return nodeDelete pada AVL Tree dilakukan dengan cara BST. Setelah node dihapus, tree harus diperiksa kembali agar tetap seimbang.
def delete(node, value):
if node is None:
return None
if value < node.value:
node.left = delete(node.left, value)
elif value > node.value:
node.right = delete(node.right, value)
else:
if node.left is None:
return node.right
if node.right is None:
return node.left
successor = find_min(node.right)
node.value = successor.value
node.right = delete(
node.right,
successor.value
)
update_height(node)
balance = get_balance(node)
# Left heavy
if balance > 1:
if get_balance(node.left) >= 0:
return rotate_right(node)
node.left = rotate_left(node.left)
return rotate_right(node)
# Right heavy
if balance < -1:
if get_balance(node.right) <= 0:
return rotate_left(node)
node.right = rotate_right(node.right)
return rotate_left(node)
return nodeTraversal pada AVL Tree sama seperti traversal pada BST karena AVL Tree tetap merupakan Binary Search Tree.
def inorder(node):
if node is not None:
inorder(node.left)
print(node.value, end=" ")
inorder(node.right)
def preorder(node):
if node is not None:
print(node.value, end=" ")
preorder(node.left)
preorder(node.right)
def postorder(node):
if node is not None:
postorder(node.left)
postorder(node.right)
print(node.value, end=" ")class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
self.height = 1
def height(node):
if node is None:
return 0
return node.height
def update_height(node):
node.height = 1 + max(
height(node.left),
height(node.right)
)
def get_balance(node):
if node is None:
return 0
return height(node.left) - height(node.right)
def rotate_right(y):
x = y.left
temp = x.right
x.right = y
y.left = temp
update_height(y)
update_height(x)
return x
def rotate_left(x):
y = x.right
temp = y.left
y.left = x
x.right = temp
update_height(x)
update_height(y)
return y
def insert(node, value):
if node is None:
return Node(value)
if value < node.value:
node.left = insert(node.left, value)
elif value > node.value:
node.right = insert(node.right, value)
else:
return node
update_height(node)
balance = get_balance(node)
if balance > 1 and value < node.left.value:
return rotate_right(node)
if balance < -1 and value > node.right.value:
return rotate_left(node)
if balance > 1 and value > node.left.value:
node.left = rotate_left(node.left)
return rotate_right(node)
if balance < -1 and value < node.right.value:
node.right = rotate_right(node.right)
return rotate_left(node)
return node
def search(node, target):
if node is None:
return False
if node.value == target:
return True
if target < node.value:
return search(node.left, target)
return search(node.right, target)
def inorder(node):
if node is not None:
inorder(node.left)
print(node.value, end=" ")
inorder(node.right)
root = None
data = [30, 20, 10, 40, 50, 25]
for value in data:
root = insert(root, value)
print("Inorder:")
inorder(root)
print("\\nCari 25:", search(root, 25))
print("Cari 100:", search(root, 100))Inorder:
10 20 25 30 40 50
Cari 25: True
Cari 100: False| Aspek | BST Biasa | AVL Tree |
|---|---|---|
| Keseimbangan | Tidak selalu seimbang. | Selalu dijaga. |
| Search Worst Case | $O(n)$ | $O(\log n)$ |
| Insert | Lebih sederhana. | Membutuhkan pemeriksaan balance. |
| Rotasi | Tidak digunakan. | Digunakan jika diperlukan. |
Operasi pada AVL Tree terdiri dari search, insert, delete, dan traversal. Operasi insert dan delete diikuti dengan pembaruan height, pemeriksaan Balance Factor, serta rotasi apabila tree tidak seimbang. Karena AVL Tree selalu menjaga keseimbangan, operasi search, insert, dan delete memiliki kompleksitas $O(\log n)$.
B-Tree adalah struktur data tree yang dirancang untuk menyimpan data dalam jumlah besar dan mengurangi jumlah akses ke media penyimpanan.
B-Tree adalah balanced multiway search tree. Berbeda dengan Binary Search Tree yang setiap node-nya memiliki maksimal dua child, sebuah node pada B-Tree dapat memiliki banyak key dan banyak child.
Semua leaf pada B-Tree berada pada level yang sama. Hal ini membuat struktur B-Tree tetap seimbang meskipun banyak data ditambahkan atau dihapus.
[30 | 60]
/ | \
[10 | 20] [40 | 50] [70 | 80 | 90]Node root menyimpan beberapa key dan memiliki tiga child. Setiap child menyimpan nilai sesuai rentang key pada parent.
| Istilah | Pengertian |
|---|---|
| Key | Nilai yang disimpan dalam node. |
| Node | Tempat untuk menyimpan satu atau beberapa key. |
| Order | Jumlah maksimum child yang dapat dimiliki sebuah node. |
| Leaf | Node yang tidak memiliki child. |
| Internal Node | Node yang memiliki satu atau beberapa child. |
Pada B-Tree order 3, setiap node dapat memiliki maksimal tiga child dan maksimal dua key.
| Komponen | Jumlah Maksimal |
|---|---|
| Child | 3 |
| Key | 2 |
| Subtree | 3 |
[30 | 60]
/ | \
[10] [40] [70]| Aspek | BST | B-Tree |
|---|---|---|
| Jumlah child | Maksimal 2 | Dapat lebih dari 2 |
| Key per node | Satu key | Dapat memiliki banyak key |
| Keseimbangan | Tidak selalu seimbang | Selalu seimbang |
| Penggunaan utama | Pencarian di memori | Database dan file system |
| Operasi disk | Dapat lebih banyak | Lebih sedikit |
Mencari key pada node atau child tertentu.
Menambahkan key baru ke dalam B-Tree.
Menghapus key dengan proses merge atau borrow.
Memecah node yang sudah penuh.
Split dilakukan ketika sebuah node telah mencapai jumlah key maksimum. Key bagian tengah dinaikkan ke parent, sedangkan key lainnya dibagi ke dua node baru.
Node penuh:
[10 | 20 | 30]
Setelah split:
[20]
/ \
[10] [30]Proses split membantu B-Tree mempertahankan ukuran dan keseimbangan setiap node.
| Operasi | Kompleksitas |
|---|---|
| Search | $O(\log n)$ |
| Insert | $O(\log n)$ |
| Delete | $O(\log n)$ |
| Traversal | $O(n)$ |
Karena B-Tree memiliki banyak child pada setiap node dan selalu seimbang, tinggi tree dapat dijaga tetap rendah.
B-Tree adalah balanced multiway search tree yang dapat menyimpan banyak key dalam satu node. Semua leaf berada pada level yang sama sehingga tree tetap seimbang. B-Tree digunakan secara luas pada database dan file system karena mampu mengurangi jumlah akses ke media penyimpanan. Operasi search, insert, dan delete memiliki kompleksitas $O(\log n)$.
Node pada B-Tree dapat menyimpan beberapa key dan memiliki beberapa child sesuai dengan order B-Tree.
Node pada B-Tree berbeda dari node pada Binary Search Tree. Satu node B-Tree dapat menyimpan lebih dari satu key dan memiliki beberapa pointer child.
Key dalam setiap node harus tersusun secara menaik agar proses pencarian dapat dilakukan dengan efisien.
[K1 | K2 | K3]
/ | | \
C0 C1 C2 C3Node tersebut memiliki tiga key dan empat child. Secara umum, jumlah child adalah satu lebih banyak daripada jumlah key.
| Komponen | Fungsi |
|---|---|
| Keys | Menyimpan nilai atau data dalam urutan menaik. |
| Children | Menunjukkan subtree yang memiliki rentang nilai tertentu. |
| Leaf Status | Menunjukkan apakah node memiliki child atau tidak. |
| Key Count | Menyimpan jumlah key yang sedang digunakan. |
[30 | 60]
/ | \
C0 C1 C2| Child | Rentang Nilai |
|---|---|
| C0 | Nilai kurang dari 30 |
| C1 | Nilai antara 30 dan 60 |
| C2 | Nilai lebih besar dari 60 |
class BTreeNode:
def __init__(self, leaf=False):
self.keys = []
self.children = []
self.leaf = leaf
def is_full(self, max_keys):
return len(self.keys) == max_keys
def key_count(self):
return len(self.keys)root = BTreeNode(leaf=False)
root.keys = [30, 60]
child_left = BTreeNode(leaf=True)
child_middle = BTreeNode(leaf=True)
child_right = BTreeNode(leaf=True)
child_left.keys = [10, 20]
child_middle.keys = [40, 50]
child_right.keys = [70, 80]
root.children = [
child_left,
child_middle,
child_right
]def is_valid_node(node):
# Key harus terurut menaik
if node.keys != sorted(node.keys):
return False
# Leaf tidak memiliki child
if node.leaf and len(node.children) != 0:
return False
# Internal node memiliki jumlah child
# satu lebih banyak dari jumlah key
if not node.leaf:
if len(node.children) != len(node.keys) + 1:
return False
return True| Jenis Node | Ciri-ciri |
|---|---|
| Root | Node paling atas. Dapat memiliki aturan jumlah key yang berbeda. |
| Internal Node | Memiliki key dan child. |
| Leaf Node | Memiliki key tetapi tidak memiliki child. |
Root
[30 | 60]
/ | \
/ | \
Internal Internal Leaf
[10 | 20] [40 | 50] [70 | 80]Order B-Tree menentukan jumlah maksimum child yang dapat dimiliki oleh sebuah node.
| Order | Maksimal Key | Maksimal Child |
|---|---|---|
| 3 | 2 | 3 |
| 4 | 3 | 4 |
| 5 | 4 | 5 |
Secara umum, B-Tree order $m$ memiliki paling banyak $m$ child dan $m - 1$ key dalam satu node.
Node B-Tree dapat menyimpan beberapa key dan child. Key disimpan dalam urutan menaik, sedangkan child menunjukkan rentang nilai tertentu. Jika sebuah node memiliki $k$ key, maka node tersebut dapat memiliki paling banyak $k + 1$ child. Struktur ini membuat B-Tree cocok untuk penyimpanan data berukuran besar.
Pencarian pada B-Tree dilakukan dengan membandingkan nilai target terhadap beberapa key dalam node, kemudian memilih child yang sesuai.
Pencarian pada B-Tree dimulai dari root. Key dalam node diperiksa untuk menentukan apakah nilai target ditemukan atau harus dicari pada child tertentu.
Karena key pada setiap node tersusun secara menaik, pencarian dapat dilakukan secara efisien.
[30 | 60]
/ | \
[10 | 20] [40 | 50] [70 | 80]Root memiliki key 30 dan 60 sehingga root memiliki tiga rentang child.
| Kondisi Target | Child yang Dipilih |
|---|---|
| Target kurang dari 30 | Child paling kiri |
| Target berada antara 30 dan 60 | Child tengah |
| Target lebih besar dari 60 | Child paling kanan |
[30 | 60]
|
[40 | 50]
Hasil pencarian: 50 ditemukanMisalnya dilakukan pencarian terhadap nilai 55.
[30 | 60]
|
[40 | 50]
Hasil pencarian: 55 tidak ditemukandef search(node, target):
index = 0
# Cari posisi target atau posisi child
while (
index < len(node.keys)
and target > node.keys[index]
):
index += 1
# Target ditemukan pada node
if (
index < len(node.keys)
and target == node.keys[index]
):
return True
# Jika node leaf, target tidak ditemukan
if node.leaf:
return False
# Lanjutkan pencarian ke child
return search(
node.children[index],
target
)def search_iterative(root, target):
current = root
while current is not None:
index = 0
while (
index < len(current.keys)
and target > current.keys[index]
):
index += 1
if (
index < len(current.keys)
and target == current.keys[index]
):
return True
if current.leaf:
return False
current = current.children[index]
return FalseInsertion dapat menyebabkan node penuh terbelah dan key median naik ke parent.
Insertion dapat menyebabkan node penuh terbelah dan key median naik ke parent.
def proses(data):
# Implementasikan konsep Penyisipan pada B-Tree
return data
contoh = [3, 1, 2]
print(proses(contoh))Deletion dapat membutuhkan peminjaman key atau penggabungan node.
Deletion dapat membutuhkan peminjaman key atau penggabungan node.
def proses(data):
# Implementasikan konsep Penghapusan pada B-Tree
return data
contoh = [3, 1, 2]
print(proses(contoh))Graph terdiri dari vertex dan edge untuk memodelkan hubungan antarobjek.
Graph terdiri dari vertex dan edge untuk memodelkan hubungan antarobjek.
def proses(data):
# Implementasikan konsep Graph
return data
contoh = [3, 1, 2]
print(proses(contoh))Graph dapat direpresentasikan dengan edge list, adjacency matrix, atau adjacency list.
Graph dapat direpresentasikan dengan edge list, adjacency matrix, atau adjacency list.
def proses(data):
# Implementasikan konsep Representasi Graph
return data
contoh = [3, 1, 2]
print(proses(contoh))Adjacency matrix memakai tabel dua dimensi untuk menyatakan hubungan antarvertex.
Adjacency matrix memakai tabel dua dimensi untuk menyatakan hubungan antarvertex.
def proses(data):
# Implementasikan konsep Adjacency Matrix
return data
contoh = [3, 1, 2]
print(proses(contoh))Adjacency list menyimpan daftar tetangga untuk setiap vertex dan efisien untuk graph sparse.
Adjacency list menyimpan daftar tetangga untuk setiap vertex dan efisien untuk graph sparse.
def proses(data):
# Implementasikan konsep Adjacency List
return data
contoh = [3, 1, 2]
print(proses(contoh))Traversal graph mengunjungi vertex yang terhubung dengan aturan tertentu.
Traversal graph mengunjungi vertex yang terhubung dengan aturan tertentu.
def proses(data):
# Implementasikan konsep Graph Traversal
return data
contoh = [3, 1, 2]
print(proses(contoh))BFS mengunjungi graph berdasarkan level menggunakan queue.
BFS mengunjungi graph berdasarkan level menggunakan queue.
def proses(data):
# Implementasikan konsep Breadth-First Search
return data
contoh = [3, 1, 2]
print(proses(contoh))DFS menelusuri sedalam mungkin menggunakan stack atau rekursi.
DFS menelusuri sedalam mungkin menggunakan stack atau rekursi.
def proses(data):
# Implementasikan konsep Depth-First Search
return data
contoh = [3, 1, 2]
print(proses(contoh))Shortest path mencari jalur dengan total bobot minimum atau jumlah edge minimum.
Shortest path mencari jalur dengan total bobot minimum atau jumlah edge minimum.
def proses(data):
# Implementasikan konsep Shortest Path
return data
contoh = [3, 1, 2]
print(proses(contoh))Graph search digunakan untuk menemukan target, konektivitas, rute, atau komponen graph.
Graph search digunakan untuk menemukan target, konektivitas, rute, atau komponen graph.
def proses(data):
# Implementasikan konsep Graph Search
return data
contoh = [3, 1, 2]
print(proses(contoh))Project akhir mengintegrasikan struktur data dan algoritma untuk menyelesaikan masalah sains data.
Project akhir mengintegrasikan struktur data dan algoritma untuk menyelesaikan masalah sains data.
def proses(data):
# Implementasikan konsep Project Akhir
return data
contoh = [3, 1, 2]
print(proses(contoh))Rancang solusi algoritmik dan jelaskan pemilihan struktur data, kompleksitas, serta pengujiannya.
Rancang solusi algoritmik dan jelaskan pemilihan struktur data, kompleksitas, serta pengujiannya.
def proses(data):
# Implementasikan konsep Penugasan UAS
return data
contoh = [3, 1, 2]
print(proses(contoh))Kuis UAS mencakup struktur data hierarkis, graph, algoritma sorting, searching, dan analisis kompleksitas.
Kuis UAS mencakup struktur data hierarkis, graph, algoritma sorting, searching, dan analisis kompleksitas.
def proses(data):
# Implementasikan konsep Kuis UAS
return data
contoh = [3, 1, 2]
print(proses(contoh))Bangun aplikasi berbasis proyek yang menerapkan struktur data dan algoritma secara terukur dan terdokumentasi.
Bangun aplikasi berbasis proyek yang menerapkan struktur data dan algoritma secara terukur dan terdokumentasi.
def proses(data):
# Implementasikan konsep Project UAS
return data
contoh = [3, 1, 2]
print(proses(contoh))