yah bener gara gara reply ini saya jadi ikutan nimbrung maklum lg search sebuah value dalam tree tiap kali refresh
ini akan jadi core feature di dalam cimande http://www.jroller.com/fthamura/entry/cimande_update_security_hole maklum feature ini sudah build in di cimande 1.2.3.2 tap saya melihat tree interceptor ini sebuah methode yang rakus memory makanya saya lg cari metode lain 2008/6/9 viking leon <[EMAIL PROTECTED]>: > 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 <[EMAIL PROTECTED]>>: > >> 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 > > > > -- -- Frans Thamura Director of Meruvian Education, Consulting, Networking, Profesional Marketplace, OpenSource Development and Implementation Mobile: +62 855 7888 699 YM: [EMAIL PROTECTED] Linkedin: http://www.linkedin.com/in/fthamura Join jTechnopreneur Program @ jtechnopreneur.com
