Transformations

Link

Link node x and y

• remove x from its original parent
• If x is active, it's attached to the leftmost of y's children
• If x is passive but not linkable, it's attached to the left of the first passive child of y
• If x is passive linkable, it's attached to the rightmost of y's children
• Adjust the loss and rank accordingly

Active Root Reduction

Performed on two active roots x and y with equal rank r

• Compare x and y, w.l.o.g. assume y < x
• Link y to x, thus x's rank is increased by 1
• If the rightmost child z of x is passive, link z to the root
• Note, x and y were both active roots so they had and will also end up having loss 0, and their parents are passive with no rank and loss(given x and y are active roots).

Result

• Root Degree: No change or +1 (if there is z)
• Total Loss: No change
• Active Roots: -1 (y is no longer an active root)

Effects on Invariants

I1: No violations. The only change in active node is y -- the (r+1)-th rightmost child of x, this is OK since y has rank r and loss 0

I2: Trivially, no violation happens to I2 as no changes on the total loss

I3: This transformation can be used when I3 is violated since it decreases the number of active root by 1. By Lemma 4, we are guaranteed to find two active roots x and y with the same rank to perform this transformation

I4: I4 could be violated as the root degree can increase by 1, but together with Root Degree Reductions(See below and Summary), we can fix the structure in constant time

I5: No violations. The degree of x increases by 1, but we detach z to keep it the same. And, if there is no z to detach, then all children of x is active, and from Lemma 2, we know x has at most degree R

Root Degree Reduction

Performed on the three rightmost passive linkable children x, y, z of the root

• Assume, w.l.o.g x < y < z
• Make x and y active
• Link z to y
• Link y to x
• Since x is active, it now has loss 0 and rank 1(i.e. y), and make x the leftmost child of the root
• y now has loss 0 and rank 0

Result

• Root Degree: -2 (y, z are no longer children of the root)
• Total Loss: No changes
• Active Roots: +1 (x is a new active root)

Effects on Invariants

I1: No violations as y becomes the 1st rightmost child of x, and y has rank + loss of 0

I2: Trivially, no violation to I2 as no changes to the total loss

I3: It could break I3 as the Active Roots increase by 1, but together with Active Root Reduction, we are still safe

I4: This transformation can be used when I4 is violated since it can decrease the root degree by 2. By Lemma 5, we are guaranteed to find three rightmost passive linkable children x, y, z of the root to perform this transformation

I5: No violations. Both x and y get a new child. But they change from being a passive node to an active node with loss 0, so they are allowed to have one more child.

Note: Because Active Root Reduction increases the root degree by 1 and Root Degree Reduction increases the Active Roots number by 1, they are often performed together to ensure no violations to all 5 invariants (also see Summary)

One Node Loss Reduction

Performed on an active node x with loss 2

• Link x to the root. x is now an active root, thus it has loss 0 now
• x's original parent y must be active(Given x had loss 2; x was not an active root), so we decrease y's rank by 1 and increase y's loss by 1 if y is not an active root.

Result

• Root Degree: +1 (i.e. x)
• Total Loss: -1 or -2 (depends on if y was an active root or not)
• Active Roots: +1 (x is a new active root)

Effects on Invariants

I1: No violations. For y's active children on x's right side, they are not affected. For the children on the left side, their constraints are weakened, i.e. goes from at least i - 1 to at least i - 2

I2: This transformation can be used when I2 is violated since it can decrease the loss. By Lemma 3, if the loss constraint is violated by 1, together with Two Node Loss Reduction(described below), we can bring down the total loss to within the constraint

I3 and I4: It could violate I3 and I4 as the Active Roots and Root degree increase by 1, but as explained above, we can perform Active Root Reductions and Root Degree Reductions together to bring them down if needed

I5: Notice this has no effects on I5 as no non-root nodes get new children

Note: Because of I2, I3 and I4, Loss reduction, Active Root Reductions and Root Degree Reductions are always performed together when necessary(also see Summary)

Two Node Loss Reduction

Performed on two active nodes x, y with equal rank r and loss == 1

• w.l.o.g, x < y
• Link y to x
• Make both x and y has loss 0
• For y's original parent z, its rank is decreased by 1 and its loss is decreased by 1 (if it is not an active root)

Result

• Root Degree: No change
• Total Loss: -1 or -2 (depends on if z was an active root or not)
• Active Roots: No change

Effects on Invariants

I1: No violations. The only change in active node is y becomes the (r+1)-th rightmost child of x, this is OK since y has rank r and loss 0

I2: It decreases the loss by at least 1. By Lemma 3, and pair this with One Node Loss Reduction, we can keep I2.

I3 and I4: Unlike One Node Loss Reduction, active roots and root degree are not increased, so no violations

I5: The degree of x is increased by 1, however, it changes from being an active node with positive loss to an active node with loss 0, so it's allowed to have one more child.

Summary

Note, from the above analysis and the summary in the chart, we can conclude no transformations can break I1, I2 and I5. And if we perform Active Root Reduction with Root Degree Reduction (with One or Two Nodes Loss Reduction), no transformations can violate I1 to I5.

In the following sections, we will see Active Root Reductions are always paired with Root Degree Reductions to ensure no violations happen to the 5 invariants. And after a loss reduction is performed, Active Root Reductions and Root Degree Reductions are performed to ensure the invariants aren't broken.