Hint : pake pohon2an :D hehehehe S******* Tree
btw kalo datanya ga berubah2, bisa lbh bagus lg, pre processing O(N log N) dan
query O(1)
Felix Halim <[EMAIL PROTECTED]> wrote: 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
>
>
