<p>Simple... keep two pointers, a <strong>next</strong> and a <strong>previous</strong>.</p>

CC BY-SA 3.0
2012-03-05T17:33:02.093Z
I don't think this is what he means. The point is that if I give you all the possible insertion sequences of (the same) $n$ elements, some of them will generate the same B-tree. Now, I give you one of those B-trees, and I ask you for some insertion sequence that generated that tree.
zotachidil
CC BY-SA 3.0
2012-03-05T17:07:40.037Z
2012-03-05T17:07:40.037Z
A T
<p>Given a B-tree, determine what order the keys were inserted in.  There may be multiple answers: I'd like to generate them all.</p>

<p>Is there any known method for this?  Or similar problems?</p>

<p><strong>Clarification:</strong> As the comments mentioned, enumerating them all may be intractable.  I'd like to do two things:</p>

<ol>
<li><p>Create a partial ordering. Node 7 was inserted before Node 4, but cannot be compared to Node 20.  (I've done this successfully for a binary search tree, and am wondering if this can be applied to B-tree as well. For BSTs, it seems to be simple: Node A &lt; Node B iff Node A is an ancestor of Node B, assuming no deletions.)</p></li>
<li><p>Create what I call a probabilistic partial ordering.  For example: Out of <em>x</em> possible orderings, <em>y</em> have Node 4 inserted before Node 20, and <em>1 - y</em> have Node 4 after Node 20.  I still am working on this even for binary search trees, so perhaps it's better to ask this question there first.</p></li>
</ol>

<p>I'm also working on expanding the model to include deletions (probablisticly), but that will come later.</p>

CC BY-SA 3.0
2011-04-29T07:44:41.490Z
Hi SRobertJames. Please read the FAQ. This does not seem to be a research level question.
Kaveh
CC BY-SA 3.0
2011-04-29T12:28:42.683Z
@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).
Tsuyoshi Ito
CC BY-SA 3.0
2011-04-29T13:22:25.140Z
@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.
bbejot
CC BY-SA 3.0
2011-04-29T16:05:05.447Z
@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).
Kaveh
CC BY-SA 3.0
2011-04-29T16:50:41.833Z
@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!
SRobertJames
CC BY-SA 3.0
2011-04-29T20:40:32.980Z
I'm confused.  Why isn't "inserted earlier" the same partial order as "proper ancestor"?
Jeffε
CC BY-SA 3.0
2011-05-01T23:59:06.453Z
@JɛﬀE: Because tree rotations break the assumption that children are inserted after their parent.
Tsuyoshi Ito
CC BY-SA 3.0
2011-05-02T02:21:17.880Z
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.
Jeffε
CC BY-SA 3.0
2011-05-02T15:42:10.420Z
@JɛﬀE: 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](http://en.wikipedia.org/wiki/File:B_tree_insertion_example.png) for an example.
Tsuyoshi Ito
<ds.data-structures><tree>
Given a B-Tree, determine the order keys were inserted
SRobertJames
# Given a B-Tree, determine the order keys were inserted

(Asked by: username_0 on 2011-04-29)

Given a B-tree, determine what order the keys were inserted in. There may be multiple answers: I'd like to generate them all.

Is there any known method for this? Or similar problems?

**Clarification:** As the comments mentioned, enumerating them all may be intractable. I'd like to do two things:

1. Create a partial ordering. Node 7 was inserted before Node 4, but cannot be compared to Node 20. (I've done this successfully for a binary search tree, and am wondering if this can be applied to B-tree as well. For BSTs, it seems to be simple: Node A < Node B iff Node A is an ancestor of Node B, assuming no deletions.)
2. Create what I call a probabilistic partial ordering. For example: Out of *x* possible orderings, *y* have Node 4 inserted before Node 20, and *1 - y* have Node 4 after Node 20. I still am working on this even for binary search trees, so perhaps it's better to ask this question there first.

I'm also working on expanding the model to include deletions (probablisticly), but that will come later.

**Tags:** ds.data-structures, tree

> **Comments:**
> **username_1**: Hi username_0. Please read the FAQ. This does not seem to be a research level question.  
> **username_2**: @username_1: 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).  
> **username_3**: @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.  
> **username_1**: @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).  
> **username_0**: @username_1 @Tsuyoshi - Thank you for the feedback, indeed I didn't supply enough detail in my question.  It's revised now - please take a look!  
> **username_4**: I'm confused.  Why isn't "inserted earlier" the same partial order as "proper ancestor"?  
> **username_2**: @JɛﬀE: Because tree rotations break the assumption that children are inserted after their parent.  
> **username_4**: 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.  
> **username_2**: @JɛﬀE: 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](http://en.wikipedia.org/wiki/File:B_tree_insertion_example.png) for an example.  

---

## 1 answers

### Answer by username_5 on 2012-03-05. Score: -2

Simple... keep two pointers, a **next** and a **previous**.

> **Comments:**
> **username_6**: I don't think this is what he means. The point is that if I give you all the possible insertion sequences of (the same) $n$ elements, some of them will generate the same B-tree. Now, I give you one of those B-trees, and I ask you for some insertion sequence that generated that tree.  

---

