Re: Depth First Search in Binary Search Tree?
- From: "L7" <jesse.r.brown@xxxxxxxxx>
- Date: 27 Oct 2006 12:31:39 -0700
Howard wrote:
"L7" <jesse.r.brown@xxxxxxxxx> wrote in message
news:1161960241.962340.245010@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
A DFS is performed by checking the current node to see if it's the one
you
want (using whatever criteria you want to make that decision), and if you
haven't found it yet, then checking the ENTIRE subtree of one of the
children of the node, before moving on to check any of the other
children.
This method means that you'll get all the way to the bottom of the tree
down
one path before moving sideways at all. That's what "depth-first" means.
It looks "deeper" before it looks across. (An alternative search method
is
"breadth-first", which checks all child nodes of the current node before
moving downward to check their child subtrees.)
You keep using the term 'tree'. You should be using the term 'graph'.
Look at the subject. It's about searching in a binary search tree. So I've
restricted my discussions to trees. And the post I was responding to was
talking specifically about nodes called "TreeElement", which certainly
implies a tree.
Sure, if you're traversing a graph using the depth-first method, you might
output a spanning tree or list of edges or something, but when discussing
binary trees, you're probably looking for a specific node. And for binary
search trees especially, that is the main goal: to find a specific node
quickly.
Fair enough. But the design of the tree is what makes for fast
searches, not the algorithm used to traverse it. Actually, visiting all
nodes in the tree would defeat the purpose of the tree to begin with -
suposing two things: it is a binary search tree and you dont just want
to print an ordered list.
The example given at least _seemed_ to imply that reporting all nodes with a
specific depth had something to do with it being a depth-first search.
Perhaps that wasn't the point, but was just an example which happened to use
depth as a search criteria. But MY point was that it's the fact that you
fully explore the children (and their children, etc.) before moving on to
the siblings that makes it depth-first. I think perhaps the example was
poorly chosen, because it might make the OP think that depth in the tree had
something to with with why it was a depth-first search.
I still contend it's more accurately (specifically?) called a pre-order
traversal,
Absolutely, when applied to the tree - I agree.
even if it can also be considered a depth-first search.
Otherwise, what's the difference between the two terms, at least when
applied to trees?
None. So my post was misguided. I apologize. My intent was not to
contradict you, more to explain that when applied to trees, the DFS
doesnt make much sense (unless searching is not the purpose).
-Howard
.
- References:
- Depth First Search in Binary Search Tree?
- From: howa
- Re: Depth First Search in Binary Search Tree?
- From: Howard
- Re: Depth First Search in Binary Search Tree?
- From: howa
- Re: Depth First Search in Binary Search Tree?
- From: Howard
- Re: Depth First Search in Binary Search Tree?
- From: CBFalconer
- Re: Depth First Search in Binary Search Tree?
- From: Howard
- Re: Depth First Search in Binary Search Tree?
- From: L7
- Re: Depth First Search in Binary Search Tree?
- From: Howard
- Depth First Search in Binary Search Tree?
- Prev by Date: Re: Depth First Search in Binary Search Tree?
- Next by Date: Re: Depth First Search in Binary Search Tree?
- Previous by thread: Re: Depth First Search in Binary Search Tree?
- Next by thread: Re: Depth First Search in Binary Search Tree?
- Index(es):
Relevant Pages
|
|
