dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 8 of 8

Thread: binary search tree

  1. #1
    Join Date
    May 2018
    Posts
    92

    binary search tree

    I need help because I'm not able to write code for this exercise:

    I have binary search tree where every node has label of integer type.
    Node is said even (odd) type if its label is even (odd).
    For every node X, which is not leaf, It's defined D as maximum distance among X and one of its leaves of the same type.
    If subtree X doesn't contain any leaves of the same type, D=-1.
    It's necessary to write code for procedure with complexity at maximum O(n) to calculate D for every node, which is not a leaf.

    i tried several times unsuccessfully.

  2. #2
    VictorN's Avatar
    VictorN is offline Super Moderator Power Poster
    Join Date
    Jan 2003
    Location
    Hanover Germany
    Posts
    19,456

    Re: binary search tree

    Quote Originally Posted by zio_mangrovia View Post
    I need help because I'm not able to write code for this exercise:
    ...
    i tried several times unsuccessfully.
    And how did you try it? And what went wrong?
    Victor Nijegorodov

  3. #3
    Join Date
    May 2018
    Posts
    92

    Re: binary search tree

    Quote Originally Posted by VictorN View Post
    And how did you try it? And what went wrong?
    I don't find to think the way using recursion to keep track of node type to compare, for example, to every leaf (which are at several levels)
    I think It's easy if I have to calculate this Properties only for father of every leaf but not for the other top nodes

  4. #4
    Join Date
    Feb 2017
    Posts
    465

    Re: binary search tree

    1. The tree is recursively traversed once.

    2. Whenever a leaf is reached a return record R is filled in. It's then passed down when the recursion winds back toward the root.

    3. The return record initially looks like this,
    Code:
    struct R {
       int odd = -1;
       int even = -1;
    };
    The odd and the even numbers indicate distance D for each type. -1 means no distance exists yet.

    4. At an odd leaf the record is set to,
    Code:
    struct  R {
       int odd = 0; // 0 distance so far
       int even = -1; // no distance exists
    };
    At an even leaf it's the other way around, even is set to 0 and odd to -1.

    5. When a parent node is reached the records from the children are updated and merged. How to do it requires some thinking on your part! Then the D of the node is set based on the info in the merged record. It also requires some thinking. Finally the merged record is returned (to the parent thanks to the recursion winding back).

    6. After one tree traversal all D have been set which indicates O(N) complexity.
    Last edited by wolle; September 11th, 2019 at 10:37 AM.

  5. #5
    Join Date
    May 2018
    Posts
    92

    Re: binary search tree

    Quote Originally Posted by wolle View Post
    ...

    When a parent node is reached the records from the children are updated and merged. How to do it requires some thinking on your part! Then the D of the node is set based on the info in the merged record. It also requires some thinking. Finally the merged record is returned (to the parent thanks to the recursion winding back).
    you can't imagine how much you helped me to understand problem.
    I thought to this procedure and it Works.... after 2 daysssss

    Code:
    struct node {					// D is max dist. from node to leaf of same type
    	int label;					// -1 means there is no leaf of same type of node
    	int D;					
    	int leaf;                                     // leaf is flag, 1: leaf 0: not leaf 
    	node *left, *right;		
    	node(int inf): label(inf), D(-1), leaf(0), left(NULL), right(NULL) {};
    };
    
    struct leafstate {
    	int even_sx;
    	int even_dx;
    	int odd_sx;
    	int odd_dx;
    	leafstate(): even_sx(-1), even_dx(-1), odd_sx(-1), odd_dx(-1) {};
    };
    
    vector<int> final;
    
    void calcolaD(node *tree, int &even, int &odd) {
    	leafstate lf;
    	if (!tree)
    		return;
    	if (tree && !tree->left && !tree->right && tree->label%2==0) { // even leaf
    		tree->leaf=1;
    		++even;
    		return;
    	}
    	if (tree && !tree->left && !tree->right && tree->label%2==1) { // odd leaf
    		tree->leaf=1;
    		++odd;
    		return;
    	}
    	calcolaD(tree->left, lf.even_sx, lf.odd_sx);		// get even-odd values
    	calcolaD(tree->right, lf.even_dx, lf.odd_dx);	// from sons
    	if ( lf.odd_dx != -1 )
    		++(lf.odd_dx);
    	if ( lf.even_dx != -1 )
    		++(lf.even_dx);
    	if ( lf.odd_sx != -1 )
    		++(lf.odd_sx);
    	if ( lf.even_sx != -1 )
    		++(lf.even_sx);
    	even = max(lf.even_sx, lf.even_dx);
    	odd = max(lf.odd_sx, lf.odd_dx);
    
    	if ( tree->label%2 == 0 )
    		tree->D = even;
    	else 
    		tree->D = odd;
    	if (!tree->leaf)
    		final.push_back(tree->D);     // I put values into vector, excluded leaves, because It's required by problem.
    }
    
    int main() {
    	node* abr = NULL;
    	int e, o;
    	e = o = -1;
    	if ( abr )
                calcolaD(abr, e, o);
    }
    What do you think?

  6. #6
    Join Date
    May 2018
    Posts
    92

    Re: binary search tree

    Code:
    final.push_back(tree->D);
    This statement doesn't change algorithm complexity, right? It's O(1), right?

  7. #7
    Join Date
    Feb 2017
    Posts
    465

    Re: binary search tree

    Quote Originally Posted by zio_mangrovia View Post
    This statement doesn't change algorithm complexity, right? It's O(1), right?
    You're right. Adding something at the end of an std::vector is an O(1) operation (*) so this won't change the overall O(N) complexity of the algorithm even if you do it each time you have a new D.

    Just a remark. There's a slightly different way of doing it and that's to make a function out of calcolaD. It would look like this,
    Code:
    struct leafstate { 
    	int even;
    	int odd;
    	leafstate(): even(-1), odd(-1) {};
    };
    
    leafstate calcolaD(node *tree); // signature
    So instead of returning values as output parameters int &even and int &odd you return these values by way of returning the leafstate struct as a calcolaD function value instead.

    This will make your code look somewhat cleaner and simpler and it would be more in line with what is generally expected. If it's a graded exercise I suppose it will improve your chances of getting a high grade especially if your professors are traditionalists.

    (*) But this O(1) is on average (or amortized as it's also called). If you have reason to believe this distinction matters it's safest to break the collection of the D values out of calcolaD and do it in a separate function which traverses the tree once more. Then calcolaD itself will be solid O(N).
    Last edited by wolle; September 13th, 2019 at 04:05 AM.

  8. #8
    Join Date
    May 2018
    Posts
    92

    Re: binary search tree

    Quote Originally Posted by wolle View Post
    This will make your code look somewhat cleaner and simpler and it would be more in line with what is generally expected. If it's a graded exercise I suppose it will improve your chances of getting a high grade especially if your professors are traditionalists.
    Good idea, I'll try again to write code according to your suggestion.
    Thanks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)