wah kelupaan lagi searchnya hehehe bolong terus
engga tau boleh atau engga, biar bantu agar searchnya lebih cepet ... di BSTnya
satu node consist of index, dan valuenya:
cth:
>> BST value-nya:
>> 2
>> / \
>> 1 4
>> /
>> 3
>> BST indexnya:
>> 0
>> / \
>> 2 1
>> /
>> 3
jadinya
i:0|v:2
/ \
i:2|v:1 i:1|v:4
/
1:3|v:3
selama belum ktemu nodenya, bisa dicompare valuenya dengan node skarang ...
kalo lebih kecil cari di kiri, kalo besar cari di kanan..... dengan begini bisa
bener2 search pake binary search dalam sebuah BST.
misal mencari (3,3),
parent v=2
3>2
cari di kanan ktemu node 4
4>3
cari di kiri ktemu 3,
selanjutnya stelah node ktemu bisa cari berdasar index melulu.
--- 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, 12:09 PM
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] com>:
> 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] com>:
> 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 <felix.halim@ gmail.com> wrote:
>
> From: Felix Halim <felix.halim@ gmail.com>
> 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
>
>
