Observations

Everybody knows that a binary tree is defined by a formula T(x)=1+x*T2(x), where x is the type of the value that the tree contains.

For the beginners: A tree is either empty (=1) or a triple: (x, t1, t2) where t1 and t2 are also binary trees of the aforementioned kind.

So there. Easy. You can see that this is a quadratic equation, and that it can be represented as a cubic root on a complex plane... it's not about this; let's see how we can store changes in trees, that is, differences, that is, derivatives.

dT/dx = T2 + 2*x*T*dT/dx, whereby we have
dT/dx = T2/(1-2*x*T)

Oh, wait, you probably heard already that List(x) is defined by a formula List(x)=1+x*List(x), right? Either empty (=1) or a pair (ok, a product) (x, List(x)), right?

but this equation, List(x)=1+x*List(x) has a solution, List(x)=1/(1-x). Remember this.

Now 1/(1-2*x*T) is a list, List(2*x*T)

So dT/dx = T2 * List(2*x*T)

An update of a tree can be represented as two trees and a list of triples (bool, x, T), where T is a tree.
But what is it?

The two trees are left and right subtrees of the point-of-change; and the list of triples is the path from the root to the point of change; each element of the path being this:
- left or right
- the changed value
- the intact subtree

On this picture you see gray left, black right, and the path is red values with brown intact subtrees.



Cool eh?

Note, I did not use any particular programming language.

Source: http://www.youtube.com/watch?v=YScIPA8RbVE&noredirect=1