- Link(u,v) : node -> node -> effect
- Cut(u,v) : node -> node -> effect
- ConnectedQ(u,v) : node -> node -> bool
They should all be implemented in O(log |V|) by using Link-Cut trees.
typedef struct { // Represents a node in the lct.
LCT left; // Child
LCT right; // Child
LCT *hook; // General parent pointer
int sum; // The size of this sub-tree. Negative values are used to indicate
// that left and right pointers should be swapped on the sub-tree.
} *LCT;
LCT allocLCT(int n); // allocates space for a link-cut tree with n vertexes
void freeLCT(LCT t); // frees the link-cut structure
void access(LCT t, int v); // makes the path from the root to v selected
void reRoot(LCT t, int v); // makes v the root of the represented tree
// this is the same as the evert op. in the paper
int connectedQ(LCT t, int u, int v); // returns if there is a path from u to v
void link(LCT, int r, int v); // adds the edge from r to v to the represented
// tree. Before linking, the node r is made the
// root of its represented tree.
void cut(LCT t, int r, intv); // removes the edge (r,v) from the represented
// tree. The node r becomes the root of the
// resulting sub-tree.
// The connectedQ can be computed by applying reRoot to u and then computing
// access on v. If u and v end up in the same preferred path, then the two are
// connected; otherwise, they're not.Each tree of the forest has its edges partitioned into two classes: solid and broken.
Invariant: At most one of the edges entering each vertex is solid (they assume the edges are directed from children to parents).
- only allow link(v,w) when v is a tree root
- only allow cut(v,w) when w is the parent of v
- n = |V|, m = |E|
- apex
- shallowest vertex on a solid path
- nadir
- deepest vertex on a solid path
- root path
- solid path whose apex is a tree root
- by def, a rooted tree contains only one root path
- internal path
- solid path that’s not a root path
- by def, a rooted tree may contain zero or noe internal paths
- link(v,w)
- Link the trees containing vertices v and w by adding edge
(v,w), making vertex w the parent of vertex v. A link is only
allowed if v and w are in different trees and v is a tree root.
We carry out link(v,w) by performing expose(w) followed by a type 1 concatenation of the path whose apex is v and the path whose nadir is w.
- cut(v,w)
- Cut the tree containing vertices v and w into two trees by
deleting edge (v,w). A cut is only allowed if (v,w) is an edge.
We carry out cut(v,w) by performing expose(v) followed by a split(w) of type 1.
- root(v)
- Return the root of the tree containing vertex v.
We carry out root(v) by performing expose(v) and finding the apex of the path containing v.
- evert(v)
- Modify the tree containing vertex v by making v the root.
We carry out evert(v) by performing expose(v) and then reverse the solid path whose nadir is v with reverse(v).
- concatenate
- Combine paths p1 and p2 into a single path by constructing a
solid edge leading from the apex of p1 to the nadir of p2.
- concatenate1
- p1 is a root path; the concatenate has the effect of linking the trees containing p1 and p2, carrying out link(apex(p1), nadir(p2)).
- concatenate2
- In a type 2 concatenate, p1 and p2 are in the same tree and a broken edge leads from apex(p1) to nadir(p2); the effect of this operation is to convert this broken edge to solid. To specify this op. we only need to give the apex of p1.
- split
- Split the path containing vertex v into two paths, one of which has v
as its nadir. It’s only allowed if a solid edge(u,v) enters vertex v.
- split1
- Deletes the edge from the forest.
- split2
- Converts the edge to a broken edge.
- splice
- Vertex v must have an exiting broken edge. Let w be the other end of the broken edge exiting v. If w has an entering solid edge, perform a split(w) of type 2. Once no solid edge enters w, perform a concatenate(v) of type 2.
- expose
- Construct a path whose nadir is v and whose apex is the root of the
tree containing v.
If v has an entering solid edge, perform a split(v) of type 2. Now repeat the following step until the apex of the path containing v is a tree root: Let w be the apex of the path containing v; perform splice(w).
Remark: Notice that the expose operation requires the ability, given a vertex, of finding the apex of the path containing the vertex.
- reverse
- reverse the direction of every edge on the path p, thereby exchanging the nadir and apex of p.
(Application of splay trees to link/cut trees start in page 26)
Repeat the splaying step until the accessed node is the root of the tree.
- access(i,t)
- If item i is in tree t, return a pointer to its location;
otherwise, return a pointer to the null node.
To perform access(i,t), we search down from the root of t, looking for i. If the search reaches a node x containing i, we complete the access by splaying at x and returning a pointer to x. If the search reaches the null node, indicating that i is not in the tree, we complete the access by splaying at the last nonnull node reached during the search and returning a pointer to null. If the tree is empty, we omit the splaying operation.
- insert(i,t)
- Insert item i in tree t, assuming that it is not there
already.
To carry out insert, we perform split(i,t) and then replace t by a tree consisting of a new root node containing i, whose left and right subtrees are the trees t1 and t2 returned by the split.
Check the other (better) implementation on page 11.
- delete(i,t)
- Delete item i from tree t, assuming that it is present.
To carry out delete(i,t), we perform access(i,t) and then replace t by the join of its left and right subtrees.
Check the other (better) implementation on page 11.
- join(t1,t2)
- Combine trees t1 and t2 into a single tree containing all
items from both trees and return the resulting tree. This
operation assumes that all items in t1 are less than all
those in t2 and destroys both t1 and t2.
To carry out join(t1,t2), we begin by accessing the largest item, say i, in t1. After the access, the root of t1, contains i and thus has a null right child. We complete the join by making t2 the right subtree of this root and returning the resulting tree. We must deal explicitly with empty input trees.
- split(i,t)
- Construct and return two trees t1 and t2, where t1 contains all
items in t less than or equal to i, and t2 contains all items in
t greater than i. This operation destroys t.
To carry out split(i,t), we perform access(i,t) and then return the two trees formed by breaking either the left link or the right link from the new root of t, depending on whether the root contains an item greater than i or not greater than i. We must deal explicitly with the case of an empty input tree.
*----------------------------------------------------------------------------* * Link/Cut tree internal represetation * *----------------------------------------------------------------------------*
typedef struct node { struct node *left; struct node *right; struct node *parent; } *node;
* Is it the root of the virtual tree? * bool is_root(node n) { return n && n->parent == NULL; }
bool is_left_child(node n) { return n && n->parent->left == n; } bool is_right_child(node n) { return n && n->parent->right == n; }
bool is_middle_child(node n) { return n && not(is_root(n)) && not(is_left_child(n->parent)) && not(is_right_child(n->parent)); }
* Is it the root of a solid subtree? * bool is_solid_root(node n) { return is_root(n) || is_middle_child(n); }
void swap(node a, node b) { struct node t = *a; *a = *b; *b = t; }
void splice(node n) { if (is_middle_child(n) && is_solid_root(n->parent)) { swap(n, n->left); } }
/**
- Rotates the edge joining y and its right child.
*/ void rotate_left(node y) { node x = y->right, z = y->parent;
if (z) { if (z->left == y) { *z->left = *x; } else if (z->right == y) { *z->right = *x; } }
*y->right = *x->left; *x->left = *y;
*x->parent = *z; *y->parent = *x;
if (y->right) { *y->right->parent = *y; } }
/**
- Rotates the edge joining y and its left child.
*/ void rotate_right(node y) { node x = y->left, z = y->parent;
if (z) { if (z->right == y) { *z->right = *x; } else if (z->left == y) { *z->left = *x; } }
*y->left = *x->right; *x->right = *y;
*x->parent = *z; *y->parent = *x;
if (y->left) { *y->left->parent = *y; } }
/**
- Splaying Step
*
- Case 1 (zig). If x->parent, the parent of x, is the tree root, rotate the edge
- joining x with x->parent. (This case is terminal.)
*
- Case 2 (zig-zig). If x->parent is not the root and x and x->parent are both left or
- both right children, rotate the edge joining x->parent with its grandparent x->parent->parent
- and then rotate the edge joining x with x->parent.
*
- Case 3 (zig-zag). If x->parent is not the root and x is a left child and x->parent a
- right child, or vice-versa, rotate the edge joining x with x->parent and then
- rotate the edge joining x with the new x->parent.
*/ void splay_step(node x) { if (is_left_child(x)) { if (is_solid_root(x->parent)) { rotate_right(x->parent); } else if (is_left_child(x->parent)) { rotate_right(x->parent->parent); rotate_right(x->parent); } else if (is_right_child(x->parent)) { rotate_right(x->parent); rotate_left(x->parent); } } else if (is_right_child(x)) { if (is_solid_root(x->parent)) { rotate_left(x->parent); } else if (is_right_child(x->parent)) { rotate_left(x->parent->parent); rotate_left(x->parent); } else if (is_left_child(x->parent)) { rotate_left(x->parent); rotate_right(x->parent); } } }
/**
- Splaying as a three-pass bottom-up process.
*/ void splay(node x) { node v; for (v = x; v && not(is_root(v));) { splay_step(v); if (is_middle_child(v)) v = v->parent; } for (v = x; v && not(is_root(v)); v = v->parent) splice(v->parent); for (; x && not(is_root(x)); x = x->parent) splay_step(x); }
*----------------------------------------------------------------------------* * Fundamental Path Operations * *----------------------------------------------------------------------------*
*----------------------------------------------------------------------------* * Link/Cut operations * *----------------------------------------------------------------------------*
/**
- Return the root of the tree containing node v.
*/ node find_root(node v) { splay(v);
node last; { * Follow right pointers until reaching the last node. * node r = v->right; node rr = r->right;
if (r == NULL) { last = v; }
while (rr) { r = rr; rr = rr->right; }
last = r; }
splay(last); return last; }
/**
- If v is a tree root and w is a vertex in another tree, link the trees
- containing v and w by adding the edge (v,w), making w the parent of v.
*/ void link(node v, node w) { splay(v); splay(w); *v->parent = *w; }
/**
- If node v is not a tree root, divide the tree containing v into two trees by
- deleting the edge from v to its parent.
*/ void cut(node v) { splay(v); v->right->parent = NULL; v->right->parent = NULL; }
/**
- Turn the tree containing vertex v “inside out” by making v the root of the
- tree.
*/ void evert(node v) { reverse(expose(v)); }
* /\*----------------------------------------------------------------------------*\ / / \* Project operations *\ / / \*----------------------------------------------------------------------------*\ */
* void Link(node u, node v) { undefined(“Link”,u,v); } * * void Cut(node u, node v) { undefined(“Cut”,u,v); } * * void ConnectedQ(node u, node v) { undefined(“ConnectedQ”,u,v); } *
* /\*----------------------------------------------------------------------------*\ / / \* Main *\ / / \*----------------------------------------------------------------------------*\ */
int main_link_cut() { return 0; }
int main() { undefined(“main”); return main_link_cut(); }