4
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • $\begingroup$ Hi SRobertJames. Please read the FAQ. This does not seem to be a research level question. $\endgroup$
    – Kaveh
    Commented Apr 29, 2011 at 7:44
  • 1
    $\begingroup$ I'm confused. Why isn't "inserted earlier" the same partial order as "proper ancestor"? $\endgroup$
    – Jeffε
    Commented Apr 29, 2011 at 20:40
  • 1
    $\begingroup$ @JɛffE: Because tree rotations break the assumption that children are inserted after their parent. $\endgroup$
    – Tsuyoshi Ito
    Commented May 1, 2011 at 23:59
  • 2
    $\begingroup$ 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. $\endgroup$
    – Jeffε
    Commented May 2, 2011 at 2:21
  • 2
    $\begingroup$ @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. $\endgroup$
    – Tsuyoshi Ito
    Commented May 2, 2011 at 15:42

1 Answer 1

Reset to default
-2
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$
    – zotachidil
    Commented Mar 5, 2012 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.