[Sumtree]: Sumtree Insertion

[crnbarr93]

Background

A fundamental feature of any tree structure is node insertion, in the case of the sumtree mechanism we must insert only leaf nodes.

Suggested Design

This insertion can be done using a recursive function on the Node struct. Using recursion to traverse the tree we can determine insertion logic based on priority when reaching a decision point. For any node there are four possibilities for either children:

1. Child does not exist
2. Child is internal
   2a. Child is internal and new node is out of range
   2b. Child is internal and new node is in range
3. Child is a leaf

Using this we can determine there are 12 possible outcomes, however some priorities may cover multiple conditions. The following priority should suffice for first iteration insertion:

1. New node fits in either left or right range, insert accordingly
2. Left is empty, insert left
3. Incompatible left, Right is empty, insert right
4. Left is leaf, split left
5. Left is incompatible, right is leaf, split right

Here "splitting" a node involves creating a new internal node and assigning the split node and the new node as ordered children. It's very likely we may be able to simplify these conditions in future, or alter them to aid with balancing the tree.

Acceptance Criteria

• Sumtree insertion logic
• Unit-testing