The parenthesis tree |
| |
| Authors: | Ralf Hartmut Güting Derick Wood |
| |
| Affiliation: | Lehrstuhl Informatik VI, Universität Dortmund, D-4600 Dortmund 50, West Germany;Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 |
| |
| Abstract: | We provide a simple and direct dynamic data structure, the parenthesis tree, to represent a set of nested intervals using O(n) space. Updating and querying with an interval nested with respect to those in the tree can be carried out in O(logn) time. This structure provides a simpler alternative to the “treap” when solving the connected component problem. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
