Quadtree manipulation in Erlang - Will editing a quadtree record invalidate the parent?

Question

So this question is theoretical and I am wondering mainly how this scenario would turn out for our theoretical quadtree.

The tree itself is a record with objects, bounds and children. The children, as of now, are other quadtree records. So, it's going to be a big structure depending on how many splits are done.

If lets say I want to delete an object in a subtree of level 3. Would that properly save the parent, and its parent? If I would write something like this:

Quad#quad{objects = ListWithoutSaidObject}.

without actually doing recursion in a way where the function call would save the result of the above line in the appropriate child variable? Like this:

delete_object(Quad, ObjectToDelete) ->
    <nice code to find proper child if not present in current>
    Quad#quad{child = delete_object(Quad#quad.child, ObjectToDelete)}.

where delete_object returns the same quadtree without said object if it was in that tree, otherwise it keeps digging until it finds the tree containing the object it is supposed to remove. When found it deletes it, and returns the new child tree.

This is no tailrecursion and as far as I know this is how I need to do it to not mess the tree up. Am I wrong? I thought if I implemented each tree as a separate process and stored their pids in each tree and saved the parents as well, I could do this more efficiently.

As I don't have any code yet I can't give examples. I'm asking so I know before I implement it which way I shall do this.

Answer 1

Erlang data structures are immutable, so you can't mutate a sub tree without getting a new copy of the original tree. The copy will be sharing as much as possible with the original tree -- which it can only because of said immutability -- so this might sound worse as it is in practice.

Besides not having to worry about messed up data structures it also gives you the possibility of using the old and the new tree at the same time.

In your example you therefore do need the recursion, if this gets bothersome you could build a higher order function to do the recursing and pass it whatever you want to do to the children as a parameter fun.

Answer 2

In addition to the answer of Peer Stritzinger:

Quadtrees are generally not very suitable for deletion.