ow cara searchnya ada di postingan lama sih ... saya post lagi dibawah, maaf
kalo tulisannya acak2an ........
Re: [JUG-Indonesia] Kode menarik
sory double posting keteken send waktu gambar2 BStnya
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)
searchnya pake algo kira2 begini:
- 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)
jadi tuk search:
queryMin( 0, 3 ) =
- ktemu 0, keep on searching left
- ktemu 2 keep on searching left which is null
so hasilnya = 2
queryMin( 1, 1 ) =
- 0, belum ktemu cari kiri
- 2 belum ktemu kiri, kanan ga ada
- recursif back to 0, kanannya 1
- 1 ktemu, cari kiri null
hasil = 1
queryMin( 1, 2 ) = 1
- 0 belum ktemu, cari kiri
- 2 ktemu cari kiri, null
hasil=2
queryMin( 0, 1 ) = 2
- 0 ktemu, keep kiri
- kiri = 2, tidak ada di index balek ke parent
hasil = 0
queryMin( 3, 3 ) =
- 0 belum ktemu cari kiri
- kiri =2 tidak ada di index balek parent search kanan
- 1 belum ktemu cari kiri = null
- cari kanan, ktemu =3, keep kiri = null
- hasil = 3
searchnya kira2 = O(log n)
masalah search kanan aja mungkin maksudnya kiri saja, tree bagian kanan stelah
ktemu bisa diabaikan .... karena pada dasarnya untuk mencari bilangan terkecil,
bagian kiri selalu lebih kecil dari parent sedangkan bagian kanan selalu lebih
besar dari parent, jadi kalo sudah dapat parentnya engga perlu lagi untuk
mencari disbelah kanan karena sudah pasti lebih besar.....
tentang log n, ini maksudnya waktu untuk mencari sebuah node dalam BST kira2
sebanding dengan height/tinggi dari tree tersebut. tinggi sebuah BST yang
balance kira2 adalah log n.
regards,
yohan
--- On Mon, 6/9/08, Frans Thamura <[EMAIL PROTECTED]> wrote:
From: Frans Thamura <[EMAIL PROTECTED]>
Subject: Re: [JUG-Indonesia] Kode menarik
To: jug-indonesia@yahoogroups.com
Date: Monday, June 9, 2008, 6:57 AM
2008/6/9 viking leon <[EMAIL PROTECTED] com>:
mungkin agak kebalik bukan arraynya merepresentasikan tree tetapi arraynya
direpresentasikan dalam tree. Tapi yang disimpan oleh treenya hanya index dari
array tersebut (value sesungguhnya tetap di array) ..... setelah index dari
bilangan terkecil ditemukan dengan melakukan search pada tree, selanjutnya
indexnya perlu di lookup ke arraynya untuk mengetahui bilangan sesungguhnya.
array dirubah jadi tree, emang harus adaindex, saya sih pake satu dimensi
iparent untuk melakukannya
tapi gimana searchnya
diatas dijelaskan log untuk search bisa kanan saja
ini gimana yah
