4 ms·
How do you determine if your tree is pathological? I.e., what types of tree structures would you find the closure table model to be pathological enough to warra
by jsherer 12y ago
How do you determine if your tree is pathological? I.e., what types of tree structures would you find the closure table model to be pathological enough to warrant other modeling options?
- acjohnson55 12y agoGood question -- so the most pathological tree of n nodes would be one with depth of O(n). If this was the case, the closure table would be of size O(n^2). In tree applications I can think of--like an org chart or site comments--the depth is O(log(n)), in which case the closure table is just O(n). Note that this same kind of pathological tree would be hell for a recursive query too, just trading space for time.