Replace node in immutable tree
I have a tree structure akin to this:
I wanna have a method
Tree ReplaceNode(this Tree tree, Node oldNode, Node newNode) to replace nodes in this tree (i.e. return a new tree with a node replaced), but I have no idea how to do this efficiently. Is there some common algorithm or something for this?11 Replies
Well without having any idea about the position, just the object, you need to traverse the entire tree
Can this node be anywhere, or is there bigger chance it will be in some spot in the tree?
Could be anywhere
The main issue is that I also have to replace the node(s) in the
Nodes dictionary (which contains all nodes in the entire tree) as well as in the actual nodes.Can you edit the dictionary? So you would also store the position in the tree?
That would make it much easier and faster
Idk how I would store the position in the tree
Wait a sec, let me find a diagram
Nvm didnt find what i was looking for, but im pretty sure there is some standard notation for the nodes, so you can search the tree quick
https://en.wikipedia.org/wiki/Search_tree i think this is what i thought is used
Search tree
In computer science, a search tree is a tree data structure used for locating specific keys from within a set. In order for a tree to function as a search tree, the key for each node must be greater than any keys in subtrees on the left, and less than any keys in subtrees on the right.The advantage of search trees is their efficient search time ...
Or you could hold a pointer to the node in the tree in the dictionary, that would be probably easyer as i think about it
Hmm, right
Did it work?
If the tree is immutable you must duplicate the tree
If your just asking how to replace a node that's pretty simple
Find the node, point new node to children , then point parent to newnode
Done
Unless it's a bst, heap etc where you have to rebalance
Right