4

Let's say you are engineering a chat room software.

let client = new Client();
let room = rooms.FindRoom();
room.addClient(client);

This room (parent) now has a client (child).

client.on('message', (event) => {
   // With the above code, room must be found
   let room = rooms.FindClientsRoom(client);
   if(room){
       room.handleMessage(event);
   }
});

Or we have a child that knows about its parent

let client = new Client();
let room = rooms.FindRoom();
room.addClient(client);
client.setRoom(room);


client.on('message', (event) => {
   let room = client.getRoom();
   if(room){
       room.handleMessage(event);
   }
});

This is incredibly fast compared to looking for a client within 1000s of rooms. But is there something wrong with the design pattern? In any system, such as XML, do child nodes know about their parents? Should they?

| improve this question | |
  • 3
    For what it’s worth, the web’s DOM model lets you do this, with Element.parentNode. – JW01 23 hours ago
  • The efficient version of rooms.FindClientsRoom would be to have a map of client to room. That shouldn't be much slower than storing the room on the client. I assume it's slow now because you're looping over all rooms. – Bernhard Barker 9 hours ago
31

Your question is basically the same as "should linked list items have a reference to the previous item?", and the answer is the same: it depends. There are use cases when a singly-linked list is correct, and there are use cases when a doubly-linked list is correct.

The important point here is that it is the use case that matters, not the format: XML does not specify whether child nodes know about their parents, that is a matter of the design of the parser which reads the XML and creates in-memory data structures for it. Some parsers will do this, other ones won't.

If you need a quick lookup from your child nodes to the parent nodes, then put it in. If you don't, Keep It Simple S... and don't have them.

| improve this answer | |
  • 3
    I wouldn't say a linked-list is quite the same, as with that all nodes are the same type (even if the data stored in the node can be of different types), whereas here you could have different types and you'd be coupling those types together more strongly by having one contain a reference to the other. It also depends how you use that reference, of course. – Bernhard Barker 9 hours ago
  • 1
    @BernhardBarker Considering that headers and footers and NULL can often not be the same type of node, I'd say your comment isn't fully accurate. Regardless, the point still stands - you need a reference to next but do you need a reference to prev? Well, it depends on whether what you're doing. – corsiKa 2 hours ago
3

In most tree models you want to know the parent of nodes, you will likely have a use case for it. You already mentioned your own use case and keeping track of parents is cheap so it is a no-brainer.

In other tree applications you typically want the node to be able to tell you its path, and its level (or depth). For this you also need the parent. It is a common thing to take onboard for tree nodes.

| improve this answer | |
  • "keeping track of parents is cheap" - until somebody handcrafts the code to do this in a multi-threaded environment and the subtle bugs cause data corruption... – Philip Kendall 11 hours ago
  • @PhilipKendall Whether the tree is a UI control or a document or something else, in a multi-threaded context you would have to marshall any action on the tree to the appropriate thread. Adding a parent property would not change that. So I am afraid I do not understand your point. – Martin Maat 9 hours ago
  • 1
    "marshall any action on the tree to the appropriate thread" - that's a brute force way of doing it. With careful locking of the appropriate parts of the data structure, you don't need to do all your actions on one thread. But my point is really that people try to do this and get it wrong, and when you're dealing with bidirectional links there's a lot more opportunity to get it wrong than if you're updating unidirectional links. – Philip Kendall 8 hours ago
3

Personally, I think the first pattern you showed to be a mistake. As you pointed out, it takes a lot of time to find the room.

The general problem with the second pattern is that it makes reference counting garbage collection fail. (This issue varies by language.)

What you missed is that there is a third pattern. Specifically, that the events to the client can identify the room. This works well if the events are coming from the room. It doesn't work well if the events are from an unrelated external source.

You might also want to consider if a client can be associated with multiple rooms.

| improve this answer | |
1

If you're doing this on a chat server application, then you should use a database. The most common database design for a tree is that parents do not have references to their children, only the child have foreign key reference to their parents. Instead, the parent to child relation should be handled by an index.

If you're doing this in a chat client application, then don't worry too much about it. Even the heaviest chat software users aren't going to have more than hundred room or so simultaneously, don't worry about performance and pick the simplest implementation that makes your life and future maintenance easy rather than worrying about negligible performance differences.

| improve this answer | |
1

Trees are used for a variety of purposes, some of which are facilitated by having child nodes hold parent pointers, and some of which would require that child nodes not have parent pointers.

If child nodes have references to their parents, than a reference to a child can effectively identify both a tree and location within it. On the other hand, making a snapshot of a tree's state will require making a copy of all the nodes therein.

If tree nodes are immutable, and modifications to a tree are performed by producing a modified tree node and replacing referencces to the original with references to the modified version, then code may take a snapshot of a tree merely by copying a reference to its current root node.

Each approach is excellent for some purposes, but will work poorly for some others. Depending upon what you're doing with trees, either approach may work better. Alternatively, it may be useful to use a hybrid approach in which every tree node object is either referenced by exactly one tree, or will never be modified. I can't think offhand of situations where it would be useful for non-shared nodes to have parent references, but they could do so.

| improve this answer | |
1

In general terms, you're adding an edge connecting Client and Room.

If this is a real world example, this is a poor model to make it a parent-child relationship. As others have pointed out, you may have to extend it to multiple client-room relationships which breaks a single back-pointer from Child -> Room.

This may seem wildly unrealistic but, say someone has more than one chat window open - they are now in more than one room at a time.

Even if you were modeling physical presence, a booking system would have to cope with the person who books more than one room on behalf of others (common) or books a long slot for one room whilst in the middle having an overlapping short use of another.

In-memory you can model such edges as a hash key in a dictionary that is a combination of client + room ID. This would continue to be a fast lookup.

That approach also extends easily to databases adding such records with a composite key.

It has a secondary benefit that you can save these edge records over time, showing a history of the relationships.

| improve this answer | |
0

Adding new fields requires more memory. The difference between the first and second approach is more CPU vs more RAM usage. As they can be a tradeoff, need to decide which one to optimize depending on the application.

| improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.