An abstract representation of a binary tree that can hold integers in the range [0, num_leaves - 1] and has a depth of exactly 1+ceil(log2(num_leaves)). For example, a FixedShapeBinaryTree(5) can be represented by: [0, 4] / \ / \ / \ [0, 3] [4, 4] / \ / \ / \ / \ [0, 1] [2, 3] [4, 4] [-1, -1] / \ / \ / \ / \ The most common use of this class is to have a concrete binary tree by defining its storage like: StrongVector<TreeNodeIndex, Val> tree(abstract_tree.StorageSize());
Besides the classical binary tree structure of left and right children, this class provides an API to inspect and search the intermediate nodes by their interval values.
Definition at line 51 of file fixed_shape_binary_tree.h.
| TreeNodeIndex operations_research::FixedShapeBinaryTree::GetNodeEndOfRange |
( |
LeafIndex | first_leaf, |
|
|
LeafIndex | last_leaf ) const |
|
inline |
Given a range of values, return the largest node in the tree associated to an interval [int_begin, int_end] that satisfies:
- int_end == first_leaf
- int_begin >= last_leaf. For example, GetNodeEndOfRange(0, largest_leaf_index) = Root().
This corresponds to a last node (including all its descendants) to do a DFS traversal to cover all intervals fully contained in the range [begin, end].
To see how high we can go on the tree we need to check the two rules:
- we need to end at
last_leaf, so we need to know which power of two divides last_leaf+1.
- the interval needs to be not greater than
last_leaf - first_leaf. If last_leaf - first_leaf is zero it must be a leaf, if it is one it can be one step above, etc).
Definition at line 186 of file fixed_shape_binary_tree.h.
| TreeNodeIndex operations_research::FixedShapeBinaryTree::GetNodeStartOfRange |
( |
LeafIndex | first_leaf, |
|
|
LeafIndex | last_leaf ) const |
|
inline |
Given a range of leaf indexes [first_leaf, last_leaf], return the largest node in the tree associated to an interval [int_begin, int_end] that satisfies:
- int_begin == first_leaf
- int_end <= last_leaf. For example, GetNodeStartOfRange(0, num_leaves - 1) = Root().
This corresponds to a starting node to do a DFS traversal (including all its children) to cover all intervals fully contained in the range [begin, end].
Since we truncate the intervals to the largest_leaf_index_, this is equivalent on the full binary tree to look for the largest possible value.
To see how high we can go on the tree we need to check the two rules:
- we need to start at
first_leaf, so we need to know which power of two divides first_leaf (odd are leaves, divisible by 2 but not by 4 are right above the leaves, etc).
- the interval needs to be not greater than
last_leaf - first_leaf. If last_leaf - first_leaf is zero it must be a leaf, if it is one it can be one step above, etc).
Definition at line 142 of file fixed_shape_binary_tree.h.
1.13.2