Significant Comparisons in Binary Search Trees?
Hello,
I am a bit confused as to what constitutes asignificant comparison in a binary search tree. I have an assignment where I need to modify a BST class to keep track of the number of significant comparisons being done for an analysis of running time. The class supports search, insert, and delete and the assignment stipulates that each method needs to update the number of comparisons instance variable that you implement. The comparison count is obvious for the pure recursive search, but I don't understand what to and what not to count in the delete and insert methods. Is this a standard term that is defined explicitly, or is this my professor demanding of us to think critically for better or worse? Thanks for any help.
[752 byte] By [
Dmitriva] at [2007-11-27 10:36:04]
I know what a BST tree is, and I know what comparisons are, but I don't know what 'significant comparisons' are. Maybe if you could tell me what the difference between a significant and insignificant comparison was I'd be in business.
Google didn't help me. Did find this:
http://en.wikipedia.org/wiki/Tree_traversal
No mention of "significant comparison" from a quick scan.
Write the BST and worry about that detail later.
%
> I know what a BST tree is, and I know what comparisons are, but I
> don't know what 'significant comparisons' are. Maybe if you could tell
> me what the difference between a significant and insignificant
> comparison was I'd be in business.
According to some notes on my desk, a 'significant comparison' causes
a rotation of a subtreee in a 'red-black' tree; but I don't know what it is
supposed to be in a general sorted binary tree. My guess is that this is
not a generally accepted term. I might be wrong again ...
kind regards,
Jos
ps. Hi Duffy, how are you doing?
JosAHa at 2007-7-28 18:38:47 >
> Hi Jos, I'm doing better. How's by you? Any
> interesting projects these days?
Hi Duffy; Q1 was a bit quiet and boring but in Q2 I've been working my
head off again: supply chain planning; very interesting and complex
stuff and I'm still working on it. What's been keeping you from the street?
kind regards,
Jos
JosAHa at 2007-7-28 18:38:47 >
