2008/6/8 viking leon <[EMAIL PROTECTED]>: > 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
