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...
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
yeah they are similar ok... i'll post the function shortly....
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.Originally Posted by std10093
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
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"
