algorithm - Counting number of nodes in a complete binary tree -


i want count number of nodes in complete binary tree can think of traversing entire tree. o(n) algorithm n number of nodes in tree. efficient algorithm achieve this?

suppose start off walking down left , right spines of tree determine heights. we'll either find they're same, in case last row full, or we'll find they're different. if heights come same (say height h), know there 2h - 1 nodes , we're done.

otherwise, heights must h+1 , h, respectively. know there @ least 2h - 1 nodes, plus number of nodes in bottom layer of tree. question, then, how figure out. 1 way find rightmost node in last layer. if know @ index node is, know how many nodes in last layer, can add 2h - 1 , you're done.

if have complete binary tree left height h+1, there between 1 , 2h - 1 possible nodes in last layer. question how determine efficiently possible.

fortunately, since know nodes in last layer filled in left right, can use binary search try figure out last filled node in last layer is. essentially, guess index might be, walk root of tree down leaf should be, , either find node there (so know rightmost node in bottom layer either node or right) or don't (so know rightmost node in bottom layer must purely right of current location). can walk down kth node in bottom layer should using bits in number k guide search down: start @ root, go left if first bit of k 0 , right if first bit of k 1, use remaining bits in corresponding manner walk down tree. total number of times we'll o(h) , each probe takes time o(h), total work done here o(h2). since h height of tree, know h = o(log n), algorithm takes time o(log2 n) time complete.

i'm not sure whether it's possible improve upon algorithm. can ω(log n) lower bound on correct algorithm, though. i'm going argue algorithm correct in cases must inspect rightmost leaf node in final row of tree. see why, suppose there's tree t algorithm doesn't this. let's suppose rightmost node algorithm inspects in bottom row x, actual rightmost node in bottom row y, , leftmost missing node in bottom row algorithm detected z. know x must left of y (because algorithm didn't inspect leftmost node in bottom row) , y must left of z (because y exists , z doesn't, z must further right y). if think algorithm's "knowledge" @ point, algorithm has no idea whether or not there nodes purely right of x or purely left of z. therefore, if give modified tree t' deleted y, algorithm wouldn't notice had changed , have same execution path on t , t'. however, since t , t' have different number of nodes, algorithm has wrong on @ least 1 of them. inspecting node takes time @ least ω(log n) because of time required walk down tree.

in short, can better o(n) above o(log2 n)-time algorithm, , might able better that, though i'm not entirely sure how or whether that's possible. suspect isn't because suspect binary search optimal way check bottom row , lengths of paths down nodes you'd probe, after taking account share nodes in common, θ(log2 n), i'm not sure how prove it.

hope helps!


-

Comments

Post a Comment

Popular posts from this blog

OpenCV OpenCL: Convert Mat to Bitmap in JNI Layer for Android -

there several posts converting mat bitmap using utils.mattobitmap() function. i'm assuming function can called in java layer after importing utils class. i want transfer data memory address pointed uint32_t* bmpcontent; in code below. jniexport void jnicall java_com_nod_nodcv_nodcvactivity_runfilter( jnienv *env, jclass clazz, jobject outbmp, jbytearray indata, jint width, jint height, jint choice, jint filter) { int outsz = width*height; int insz = outsz + outsz/2; androidbitmapinfo bmpinfo; if (androidbitmap_getinfo(env, outbmp, &bmpinfo) < 0) { throwjavaexception(env,"gaussianblur","error retrieving bitmap meta data"); return; } if (bmpinfo.format != android_bitmap_format_rgba_8888) { throwjavaexception(env,"gaussianblur","expecting rgba_8888 format"); return; } uint32_t* bmpcontent; if (androidbitmap_lockpixels(env, outbmp,(void**)&bmpcontent)
Read more

python - How to remove the Xframe Options header in django? -

i have made page has iframe . inside iframe want show multiple different links article facebook, or news, or youtube video or other possible url. but, due xframe header, unable so. referred following link: https://docs.djangoproject.com/en/1.8/ref/clickjacking/ , django xframeoptionsmiddleware (x-frame-options) - allow iframe client ip but didn't help. my settings.py file's middleware_classes is: middleware_classes = ( 'django.contrib.sessions.middleware.sessionmiddleware', 'django.middleware.common.commonmiddleware', 'django.middleware.csrf.csrfviewmiddleware', 'django.contrib.auth.middleware.authenticationmiddleware', 'django.contrib.auth.middleware.sessionauthenticationmiddleware', 'django.contrib.messages.middleware.messagemiddleware', 'django.middleware.clickjacking.xframeoptionsmiddleware', ) from http://django-secure.readthedocs.org/en/latest/middleware.html , found using
Read more

android - org.xmlpull.v1.XmlPullParserException: expected: START_TAG {http://schemas.xmlsoap.org/soap/envelope/}Envelope -

i trying hit soap api in application login purpose , getting above mentioned error , can 1 tell me going wrong , first time soap apis. here code hit soap :- vector<object> args = new vector<object>(); hashtable<string, object> hashtable = new hashtable<string, object>(); hashtable.put("email", "mss.siddhart28@gmail.com"); hashtable.put("password", "siddharth"); args.add(hashtable); soapserializationenvelope envelope = new soapserializationenvelope( soapenvelope.ver11); envelope.dotnet = true; envelope.xsd = soapserializationenvelope.xsd; envelope.enc = soapserializationenvelope.enc; (new marshalhashtable()).register(envelope); httptransportse androidhttptransport = new httptransportse( "http://tempuri.org/", 15000); androidhttptransport.debug = true; string result = ""; try { soapobject request = new soapobject("http:
Read more