Space Partitioning Trees¶
- class pydatastructs.OneDimensionalSegmentTree(segs)¶
Represents one dimensional segment trees.
- Parameters
segs (list/tuple/set) – The segs should contains tuples/list/set of size 2 denoting the start and end points of the intervals.
Examples
>>> from pydatastructs import OneDimensionalSegmentTree as ODST >>> segt = ODST([(3, 8), (9, 20)]) >>> segt.build() >>> segt.tree[0].key [False, 2, 3, False] >>> len(segt.query(4)) 1
Note
All the segments are assumed to be closed intervals, i.e., the ends are points of segments are also included in computation.
References
- build()¶
Builds the segment tree from the segments, using iterative algorithm based on queues.
- query(qx, init_node=None)¶
Queries the segment tree.
- Parameters
qx (int/float) – The query point
init_node (int) – The index of the node from which the query process is to be started.
- Returns
intervals – The set of the intervals which contain the query point.
- Return type
set
References
- __str__()¶
Used for printing.
- segments¶
- tree¶
- root_idx¶
- cache¶
- __module__ = 'pydatastructs.trees.space_partitioning_trees'¶