Binary Search Tree

Sifat binary tree :
1. Nilai root < nilai anak kanan
2. Nilai root > nilai anak kiri

Binary search tree mepercepat pencarian dibandingkan sequential search
BST
Waktu terlama = tinggi binary search tree
jika ada n data, waktu ( t ) = log ( n+ 1) // dengan basis 2
= log n ( O ) // dengan basis 2

Sequential search
waktu ( t ) = n ( O )

Operasi delete
Prinsip : setelah operasi delete hasil harus binary search tree lagi
Ada 3 operasi :
1. Jika delete node yang tidak punya anak : tidak ada perubahan
2. Jika delete node yang memiliki 1 anak : anaknya sebagai pengganti
3. Jika delete node yang memiliki 2 anak :
jika pengganti dari kiri, ambil node tertinggi
Jika pengganti dari kanan, ambil node terendah


Untuk source code :

http://download.gilaupload.com/filepointer.php?fid=a1315ef67274eed20268babaf129c501

Untuk animasi :
http://www.ibr.cs.tu-bs.de/courses/ss98/audii/applets/BST/

Overloading operator

Operator-operator yang ada di dalam bahasa pemrograman, seperti c/c++, dapat dioverload.
Maksud dioverload adalah makna dari operator itu bisa diubah.
Contohnya :
operator + dalam bahasa pemrograman hanya bisa menjumlahkan antara tipe integer dan integer ( default ) tetapi dengan operator overloading, operator + dapat dioverload sehingga dapat menjumlahkan antara tipe char dengan char, tipe string dengan string.

Operator-operator lain pun bisa dioverload. Dibawah akan diberikan contoh penggunaan operator overloading dan bagaimana mengoverloadnya.

http://download.gilaupload.com/filepointer.php?fid=1f5e3e352c84fb4c0e4bf5f6c487616d

Heap sort

Heap sort adalah salah satu cara dari beberapa cara pengurutan yang ada.
Heap sort merupakan cara yang tercepat untuk mengurutkan angka, huruf, string, dan lain-lain.
Heap sort memiliki kompleksitas algoritma (O(n)) = n log n

Lebih lengkap :
Struktur data heap adalah array objek yang dapat dengan mudah divisualisasi sebagai sebuah complete binary tree. Terdapat sebuah one to one koresponden antara element - element array dan node -node tree. Tree diisi pada semua level kecuali mungkin ada yang terendah dimana diisi dari kiri sampai 'a point'. Semua node heap juga 'memuaskan' hubungan dimana nilai kunci pada setiap node setidaknya sama besar dengan nilai pada anaknya.

Langkah-langkahnya :
1. User menginput ukuran heap. Lalu program menghasilkan binary tree yang saling berkaitan
dengan node mempunyai nilai kunci yang dihasilkan secara acak.

2. Membangun operasi heap
Misalkan n adalah nomor node di dalam tree dan i adalah kunci sebuah tree. Untuk ini,
program menggunakan operasi heapify. Ketika heapify dipanggil keduanya subtree kiri dan
kanan i adalah heap. Fungsi heapify adalah meletakkan i ke sebuah posisi ( dengan
pertukaran dirinya dengan nilai yang lebih besar pada anaknya, sewaktu sifat heap tidak
terpenuhi ) sampai sifat heap terpenuhi di dalam tree dimana 'diakarkan' pada i. Operasi ini memanggil.

3. Hilangkan elemen maksimum
Program menghilangkan elemen terbesar pada heap ( root ) dengan menukarkannya dengan
elemen terakhir.

4. Program mengeksekusi heapify( root baru ) jadi menghasilkan tree yang memenuhi sifat heap

5. Ulangi langkah 3 sampai heap habis atau kosong.

Berikut disertakan contoh kodingan dengan menggunakan bahasa c.
http://download.gilaupload.com/filepointer.php?fid=deae6d6ca7abe9e3779f0263ae22cdd8

Untuk animasi :
http://www2.hawaii.edu/~copley/665/HSApplet.html

Single Shortest Path

Single Shortest Path merupakan salah satu metode Greedy untuk mencari jalur terpendek.
Single shortest path ini menggunakan algoritma Djikstra.
Dalam teori graph, masalah jalur terpendek adalah masalah menemukan sebuah jalur antara 2 verteks yang mempunyai jumlah cost minimal. Contohnya adalah menemukan cara tercepat untuk sampai ke suatu lokasi dari lokasi lain pada peta. Pada kasus ini, verteks bertindak sebagai lokasi dan rusuk bertindak sebagai segmen jalan dan cost nya adalah waktu yang dibutuhkan untuk melewati segmen jalan tersebut.
Untuk lebih jelasnya, saya berikan link yang berisikan source code dalam bahasa c++ agar bisa lebih dimengerti.

Untuk source code :
http://download.gilaupload.com/filepointer.php?fid=f8c7ffba0a8ca65e4298d560397f2ee6

Untuk animasi :
http://www.cs.sunysb.edu/~skiena/combinatorica/animations/dijkstra.html