Timeline for Subrange of a Red and Black Tree
Current License: CC BY-SA 2.5
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 3, 2011 at 13:32 | vote | accept | Daniel C. Sobral | ||
| Feb 3, 2011 at 13:32 | vote | accept | Daniel C. Sobral | ||
| Feb 3, 2011 at 13:32 | |||||
| Feb 3, 2011 at 2:41 | answer | added | Danny Sleator | timeline score: 8 | |
| Oct 14, 2010 at 7:03 | answer | added | Maverick Woo | timeline score: 6 | |
| Sep 12, 2010 at 15:01 | vote | accept | Daniel C. Sobral | ||
| Feb 3, 2011 at 13:32 | |||||
| Sep 11, 2010 at 20:17 | answer | added | Tsuyoshi Ito | timeline score: 11 | |
| Sep 9, 2010 at 14:20 | comment | added | Tsuyoshi Ito | It seems that the split operation on red-black trees can be implemented in worst-case time O(log n), where n is the number of elements in a tree. This claim can be found in the introduction of the paper “Purely functional worst case constant time catenable sorted lists” by Gerth Stølting Brodal, Christos Makris and Kostas Tsichlas, ESA 2006: cs.au.dk/~gerth/pub/esa06trees.html. As I mentioned in my previous comment, this allows a worst-case O(log n)-time implementation of the subrange operation. | |
| Sep 9, 2010 at 12:10 | comment | added | Tsuyoshi Ito | The subrange operation can be implemented by two split operations, and the split operation might be easier to consider. I will not be surprised if split (and hence subrange) on a red-black tree can be implemented in worst-case time O(log n), where n is the number of elements in the original tree. | |
| Sep 8, 2010 at 8:30 | comment | added | Radu GRIGore | @Daniel: If trees are immutable then I don't see how you can avoid using $\lg n$ auxiliary space (typically in the form of a call stack). (You ask for $o(m)$ auxiliary space, but it's not clear what dependence on n you want.) | |
| Sep 8, 2010 at 1:03 | comment | added | Tsuyoshi Ito | If the trees are immutable, I wonder if O(polylog n) time is possible, where n is the number of elements in the original tree. Of course, it is easy to construct a binary search tree consisting of the desired range in O(log n) time (because you can share subtrees if trees are immutable), and the “only” nontrivial part is to recover the invariants of the red-black tree. I wonder how many nodes have to change their colors to recover the invariants. | |
| Sep 7, 2010 at 22:14 | comment | added | Daniel C. Sobral | @Tsuyoshi Preferably, immutable trees and no temporary data structure storing all elements -- like in Radu's answer. However, anything helps. | |
| Sep 7, 2010 at 22:11 | history | edited | Daniel C. Sobral | CC BY-SA 2.5 |
added 1 characters in body
|
| Sep 7, 2010 at 22:11 | comment | added | Daniel C. Sobral | @Tsuyoshi Indeed, yes. Fixing... | |
| Sep 7, 2010 at 21:45 | comment | added | Tsuyoshi Ito | Also, did you mean upper bound instead of lower bound in the last paragraph? | |
| Sep 7, 2010 at 21:35 | comment | added | Tsuyoshi Ito | Are trees immutable? | |
| Sep 7, 2010 at 18:17 | answer | added | Radu GRIGore | timeline score: 3 | |
| Sep 7, 2010 at 17:38 | comment | added | Daniel C. Sobral | @Radu I added a couple of paragraphs to better explain my question. | |
| Sep 7, 2010 at 17:36 | history | edited | Daniel C. Sobral | CC BY-SA 2.5 |
better explain what I want
|
| Sep 7, 2010 at 16:31 | comment | added | Aryabhata | @Radu: There is a bug in the comment edit feature. If you use latex in a comment and edit the comment, you see strange behaviour, like duplication etc. | |
| Sep 7, 2010 at 14:58 | history | asked | Daniel C. Sobral | CC BY-SA 2.5 |