Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
|
A Basic Tree, which supports binary lifting. More...
Public Member Functions | |
Tree (int nodes) | |
Class parameterized constructor, resizes the and initializes the data members. | |
void | add_edge (const int u, const int v) |
Adds an undirected edge from node u to node v in the tree. | |
void | change_root (int new_root) |
Set the root for the tree. | |
void | set_node_val (const std::vector< X > &node_val) |
Set the values for all the nodes. | |
void | init () |
This function must be called after the tree adjacency list and node values are populated The function initializes the required parameters, and populates the segment tree. | |
void | lift (int *const p, int dist) |
The function lifts a node, k units up the tree. The lifting is done in place, and the result is stored in the address pointed by p. | |
int | kth_ancestor (int p, const int &dist) |
The function returns the kth ancestor of a node. | |
int | lca (int a, int b) |
The function returns the least common ancestor of two nodes. | |
Private Member Functions | |
void | dfs_size (int u, int p=-1) |
Utility function to compute sub-tree sizes. | |
void | dfs_lca (int u, int p=-1) |
Utility function to populate the t_par vector. | |
Private Attributes | |
std::vector< std::list< int > > | t_adj |
an adjacency list to stores the tree edges | |
const int | t_nodes |
number of nodes | |
const int | t_maxlift |
maximum possible height of the tree | |
std::vector< std::vector< int > > | t_par |
a matrix to store every node's 2^kth parent | |
std::vector< int > | t_depth |
a vector to store the depth of a node, | |
std::vector< int > | t_size |
a vector to store the subtree size rooted at node | |
int | t_root |
the root of the tree | |
std::vector< X > | t_val |
values of nodes | |
Friends | |
template<typename T > | |
class | HLD |
A Basic Tree, which supports binary lifting.
the | data type of the values stored in the tree nodes |
Deleting the default constructor An instance can only be created with the number of nodes Defaults: t_node indexing are zero based t_root is 0 depth of root_node is 0 Supports: lift :- lift a node k units up the tree kth_ancestor :- returns the kth ancestor lca :- returns the least common ancestor
|
inlineexplicit |
Class parameterized constructor, resizes the and initializes the data members.
nodes | the total number of nodes in the tree |
|
inline |
Adds an undirected edge from node u to node v in the tree.
u | the node where the edge is from |
v | the node where the edge is to |
|
inline |
|
inlineprivate |
Utility function to populate the t_par vector.
u | current dfs node |
p | the parent of node u |
|
inlineprivate |
Utility function to compute sub-tree sizes.
u | current dfs node |
p | the parent of node |
u |
|
inline |
This function must be called after the tree adjacency list and node values are populated The function initializes the required parameters, and populates the segment tree.
|
inline |
The function returns the kth ancestor of a node.
p | the node id whose kth ancestor is to be found |
dist | the distance to move up the tree |
|
inline |
The function returns the least common ancestor of two nodes.
a | node id_1 |
b | node id_2 |
|
inline |
The function lifts a node, k units up the tree. The lifting is done in place, and the result is stored in the address pointed by p.
p | a pointer to the variable that stores the node id |
dist | the distance to move up the tree |
|
inline |
Set the values for all the nodes.
node_val | a vector of size n, with all the node values where, n is the number of nodes |