Updating a tree of selections

18 September 2012, by

Last time I discussed how to render a tree of selectable items in HTML, including partially-selected branches. This time I’m going to talk about initialising, maintaining and persisting this state from a selection tree.

This is actually all very straightforward once you’ve spotted the basic principles of how the tree works:

  • a non-leaf node is selected if-and-only-if all of its descendant nodes are selected
  • likewise a non-leaf node is de-selected if-and-only-if all of its descendant nodes are de-selected
  • therefore a non-leaf node with a mixture of selected and de-selected descendants is partially-selected.

An illustration of the three basic rules: selected if-and-only-if descendants are all selected, de-selected if-and-only-if all descendants are de-selected, partiaully-selected otherwise.

A corollary of the last point is that any node with an immediate child node that is partially-selected must itself be partially-selected itself, or that if a node is partially-selected then all of its ancestors to the root of the tree must themselves be partially-selected.

Therefore the simplest algorithms to run a tree of selections are as follows.

To update the tree with a new selection:

  1. Walk down the tree from the newly-selected node, selecting that node and all of its descendant nodes
  2. Walk up the tree from the selected node towards the root: update the selected node’s parent and each further ancestor for the new selection:
    1. if all immediate children of this node are selected, this node must be selected
      (equivalently you can use “if all descendants of this node are selected” if that is easier to compute, e.g. this can be easier to represent as a CSS selector depending on the construction of your tree)
    2. if all immediate children of this node are deselected, this node should be deselected
      (again, equivalently: “if all descendants of this node are deselected”)
    3. else we have a mix of selected and not: this node should be partially selected

    If this node is already correct then we can stop – no further updates will be required further up the tree.

An illustration of this process: users clicks on a node, mark the node and its descendants as selected, walk up the tree updating its parent nodes, result

The process for removing a selection is identical except you clear the selection from the node all descendants in the first step. The usual convention is that a click on a partially-selected node is treated as a selection not a de-selection.

To save the state of the tree, we need to store one of

  • the complete set of checked nodes throughout the tree
  • the set of checked leaf nodes
  • the set of nodes are the top of any completely selected sub-tree – this is the minimal set.

An example tree of selections and the three versions of state we can safe: all selected nodes, selected leaf-nodes only and the minimal set from the tops of completely selected sub-trees

plus perhaps also the expanded / collapsed state of every node on the tree. Which one you choose will obviously depend on what’s useful for your application that consumes the selection, but these will also behave subtly differently if you ever load the selection back into an expanded tree: new nodes added as children or siblings of nodes marked selected here may themselves default to be selected unless you store leaf selections only.

To build the last option, the minimal set, we can either

  1. Walk down the tree from the root
    1. When we encounter a selected node store that node in the set to persist and stop recursing this branch
    2. For all de-selected or partially selected nodes recurse down into all child nodes
  2. Take set of all selected nodes and discard all selected nodes that are covered by a selection higher up their branch
  3. Collect the set of all selected nodes then produce a second set from this for all nodes in the first set whose parent nodes are not also in that set.

Finally to load a set of selections into a tree the simplest approach is to process each one in turn as a new selection using the algorithm above. This may however cause extra redundant passes walking up and down the tree if e.g. we select all sibling nodes at one level one-by-one, or if we first select a non-leaf node then we select one of its immediate children. We can therefore optimise this further:

  1. For each selection in the set we’re loading, check if that node is not already selected in our tree. If it isn’t,
    1. mark this node and all descendant nodes as selected
    2. add this node’s parent to a set of topmost-node-parents we will use for the next step, if not already present.
  2. For each node in the set of topmost-node-parents,
    1. if this node is already selected (i.e. it was selected itself or an ancestor was) or already partially-selected (i.e. it has been considered by the ‘walk up’ step from a previously processed node) then ignore and continue the loop
    2. else perform the ‘walk up’ step from the selection algorithm starting with this node.

The process of loading a selection: with a given input set, mark the nodes and all descendant nodes as selected whilst also identifying the set of their parent nodes, walk up the tree from each parent node updating its state, leaving the complete re-loaded tree.

Or if we can guarantee that the selected set we have is minimal as above, i.e. no node in the set is a descendent of any other, and no complete set of sibling nodes are all selected, then we can optimise this further:

  • For every selected node
    1. mark the node and all descendants as selected
    2. mark all ancestor nodes as partially-selected

since all other cases are forbidden by our restrictions on the selection set.

I realise most of us won’t have to ever build our own implementation of these UI controls but I hope this has been interesting at least – whilst these are apparently simple UI controls there is actually a lot going on behind the scenes! Next time I will discuss a more complicated system with multiple paths of inherited selections and how to extend these algorithms to that case.

Tags: , , , ,

Categories: Technical


Leave a Reply

* Mandatory fields

× five = 25

Submit Comment