Thread: randomized version generally doesn't work

  1. #1
    Registered User
    Join Date
    Oct 2002
    Posts
    69

    randomized version of program generally doesn't work...

    i made a second version of a red black tree program i was working on. the first version used a standard reading of the input file sequentially adding each city to the tree. this wasn't working very well since the file provided sorted input. the resulting tree was heavily skewed to the right because of this.

    in this version of the program, i read the input file into a vector and then randomly sampled from the vector for input to the tree until each item was used.

    for some reason i haven't been able to figure out, the program runs fine sometimes and crashes or infinite loops other times. when it lets me debug, it points me to the line:

    Code:
    void leftrotate(Ptr& root, Ptr& x)
    {
    	Ptr y=x->right;				//new Ptr y = right[x]
    
    	Ptr spare=x;
    
    	x->right=y->left;			//right[x]=left[y]
    i'll attach the cpp file, header file, and data file on here
    Last edited by talz13; 11-04-2003 at 08:04 PM.

  2. #2
    Registered User
    Join Date
    Oct 2002
    Posts
    69
    rename the data file extension to .dat from .txt

  3. #3
    Registered User
    Join Date
    Oct 2002
    Posts
    69
    and here's the header file

  4. #4
    Registered User
    Join Date
    May 2003
    Posts
    1,619
    Well, you SHOULD test on sequentuial data, because that is your worst-case scenario. And if you correctly are doing red-black balancing, your longest distance to a leaf should be at most twice the shortest distance.
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

  5. #5
    Registered User
    Join Date
    Oct 2002
    Posts
    69
    i understand that, but our algorithm book is really poorly constructed. both my teacher and i had the same problem with the tree going heavily to the right. i decided to make a random version to try and fix this, but it's not working so well right now

    i find it strange that once in a while it works perfectly, but other times it infinite loops or crashes... so i think it has something to do with the randomizing part

    (btw, this isn't a homework or anything, just some extra coding i was working on on top of the project)

  6. #6
    Registered User
    Join Date
    May 2003
    Posts
    1,619
    Define heavily to the right.

    If you get serious imbalance in a RB tree, your implementation of the insertion algorithm is probably wrong.
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

  7. #7
    Registered User
    Join Date
    Oct 2002
    Posts
    69
    heavily to the right meaning the root has a left and right child, the right child of the root has a left and right, and so on.

    my implementation of the algorithm we were given was right (at least according to the teacher, since she got the same problem). i'm not saying the algorithm we were given was flawless... do you know where i can find a different algorithm for insert and insert fixup?

  8. #8
    Registered User
    Join Date
    May 2003
    Posts
    1,619
    Well, is the resulting tree a valid red-black tree? That is, can you check that:

    * Every leaf is black.
    * If a node is red, then both its children are black.
    * Every simple path from a node to a descendant leaf contains the same number of black nodes.

    Do a tree recursal and print out the black height of each leaf. If they are not the same, your implementation is wrong. Also look for red nodes with red children.

    Also find the minimum and maximum height of leaves.

    If those three points are met, your tree is *not* heavily skewed. A RB tree with a min leaf height of 20 and a max of 40 (and all leaves with a black height of 20) is working properly.

    Your insert algorithm takes into account that the root node can change after an insert, and it properly updates the root *?
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. OpenGl Version
    By Nextstopearth in forum Game Programming
    Replies: 6
    Last Post: 11-26-2008, 07:56 AM
  2. No Version info tab in file properties?
    By cpjust in forum Windows Programming
    Replies: 2
    Last Post: 06-03-2008, 03:42 PM
  3. help getting program to work
    By jlmac2001 in forum C Programming
    Replies: 2
    Last Post: 11-13-2002, 11:04 PM
  4. DLL __cdecl doesnt seem to work?
    By Xei in forum C++ Programming
    Replies: 6
    Last Post: 08-21-2002, 04:36 PM
  5. Version info and ListBox
    By GaPe in forum Windows Programming
    Replies: 10
    Last Post: 03-28-2002, 12:08 AM