0
# Tree Operations
1
2
Core operations for creating, populating, and modifying interval trees. These operations maintain the tree's self-balancing properties and provide efficient O(log n) performance for most single-interval operations.
3
4
## Capabilities
5
6
### Construction
7
8
Create interval trees from various sources.
9
10
```python { .api }
11
class IntervalTree:
12
def __init__(self, intervals=None):
13
"""
14
Initialize interval tree.
15
16
Parameters:
17
- intervals: Optional iterable of Interval objects to populate tree
18
19
Time Complexity: O(n*log n) if intervals provided, O(1) if empty
20
"""
21
22
@classmethod
23
def from_tuples(cls, tups):
24
"""
25
Create tree from iterable of tuples.
26
27
Parameters:
28
- tups: Iterable of 2-tuples (begin, end) or 3-tuples (begin, end, data)
29
30
Returns:
31
IntervalTree: New tree containing intervals from tuples
32
33
Time Complexity: O(n*log n)
34
"""
35
```
36
37
### Adding Intervals
38
39
Insert individual intervals or batches of intervals.
40
41
```python { .api }
42
def add(self, interval):
43
"""
44
Add interval to tree if not already present.
45
46
Parameters:
47
- interval: Interval object to add
48
49
Time Complexity: O(log n)
50
"""
51
52
def append(self, interval):
53
"""Alias for add()."""
54
55
def addi(self, begin, end, data=None):
56
"""
57
Add interval by begin/end values.
58
59
Parameters:
60
- begin: Lower bound (inclusive)
61
- end: Upper bound (exclusive)
62
- data: Optional data payload
63
64
Time Complexity: O(log n)
65
"""
66
67
def appendi(self, begin, end, data=None):
68
"""Alias for addi()."""
69
70
def update(self, intervals):
71
"""
72
Add multiple intervals from iterable.
73
74
Parameters:
75
- intervals: Iterable of Interval objects
76
77
Time Complexity: O(m*log(n+m)) where m is number of intervals to add
78
"""
79
```
80
81
### Removing Intervals
82
83
Remove individual intervals or clear the entire tree.
84
85
```python { .api }
86
def remove(self, interval):
87
"""
88
Remove interval from tree.
89
90
Parameters:
91
- interval: Interval object to remove
92
93
Raises:
94
ValueError: If interval not present in tree
95
96
Time Complexity: O(log n)
97
"""
98
99
def removei(self, begin, end, data=None):
100
"""
101
Remove interval by begin/end/data values.
102
103
Parameters:
104
- begin: Lower bound
105
- end: Upper bound
106
- data: Data payload (must match exactly)
107
108
Raises:
109
ValueError: If interval not present in tree
110
111
Time Complexity: O(log n)
112
"""
113
114
def discard(self, interval):
115
"""
116
Remove interval if present, otherwise do nothing.
117
118
Parameters:
119
- interval: Interval object to remove
120
121
Time Complexity: O(log n)
122
"""
123
124
def discardi(self, begin, end, data=None):
125
"""
126
Remove interval by values if present.
127
128
Parameters:
129
- begin: Lower bound
130
- end: Upper bound
131
- data: Data payload
132
133
Time Complexity: O(log n)
134
"""
135
136
def clear(self):
137
"""
138
Remove all intervals from tree.
139
140
Time Complexity: O(1)
141
"""
142
```
143
144
### Tree Information
145
146
Access tree properties and statistics.
147
148
```python { .api }
149
def __len__(self):
150
"""
151
Get number of intervals in tree.
152
153
Returns:
154
int: Number of intervals
155
156
Time Complexity: O(1)
157
"""
158
159
def is_empty(self):
160
"""
161
Test if tree contains no intervals.
162
163
Returns:
164
bool: True if tree is empty
165
166
Time Complexity: O(1)
167
"""
168
169
def begin(self):
170
"""
171
Get earliest begin value in tree.
172
173
Returns:
174
Any: Minimum begin value across all intervals
175
176
Raises:
177
ValueError: If tree is empty
178
179
Time Complexity: O(1)
180
"""
181
182
def end(self):
183
"""
184
Get latest end value in tree.
185
186
Returns:
187
Any: Maximum end value across all intervals
188
189
Raises:
190
ValueError: If tree is empty
191
192
Time Complexity: O(1)
193
"""
194
195
def range(self):
196
"""
197
Get minimum-spanning interval containing all intervals.
198
199
Returns:
200
Interval: Interval from earliest begin to latest end
201
202
Raises:
203
ValueError: If tree is empty
204
"""
205
206
def span(self):
207
"""
208
Get length of minimum-spanning interval.
209
210
Returns:
211
Number: Length from earliest begin to latest end
212
213
Raises:
214
ValueError: If tree is empty
215
"""
216
```
217
218
### Tree Access
219
220
Retrieve intervals and iterate over tree contents.
221
222
```python { .api }
223
def items(self):
224
"""
225
Get all intervals as a set.
226
227
Returns:
228
set: Set containing all intervals in tree
229
230
Time Complexity: O(n)
231
"""
232
233
def __iter__(self):
234
"""
235
Iterate over all intervals in tree.
236
237
Returns:
238
iterator: Iterator over intervals in sorted order
239
240
Time Complexity: O(1) to create iterator, O(n) to consume
241
"""
242
243
def iter(self):
244
"""Alias for __iter__()."""
245
246
def copy(self):
247
"""
248
Create shallow copy of tree.
249
250
Returns:
251
IntervalTree: New tree with same intervals
252
253
Time Complexity: O(n*log n)
254
"""
255
```
256
257
### Tree Validation and Debugging
258
259
Methods for debugging and verifying tree integrity.
260
261
```python { .api }
262
def verify(self):
263
"""
264
Verify tree invariants for debugging.
265
266
Raises:
267
AssertionError: If tree structure is invalid
268
"""
269
270
def print_structure(self, tostring=False):
271
"""
272
Pretty-print tree structure for debugging.
273
274
Parameters:
275
- tostring: If True, return as string instead of printing
276
277
Returns:
278
str or None: Tree structure representation
279
"""
280
281
def score(self, full_report=False):
282
"""
283
Calculate tree optimization score.
284
285
Parameters:
286
- full_report: If True, return detailed scoring information
287
288
Returns:
289
float or dict: Score from 0-1 (lower is better) or detailed report
290
"""
291
```
292
293
## Usage Examples
294
295
### Basic Tree Operations
296
297
```python
298
from intervaltree import Interval, IntervalTree
299
300
# Create empty tree
301
tree = IntervalTree()
302
303
# Add intervals using different methods
304
tree.add(Interval(0, 10, "first"))
305
tree.addi(15, 25, "second")
306
tree[30:40] = "third" # Using slice notation
307
308
# Create tree from existing intervals
309
intervals = [Interval(0, 5), Interval(10, 15), Interval(20, 25)]
310
tree2 = IntervalTree(intervals)
311
312
# Create from tuples
313
tree3 = IntervalTree.from_tuples([(0, 5, "a"), (10, 15, "b")])
314
315
print(f"Tree has {len(tree)} intervals")
316
print(f"Tree spans from {tree.begin()} to {tree.end()}")
317
```
318
319
### Modification Operations
320
321
```python
322
from intervaltree import Interval, IntervalTree
323
324
tree = IntervalTree()
325
tree.update([Interval(0, 10), Interval(15, 25), Interval(30, 40)])
326
327
# Remove specific interval
328
tree.remove(Interval(15, 25))
329
330
# Safe removal (won't raise error if not present)
331
tree.discard(Interval(100, 200))
332
333
# Remove by values
334
tree.removei(30, 40)
335
336
# Batch addition
337
new_intervals = [Interval(5, 15), Interval(20, 30)]
338
tree.update(new_intervals)
339
340
# Clear all intervals
341
tree.clear()
342
print(f"After clear: {tree.is_empty()}") # True
343
```
344
345
### Tree Copying and Inspection
346
347
```python
348
from intervaltree import Interval, IntervalTree
349
350
# Create and populate tree
351
original = IntervalTree([Interval(i, i+5) for i in range(0, 50, 10)])
352
353
# Create shallow copy
354
copy_tree = original.copy()
355
356
# Get all intervals
357
all_intervals = original.items() # Returns set
358
interval_list = list(original) # Convert iterator to list
359
360
# Tree statistics
361
print(f"Tree contains {len(original)} intervals")
362
print(f"Spans from {original.begin()} to {original.end()}")
363
print(f"Total span length: {original.span()}")
364
365
# Debug information
366
original.verify() # Check tree invariants
367
score = original.score() # Get optimization score
368
print(f"Tree optimization score: {score}")
369
```