C++ tree AVL balance -


i've run in issue balance part of tree. have checkbal called after recursive insertion. if try add 5, 2 , 4 checks balance of 2 , continues 5 goes rotateleft part of right rotate correct. rotateleft function errors on second line.

what wrong implementation? i've searched on , compared did way people talk how it's done. got working. forgetting set n k @ end.

//============================================================================== //===== set balance ============================================================ snode<t>* checkbal(snode<t> *locroot) {     // make sure check children balanced well.     if (locroot->left != null)         locroot->left = checkbal(locroot->left);     if (locroot->right != null)         locroot->right = checkbal(locroot->right);      if(getheight(locroot->left) - getheight(locroot->right) > 1)     {         if(getheight(locroot->left->right) > getheight(locroot->left->left))             locroot->left = rotateright(locroot->left);         locroot = rotateleft(locroot);     }     else if(getheight(locroot->right) - getheight(locroot->left) > 1)     {         if(getheight(locroot->right->left) > getheight(locroot->right->right))             locroot->right = rotateleft(locroot->right);         locroot = rotateright(locroot);     }     updateheights(locroot);     return locroot; }     /*         extream cases of balancing tree requires double rotation                          \               d              /             b          'a' current root         if right->left (grandchild) larger right->right (grandchild)         first right rotate child left rotate parent           left > right 2 or more             left.left < left.right  (double right rotation)             left.left >= left.right (single right rotation)         right > left 2 or more             right.right < right.left (double left rotation)             right.right >= right.left (single left rotation)     */  snode<t>* rotateright(snode<t> *n) const { /*       n           k      / \         / \    (a)  k  =>   n  (c)        / \     / \      (b) (c) (a) (b) */     // k going our new parent     // move (c) k->right n->left     // set k->right n     // return new parent node update 1 above.     snode<t> *k = n->right;     n->right = k->left;             k->left = n;     return n = k; } 

rotateright(locroot->left);

should be, 

rotateright(locroot->right);

but it's still wrong implementation. =p

should have different implementation left side of root , right side.
try wikipedia animation.


Comments

Post a Comment

Popular posts from this blog

java - Play! framework 2.0: How to display multiple image? -

i need display gallery of photos. here template: @(photos: list[photo]) @title = { <bold>gallery</bold> } @main(title,"photo"){ <ul class="thumbnails"> @for(photo <- photos) { <li class="span3"> <a href="#" class="thumbnail"> <img src="@photo.path" alt=""> </a> </li> } </ul> } and here controller method: public static result getphotos() { return ok(views.html.photo.gallery.render(photo.get())); } and here photo bean : @entity public class photo extends model { @id public long id; @required public string label; public string path; public photo(string path, string label) { this.path = path; this.label = label; } private static finder<long, photo> find = new finder<long, photo>( long.class, photo.class); public static list<phot...
Read more

gmail - Is there any documentation for read-only access to the Google Contacts API? -

i want read-only access user's google contacts. there stackoverflow member wanted this, , received following answer : yes, there is, use https://www.googleapis.com/auth/contacts.readonly scope , "view contacts". this exchange reference read-only access google contacts can find using google. simply using access token obtained attempt read usual google contacts api (i.e. https://www.google.com/m8/feeds ) fails insufficient permissions. similarly, using google contacts api on new target fails 404 errors (for example https://www.googleapis.com/auth/contacts.readonly/default/full ). is there documentation anywhere on how use api, or permissible way access google contacts api full read-write access?
Read more

php - Controller/JToolBar not working in Joomla 2.5 -

relevant code: jtoolbarhelper::custom('savecategories', 'save', '', 'save', false, false); ... <input type="hidden" name="controller" value="easyblogcontroller"> according can dig docs , own previous questions, should call savecategories() function in easyblogcontroller . i've tried setting value easyblog , easyblog.php (file name) current easyblogcontroller (class name). clicking on save button refreshes page. not redirect, echo or var_dump test code put in savecategories() function. var_dump ing jrequest::getvar('controller') , 'task' return correct values. creating controller object , using $controller->execute('task'); works. the values going depend on location of controller trying call, , have couple options here. typically there controller in base folder of component (likely components/com_easyblog) in file called controller.php , class name inside ...
Read more