A balanced search tree O(1) worst-case update time (Q1114387): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: A new data structure for representing sorted lists / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: The design of dynamic data structures / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Worst-case optimal insertion and deletion methods for decomposable searching problems / rank | |||
Normal rank | |||
Revision as of 10:36, 19 June 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A balanced search tree O(1) worst-case update time |
scientific article |
Statements
A balanced search tree O(1) worst-case update time (English)
0 references
1988
0 references
A new data structure is described for performing member and neighbor queries in O(log n) time that allows for O(1) worst-case update time once the position of the inserted or deleted element is known. In this way previous solutions that achieved only O(1) amortized time or \(O(\log^* n)\) worst-case time are improved. The method is based on a combinatorial result on the height of piles that are split after some fixed number of insertions. This combinatorial result is interesting in its own right and might have other applications as well.
0 references
balanced search tree
0 references
data structure
0 references
member and neighbor queries
0 references
