Tree Balancing

[matthew-mccall]

There is a variety of ways the same mathematical expression could be represented in an Expression tree. The goal is to make tree insertion and tree building more deterministic.

Possibility

graph TD;
    Add1-->1;
    Add1-->Add2;
    Add2-->2;
    Add2-->Add3;
    Add3-->3;
    Add3-->4;

A Better Tree

graph TD;
    Add1-->Add2;
    Add1-->Add3;
    Add2-->1;
    Add2-->2;
    Add3-->3;
    Add3-->4;

• [ ] Research tree balancing methods: Red-Black vs AVL trees, etc
• [ ] Implement

[JMAR059]

After researching balancing trees, it was found that something that would work for OASIS is red and black trees. The implementation is simple and with some modifications to the pseudocode for red and black tree balancing, you can achieve a 1 to 1 conversion of the problem.

The first thing to keep in mind is that balancing should only occur in parts of the tree that are associative in order to not break representation. The tree structure of:

graph TD;
    Add1-->1;
    Add1-->Mul;
    Mul-->2;
    Mul-->Add2;
    Add2-->3;
    Add2-->4;

Cannot be changed to:

graph TD;
    Add1-->Mul;
    Add1-->Add2;
    Mul-->1;
    Mul-->2;
    Add2-->3;
    Add2-->4;

Since this would essentially convert 1 + 2 * (3 + 4) to (1 + 2) * (3 + 4), which is not equivalent. While this would keep representation, it poses the reality that not every tree can be fully balanced in OASIS.

However, it is almost necessary to first focus on designing inserting or deletion operations that will be used in practice first, as with any of the known balancing tree operations, these depend on these operations.

If we wanted to When it comes to red and black balancing method, two things would first need to implemented:

• Parent Pointers
• Insertion

These are both crucial for Red and Black tree balancing, and as mentioned, almost all tree balancing operations.

Assuming there is an insert that places a associative operation as one of the children of a balanced tree. Say an addition of the real number 5, to a tree of add operations. The balancing problem for the tree could be reduced to Red and Black balancing by simply representing the add operations of the tree with red and black nodes, and having children or parent nodes that are either different operations like multiply or real expressions to be represented as NULL pointers. This way, we achieve balancing for OASIS tree as if it was a Red and Black tree while maintaining that no matter the order of operations for the different additions and their children, the equivalent result will be the same.

So in the example given, when adding 5 to the expression, it first inserts then checks for violations to the tree and if rebalancing is needed. At any step, if there is a rotation of the tree, the children nodes which would be represented by NULL pointers would still be saved and exchanged since rotations could happen at any level of the tree, thus any children that could potentially be NULL or a red/black node would be preserved. Additionally, we can guarantee we would not break OASIS representation since there would not be a case where a tree structure in Red and Black would exchange NULL child nodes in such a way that the tree would be:

graph TD;
    Red --> NULL;
    NULL --> BLACK;

Thus, all children which are the expressions to add, would remain at the bottom of the tree and the add binary expressions at the top of the tree would be rebalanced. Pseudo code that check for this NULL condition can simply be something like, given node x: if x.parent is NULL --> if x.parent is NULL or x.parent.type != x.type This would allow for easy implementation, given insertion working similarly.

[K3LV0N]

Sources used for research can be found inside this document:

https://docs.google.com/document/d/1fulZ21GOU8bgYeodJCGhUnEvWsNmyL-5b_ELFxbLb8s/edit?usp=sharing