Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[RoguelikeRazuka]

Hey I got to implement my custom C# binary search tree class (it's a home task) and now I'm experiencing some difficulties with the remove node method. First, it doesn't seem to work correctly when the node being removed appears to be the root node. Additionally, it breaks when some tries to remove a node that has both left and right child and they are leaf-nodes. Could someone help me fix these?

Here's the code:

http://pastebin.com/7jsPtukT

[Reelya]

 

Code: [Select]

                   BinarySearchTreeNode<T> successor = curr.Right;
                    BinarySearchTreeNode<T> successorPrev = curr.Right;
 
                    while (successor.Left != null)
                    {
                        successorPrev = successor;
                        successor = successor.Left;
                    }

                    successorPrev.Left = successor.Right;
 
                    successor.Left = curr.Left;
                    successor.Right = curr.Right;
There are a couple of issue with how you're reconnecting everything here. Successor correctly finds the left-most node on the right side, and successorPrevs find the one that's up one level and to the right of that one.

But if the actual first node (curr.Right) has no left-node, then there are issues, because successorPrev == successor == curr.Right, since the while loop is skipped.

Code: [Select]

successorPrev.Left = successor.Right;^ this would attach the right part of curr.Right onto it's left side. Which would potentially break the sorting of the tree, and replicates nodes. In all other cases, this would be fine.

Code: [Select]

successor.Left = curr.Left;^ this one is fine either way, because curr.Left is the untouched left-side of the tree, and we're attaching it to the left side of the one we want to place at the root. But note, because of the issue in the previous line, we could have lost the data that was attached there.

Code: [Select]

successor.Right = curr.Right;^ this is an amusing error, since now curr.Right.Right = Curr.Right. That means there's an infinite loop in the tree.

Probably have an if statement, and treat curr.Right differently if it just happens to be the actual successor.

[RoguelikeRazuka]

Oh well great thanks for your help. I suppose everything is fine now. But could you please check if I'm correct at this point? Haven't I missed something?

http://pastebin.com/sEMU06dP

[TheDarkStar]

I read about how a linked list is organized, so I decided to make a class that handles one. It's still missing a few really useful functions like adding/deleting nodes to/from specific points, but it has enough basic stuff to illustrate the point - it can append nodes, show its entire contents, and delete itself. I'm mostly wondering if I wrote a reasonable implementation - I think I did, but I might be missing something.

http://pastebin.com/M9FV1tik

[Reelya]

One issue is that appending on the end like that is slow, since you're searching the entire data structure each time. Consider having pointers for both the head and tail nodes.

You also seem to have quite a few if statements that aren't needed, since they would be compensated for anyway. The whole thing can be sped up and simplified a lot.

e.g. you're creating a node for "head" in the constructor, but then checking "if (head == null)" in several functions, which can never happen. Maybe there's some advantage to declaring a dummy head node like that and never needing to check for head being null, but I'm not sure.

[Gentlefish]

...Bluh. Figured out (mostly) how to reduce a matrix to RREF through the magic of code. I still end up with a line of nan and a bunch of -0's but it reduces everything just fine and dandy.

[RoguelikeRazuka]

Hey could someone check please what I'm doing wrong (C#)? I'm trying to serialize a BinarySearchTree instance to an xml file but I'm always getting merely this: http://pastebin.com/NURCssXj
Deserializing does not work either (just getting a BinarySearchTree with a null root node)

Here's the full code:

http://pastebin.com/pfk53s2V



The SerializeToBinary function there as well as DeserializeFromBinary works the way it ought to.

[MagmaMcFry]

Give your tree and tree node classes the SerializableAttribute attribute.

[RoguelikeRazuka]

Give your tree and tree node classes the SerializableAttribute attribute.

You mean just replacing [Serializable] before the class declarations with [SerializableAttribute]? It does not help.

[RoguelikeRazuka]

I have sorted it out by adding a setter to the BinarySearchTreeClass Root property. 

[MagmaMcFry]

Further research tells me that the XmlSerializer only serializes public fields by default. It appears that making your fields public will do the trick just fine (and you only need [Serializable] for that), although making your fields public would not be good design.

Some other options: Either you use a DataContractSerializer writing to an XmlWriter, or you make your classes implement IXmlSerializable, or you just manually iterate over your tree and write to an XmlWriter. See over here for details.

E: okay

[Reelya]

Came across a new article which may be of interest to those learning to code:
http://www.devdungeon.com/content/i-know-how-program-i-dont-know-what-program
It's sort of more about how to look at things than anything technical however.

[Bumber]

Back to work on my raytracer. I didn't get it done by the deadline, but I'm still interested in making it work. I'm having trouble with smart pointers deleting themselves before I'm done using them.

Code: [Select]

std::shared_ptr<Image> render(int width, int height) const //the render function, part of the Scene class
{
    std::shared_ptr<Vector4> dir(new Vector4), origin(new Vector4);
    std::shared_ptr<SceneObject> hitobj;
    std::shared_ptr<Intersection> i;
    //irrelevant code here
    if (trace_ray(origin,dir,hitobj))
        i = hitobj->intersect(*origin,*dir);
    //more code
}

bool trace_ray(std::shared_ptr<Vector4> origin, std::shared_ptr<Vector4> dir, std::shared_ptr<SceneObject> hitobj) const
{
    bool hit = false;
    //irrelevant stuff
    hit = true;
    hitobj = _objects[x]; // _objects is a vector of std::shared_ptr<SceneObject>
    return hit;
}
As soon as the function returns, the shared pointer hitobj resets, even though I declared it in the render function. This causes the intersect to always fail, resulting in a blank scene.

There's a similar function that sets dir and origin. These work properly only when initialized as shown in the render function. Doing so inside the similar function leads to the same issue.

SceneObject can't be fixed in the same way. I tried setting up a dummy SceneObject, but the class doesn't support assignment. Even redirecting the pointer in the function, it just reverted to the dummy object after the function call.

[monkey]

Try passing hitobj by reference:
bool trace_ray(std::shared_ptr<Vector4> origin, std::shared_ptr<Vector4> dir, std::shared_ptr<SceneObject>& hitobj) const

Although I think you are not using shared_ptr correctly. There is no shared ownership here.
I don't understand why all the shared_ptrs, but you can assign one with reset().

[Bumber]

Try passing hitobj by reference:
bool trace_ray(std::shared_ptr<Vector4> origin, std::shared_ptr<Vector4> dir, std::shared_ptr<SceneObject>& hitobj) const

Although I think you are not using shared_ptr correctly. There is no shared ownership here.
I don't understand why all the shared_ptrs, but you can assign one with reset().

I'll try after finals week. I've tried SceneObject&, but it caused issues with "hitobj = _objects[x];". The reason for all the shared pointers is to handle automatic deletion of objects, and because that's how the instructor had set up the classes.