Problem with my Rb tree

This is a discussion on Problem with my Rb tree within the C Programming forums, part of the General Programming Boards category; i have just written a c implementation of a red black tree. this runs but not perfectly ..each time i ...

  1. #1
    Registered User
    Join Date
    Nov 2011
    Location
    Douala, Cameroon
    Posts
    187

    Angry Problem with my Rb tree

    i have just written a c implementation of a red black tree. this runs but not perfectly ..each time i try to insert a new element into one of the child nodes it shows only at the root... this has given me some real headache for some time now... i wish some one could give me a tip on how to debug this.. code really long about 800 lines across different files making it harder...

  2. #2
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,675
    I have not meet a RB tree,but i guess it is pretty similar with the AVL..I think you should post the insertion function at least

  3. #3
    Registered User
    Join Date
    Nov 2011
    Location
    Douala, Cameroon
    Posts
    187
    yeah they are similar ok... i'll post the function shortly....

  4. #4
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Posts
    307
    Quote Originally Posted by std10093 View Post
    I have not meet a RB tree,but i guess it is pretty similar with the AVL.
    Having implemented both an AVL tree and a RB tree, I can say that the AVL tree was MUCH MUCH simpler than the RB tree, especially for deleting a node. For instance, in the RB tree you have 6 or 7 cases (can be reduced to 3 using case-reduction) for deletion, and 3 for insertion and all the cases are different. For AVL tree, you have 3 cases for both insertion and deletion and they are almost exactly the same.

    Also, doing some simple timing tests, the AVL tree outperformed the RB tree for search and insert, and was only very slightly slower for deletion; not enough to justify the complexity of the RB tree, IMO.
    GCC on Fedora Core 10

  5. #5
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,675
    Quote Originally Posted by MacNilly View Post
    Having implemented both an AVL tree and a RB tree, I can say that the AVL tree was MUCH MUCH simpler than the RB tree, especially for deleting a node. For instance, in the RB tree you have 6 or 7 cases (can be reduced to 3 using case-reduction) for deletion, and 3 for insertion and all the cases are different. For AVL tree, you have 3 cases for both insertion and deletion and they are almost exactly the same.

    Also, doing some simple timing tests, the AVL tree outperformed the RB tree for search and insert, and was only very slightly slower for deletion; not enough to justify the complexity of the RB tree, IMO.
    Well,i do not know.I just saw on google that is a self-balancing tree,that's why i guessed so.Guessing however,is not a good thing.Thank you for your input

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,292
    Lately I would adopt more of a TDD approach with this.
    But seeing as you now have some code, what I would do is I would make little test cases to try and isolate in what cases it does not work.
    Get or create some kind of test framework. You can probably write something that does the job in about 5 minutes, if you can't be bothered finding something else and learning to use it. You just need something that exercises the code for you and gives you pass/fail results.

    Write a function that verifies the state of the tree and call it after every operation that modifies the tree. This function should check for two incorrectly connected red nodes, the tree ordering, and count the number of black nodes from the root to each leaf, making sure they are the same throughout. That sort of thing. Make those separate functions if you need to.

    Start with the realy simple and small cases. Starting with an empty tree:
    Insert one node...
    Insert two nodes, in ascending order...
    Insert two nodes, in descending order...
    Insert three nodes, in ascending, then descending, then middle-first orders...
    etc

    Check that the tree is valid after each insert.
    Every time you make a change, run through all of the test again to make sure you didn't break other cases.
    Where you have a bug for some test, try steping through the code.

    When you get really stuck, post here with information about exactly which test(s) are failing and the relevant portions of code etc.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Tree problem
    By ndrez in forum C Programming
    Replies: 8
    Last Post: 05-17-2011, 09:05 AM
  2. binary tree problem
    By masterg in forum C++ Programming
    Replies: 1
    Last Post: 12-07-2008, 12:16 AM
  3. binary tree problem
    By spank in forum C Programming
    Replies: 4
    Last Post: 04-24-2006, 05:27 AM
  4. Tree Problem
    By recluse in forum C Programming
    Replies: 36
    Last Post: 12-04-2004, 02:06 PM
  5. Binary tree problem
    By carrja99 in forum C++ Programming
    Replies: 4
    Last Post: 02-27-2003, 08:36 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21