BIND - sorting of reverse domain.

[Mark_Andrews at isc.org]

> >	At that point you also have the node that immediately preceeds the
> >	node you were looking for if you cared to save it as you traversed
> >	the tree.  Try it with any binary tree.  You either hit the node
> >	you are looking for, you traverse the node immediately preceeding
> >	it or there is no preceeding node.  The same can be said for the
> >	node after the one you were looking up.
> 
> In a binary tree, one may have the node that precedes it, but there is no
> guarentee that the CONTENTS of that node will also happen to be the immediate
> ly
> adjacent sequential element, as would be true for a sorted list.

	I never said that.  I said you would pass it and that you could save
	it.

>  The tree
> contents could represent an element for an item which sequentially FOLLOWS th
> e
> current target just as well as it could represent one which PRECEDES, and
> neither need be adjacent.  The sequentially adjacent element could be in ANY 
> of
> the nodes in the tree in the path from the target back toward the tree root -
> it need not be in the immediately preceding level.
> 
> Do you even understand what a balanced binary search tree is?  Your statement
> implies that you do not; I clearly infer such.  Perhaps you need to review th
> e
> characteristics of such.
> 
>                      A
>                   B     C
>                 D   E F   G
> 
> In this simple tree, the equivalent sorted list (left to right) is "DBEAFCG".
> Here, E and F have an adjacent node which (although in the path from the tree
> root) is NOT adjacent in the tree:  E-A, and A-F.  A is NOT an "immediately
> preceding node" to any of D, E, F, or G.
> 
> One has to remember the ENTIRE path from the root to the leaf, not just the
> immediately preceding node, for your algorithm to work.

	No.  One just has to remember the appropriate node.  This can be
	determined *as* you perform the traversal.

		H
	   D          L
	B     F    J     N

	Now look for A, C, E, G, I, K, M and O.  In all cases your
	search will pass the node immediately before and after the
	name being looked up or you can determine there isn't one.
	The same applies for unbalanced trees.  You also don't need
	to remember the whole path.  Just the appropriate nodes.

	For A and C you will be at B and you will have traversed D.
	for E and G you will be at F and you will have traversed D and H.
	for I and K you will be at J and you will have traversed H and L.
	for M and O you will be at N and you will have traversed L.

	To find the preceeding node everytime you would take the right
	branch you save the current node.
	To find the next node everytime you would take the left branch you
	save the current node.

	With one traversal you either have the node you are looking for or
	you know the node before and after the key if they exist.

	Mark
--
Mark Andrews, Internet Software Consortium
1 Seymour St., Dundas Valley, NSW 2117, Australia
PHONE: +61 2 9871 4742                 INTERNET: Mark.Andrews at isc.org