Considering how to efficiently store and update data for a tree, let's think about a common scenario like a virtual dom in React.
One way to store a tree representing a dom in JSON format could look like this:
{
nodeId: 'nodeId1',
...nodeData,
childrenNodes: [
{
nodeId: 'nodeId2',
...nodeData,
childrenNodes: [...]
},
...
]
}
Now, we would typically traverse the tree using either BFS or DFS (React uses DFS) to locate a specific element for modification.
Alternatively, we could store the same tree in a hash table-like structure:
{
nodeId1: {...nodeData, childrenNodes: [nodeId2]},
nodeId2: {...nodeData, childrenNodes: [nodeId3, nodeId4]},
...
}
In this setup, retrieving a specific node could be O(1) since we can directly access nodes by their ids without traversing the entire tree.
When dealing with a large number of elements in a virtual dom, choosing one storage method over the other may not make much difference. However, having both structures simultaneously might not be ideal due to memory constraints, especially on older devices.
If each node has a unique id and there are references from child nodes to their parent, adding and removing nodes should be straightforward regardless of the chosen structure.
The ultimate decision is whether a general-purpose approach should be used or if a combination of both structures would be more efficient for rapid updates. Building a framework from scratch might benefit from incorporating both methods based on different use cases, but resource limitations on certain devices must also be considered.