Change node in Scala class tree

Question

Suppose I have some tree structure using case classes, something like this:

abstract class Tree case class Branch(b1:Tree,b2:Tree, value:Int) extends Tree case class Leaf(value:Int) extends Tree var tree = Branch(Branch(Leaf(1),Leaf(2),3),Branch(Leaf(4), Leaf(5),6)) 

And now I want to create a method to change a node with some id to another node. It is easy to find this node, but I do not know how to change it. Is there an easy way to do this?

Answer 1

This is a very interesting question! As already noted, you must change the entire path from root to the node you want to change. Immutable cards are very similar, and you can learn something by looking at the Clojure PersistentHashMap .

My recommendations:

• Change Tree to Node . You even call this node in your question, so this is probably the best name.
• Pull value to base class. Once again, you are talking about this in your question, so this is probably the right place for him.
• In the replace method, make sure that if none of the Node and its children are changed, do not create a new Node .

Comments are given in the code below:

 // Changed Tree to Node, b/c that seems more accurate // Since Branch and Leaf both have value, pull that up to base class sealed abstract class Node(val value: Int) { /** Replaces this node or its children according to the given function */ def replace(fn: Node => Node): Node /** Helper to replace nodes that have a given value */ def replace(value: Int, node: Node): Node = replace(n => if (n.value == value) node else n) } // putting value first makes class structure match tree structure case class Branch(override val value: Int, left: Node, right: Node) extends Node(value) { def replace(fn: Node => Node): Node = { val newSelf = fn(this) if (this eq newSelf) { // this node value didn't change, check the children val newLeft = left.replace(fn) val newRight = right.replace(fn) if ((left eq newLeft) && (right eq newRight)) { // neither this node nor children changed this } else { // change the children of this node copy(left = newLeft, right = newRight) } } else { // change this node newSelf } } } 

Answer 2

Since your tree structure is immutable, you need to change the whole path from node to root. when you visit your tree, save the list of visited nodes, then update the entire node to the root using the copy method as suggested by pr10001 ..

Answer 3

copy method:

 val tree1 = Branch(Branch(Leaf(1),Leaf(2),3),Branch(Leaf(4), Leaf(5),6)) val tree2 = tree1.copy(b2 = tree1.b2.copy(b1 = Leaf(5)) // -> Branch(Branch(Leaf(1),Leaf(2),3),Branch(Leaf(5), Leaf(5),6))