Timeline for Given a B-Tree, determine the order keys were inserted
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 31, 2013 at 13:38 | history | tweeted | twitter.com/#!/StackCSTheory/status/418013203072057345 | ||
| Mar 5, 2012 at 17:07 | answer | added | A T | timeline score: -2 | |
| May 2, 2011 at 15:42 | comment | added | Tsuyoshi Ito | @JɛffE: My use of the word “rotation” was probably incorrect (I confused B-trees with (various) balanced BSTs). But a parent may have been inserted after its children in B-trees. See this figure for an example. | |
| May 2, 2011 at 2:21 | comment | added | Jeffε | But the standard B-tree insertion algorithm doesn't involve any rotations. If the original poster is considering something other than the standard algorithm, he needs to tell us what that is. If you don't know the insertion algorithm, you can't infer anything about the insertion order. | |
| May 1, 2011 at 23:59 | comment | added | Tsuyoshi Ito | @JɛffE: Because tree rotations break the assumption that children are inserted after their parent. | |
| Apr 29, 2011 at 20:40 | comment | added | Jeffε | I'm confused. Why isn't "inserted earlier" the same partial order as "proper ancestor"? | |
| Apr 29, 2011 at 16:50 | comment | added | SRobertJames | @Kaveh @Tsuyoshi - Thank you for the feedback, indeed I didn't supply enough detail in my question. It's revised now - please take a look! | |
| Apr 29, 2011 at 16:50 | history | edited | SRobertJames | CC BY-SA 3.0 |
Clarified handling intractability by using partial ordering and probabilistic methods
|
| Apr 29, 2011 at 16:05 | comment | added | Kaveh | @Tsuyoshi, I don't say it is easy, but it looks like an assignment to me and therefore not research level (why would we need to generate all answers when as say there might be exponentially many of them). | |
| Apr 29, 2011 at 13:22 | comment | added | bbejot | @Tsuyoshi: It appears to me that most cases will be exponential. It would be interesting to see if the average number of inputs for each B-tree was exponential. If so, a brute-force method of trying each of the $n!$ solutions might be justifiable. | |
| Apr 29, 2011 at 12:28 | comment | added | Tsuyoshi Ito | @Kaveh: Is this easy? I am pretty sure that there are exponentially many solutions in some cases, and I would not expect an efficient algorithm in terms of input size, but I cannot see beyond that (at least after thinking about it just one minute). | |
| Apr 29, 2011 at 7:44 | comment | added | Kaveh | Hi SRobertJames. Please read the FAQ. This does not seem to be a research level question. | |
| Apr 29, 2011 at 1:24 | history | asked | SRobertJames | CC BY-SA 3.0 |
