Basic Principles

Preferred-path decomposition:

Preferred child of node v means: * none if last access in V ‘s subtree=V * W if w is the last access in V’ s subtree.

Preferred path decomposes nodes in represented tree. Trees are separated.

Auxiliary trees:

Used in Tango Trees.

Represent each preferred path by splay trees / Tango trees / RB Trees. To key the nodes by depth. As seen by the video, the depth of the nodes are sorted. Nodes indexed in a balanced tree by depth.

Route of each aux. tree called a path parent (similar to Tree chain partition) as defined as top[].

Following one ‘s parent=find the predecessor in aux. tree. The actual parent of a subtree / aux. tree is the leftest node in the aux. tree, where the path parent’ s pointer should be indexed in the aux. tree ‘s root.

Take all the aux. trees with their path parents, we have a tree of aux. trees.

access () operation:

The most crucial operation in LCTs. Functions: * Make your life easy. * make Root-> V path preferred. * make V the root of its aux. tree (which is equivalent to: V is the root of tree of aux. trees, this is easier if using Splay trees).

  1. splay (V) within V’ s aux. tree. lchildren of V has smaller depths and vice versa. V now does not have preferred child, so we need to disconnect its preferred edge.
  2. Remove V ‘s preferred child in aux. tree:
    1. v. right. pathparent=v
    2. v. right. parent=null
    3. v. right=null
  3. Loop until v. pathparent=null
    1. w=v. pathparent
    2. splay (w) in aux. tree
    3. unlink w. right keeping w. right. pathparent
    4. w. right=v
    5. splay (v) for convenience in aux. tree / actually a rotate (v)

Query operations

findroot (v)

Find the root of the tree containing v.

  1. access (v)
  2. find leftest child of v and make it=r
  3. splay (r) / access (r) for log (n) amortized complexity

pathaggregate (v)

Find the sum of all weights on v’ s path to root

  1. access (v)
  2. return v. ltree. aggregation

access () makes our life easier.

Modify operations

cut (v)

Cut v from its parent / lives in another separate tree

  1. access (v)
  2. v. left. parent=null
  3. v. left=null

link (v, w)

Link v (the root of its tree) to w ‘s tree under w.

  1. access (v)
  2. access (w)
  3. v. left=w (it is guranteed that v. left=null)
  4. w. parent=v

Code implementation

Too lazy to write one...... Might add a post later.