Di email sebelumnya, saya hanya mengkritik BST construction nya. Sekarang saya kritik di algo searchnya. Algo search kamu meskipun menggunakan balanced BST, tetap run in O( N ).
Berikut adalah algo kamu untuk search: 2008/6/9 viking leon <[EMAIL PROTECTED]>: > search on left, > kalo belum ktemu search on right > kalo udah ktemu terus search on left > (cari terus ke node left paling dalam yang > bisa ditemukan note: node right engga usah disearch) Algo ini berjalan seperti: 1. in-order Tree traversal biasa, dan akan berhenti jika menemukan suatu node yang mempunyai index antara index queryMin(i,j), ini O( N ). 2. lalu algonya dilanjutkan dengan traverse ke kiri dari node terakhir itu O( log N ). Kalau ternyata index yang dicari ada di ujung paling kanan bawah, maka kamu akan traverse the entire tree O( N ) sebelum algonya berubah jadi algo ke-2 yang O( log N ). Jadi dalam kasus A = [1, 2, 3, ..., 1000000] kalau saya queryMin(999999, 999999) maka kamu akan looping 1 juta kali. Dan ini masih termasuk O( N ). Dalam hal ini, AVL tree, B-Tree, RB-Tree, etc-Tree tidak akan menolong. Bener gak? mohon koreksi kalau saya salah ngerti. Tapi idenya sudah bagus, menggunakan BST. Hanya perlu di-improve supaya worst-case nya dipastikan O( log N ). BTW, saya senang ada yang suka algo di milis JUG :) Felix Halim 2008/6/9 viking leon <[EMAIL PROTECTED]>: > hehehe, maksudnya aku dapet tapi penjelasannya agak salah: > > kalau inputnya [1... 10000] malah lebih bagus > > semakin lempeng ke kanan semakin bagus buat cari bilangan terkecil :-) ... > karena pada dasarnya stelah ktemu struktur di kanan kita abaikan .... contoh > kalo cari query terkecil [1...10000] ktemu 1, cari di kiri null, maka > langsung stop dia alhasil O(1) > > kalau [10000 ... 1] nah ini bakal jadi big problem, bener anda bilang bukan > O(log n) lagi tapi bakal jadi O(n) > > tuk BST-nya supaya optimal (balanced on height) .... saya ada ide pake self > balancing BST entah mau pake AA tree, AVL tree, Red-Black Tree, dll .... > udah lupa semua algoritmanya tapi menurut aku pre-processnya bakal less > equal O(n log n) ... which is meeting the requirement. > > regards, > yohan > > --- On Mon, 6/9/08, Felix Halim <[EMAIL PROTECTED]> wrote: > > From: Felix Halim <[EMAIL PROTECTED]> > Subject: Re: [JUG-Indonesia] Kode menarik > To: jug-indonesia@yahoogroups.com > Date: Monday, June 9, 2008, 2:40 AM > > 2008/6/8 viking leon <[EMAIL PROTECTED] com>: >> preprocess bikin: >> - binary search tree (left selalu lebih kecil dari parent, kanan selalu >> lebih gede dari parent) >> tapi yang disimpan dalam binary tree adalah indexnya bkan valuenya >> >> untuk array ini: [2,4,1,3] >> BST value-nya: >> 2 >> / \ >> 1 4 >> / >> 3 >> BST indexnya: >> 0 >> / \ >> 2 1 >> / >> 3 >> tuk bikin BST dari array yang sudah ada kira2: O(n) > > Good answer! > > BST nya bagus, tapi ada kekurangan. > > Kalau input saya adalah > > A = [ 1, 2, 3, 4, .., 1000000 ] > > Maka BST kamu akan lempeng ke kanan :P > Pencarian Query nya akan jadi O ( N ) bukan O ( log N ) lagi. > >> searchnya kira2 = O(log n) > > Kalau konstruksi BST nya seperti diatas, maka statement itu tidak benar. > Bagaimana anda tweak BST nya supaya querynya guaranteed O ( log N ) ? > > Felix Halim > >
