Re: Inorder Traversal of B-Tree

annamalai wrote:
On Jan 28, 9:12 pm, user923005 <dcor...@xxxxxxxxx> wrote:
On Jan 28, 5:20 pm, annamalai <annamalai.gurus...@xxxxxxxxx> wrote:

Can anybody tell me whether an in-order traversal of a B-Tree will
result in the keys being listed in ascending order? I am trying to
find out the correct way to do an inorder traversal of a B-Tree. Any
help much appreciated.

What do you suppose that "inorder" means in terms of traversal?

When you are in doubt, simple things can get confusing.

No doubt. I've experienced that recently myself... :-)

Most of the
discussion about tree traversal talks in terms of node (rather than
the keys). Even the Wikipedia article on Tree_traversal, talks in
terms of node. I guess that is because they are talking about binary
search trees. I am looking for multiway tree traversal, specifically
B-Tree traversal.

Let me then rephrase my question slightly. While traversing a B-Tree,
what does it mean to visit a node? Do I visit only one key, or do I
visit all the keys?

The important thing to understand here is that the answer to your
original question (whether traversing the tree will result in the
keys being listed in ascending order) is *necessarily* "yes".

The reason a B-tree works (and the reason a binary search tree works)
is that the B-tree follows a set of rules, and these rules ensure
that the nodes (and the key or keys within the nodes) are arranged
in such a way that order is preserved. If a node in a B-tree has
two keys, the rules of the B-tree dictate that all of the nodes to
the left of the first key have nothing but smaller keys in them,
that all of the nodes pointed to by the middle pointer have nothing
but keys between the original node's key's values, and that all of
the nodes to the right of the node have keys greater than both the
keys in the original node. A B-tree guarantees this specifically
so that it can keep the nodes in order; if the tree did not capture
the ordering, it wouldn't be possible to do the "divide and conquer"
approach that is what makes B-tree retrieval fast.

So a correct in-order traversal of a B-tree will return the keys in
order, and an implementation of a correct in-order traversal will
be built upon the properties of a B-tree that allow it to keep the
keys in order.

- Logan
.

Relevant Pages

  • Re: Inorder Traversal of B-Tree
    ... result in the keys being listed in ascending order? ... find out the correct way to do an inorder traversal of a B-Tree. ... discussion about tree traversal talks in terms of node (rather than ...  While traversing a B-Tree, ...
    (comp.programming)
  • Re: VBScript to traverse all Registry keys
    ... By saying traversing is to just loop through all registry key values. ... output this string or number to a screen or a file. ... traverse all the keys and just display it. ...
    (microsoft.public.scripting.vbscript)
  • Re: Inorder Traversal of B-Tree
    ... result in the keys being listed in ascending order? ... find out the correct way to do an inorder traversal of a B-Tree. ... Even the Wikipedia article on Tree_traversal, ... While traversing a B-Tree, ...
    (comp.programming)
  • Re: Data structure for fast associative array with lookup by both key and index
    ... I'm looking for a data structure for an associative array with the ... The first tree is an ordinary self- ... that contains a collection of keys. ...
    (comp.programming)
  • Re: compare nested lists
    ... keys are kept and values are ... ((typep (class-of tree) ... for mismatch = ... (when keys-missing-on-right ...
    (comp.lang.lisp)