One of my interests is data structures, specifically dynamic trees. Unfortunately, there are few English resources for some of these, which has lead me to reading several Chinese blogs.

One topic that I had particular difficulty finding English resources for was the self-adjusting top tree, known in Chinese as the AAA 树. It can be best described as the marriage between an Euler Tour Tree and a Link/Cut Tree, allowing for operations to be performed on both paths and subtrees.

There are several possible implementations of this, differing primarily on how they handle the non-preferred children. At a high level, the idea is that every node should hold a splay tree consisting of its non-preferred children.

One implementation I personally like is to have 5 child pointers: two of these correspond to the usual preferred path of an LCT, one corresponds to the root of the splay tree of non-preferred children, and the remaining two are used to implement said splay tree.

Update

In the 5 years since I first thought of writing about dynamic trees, it seems much of what I know (and a lot that I do not!) has been put on Codeforces. In that time, I’ve also given a short presentation on splay trees and one on LCTs, the slides can be found here and here.