User talk:Mikeblas/Archives/2013/July

Red-black tree

I wish to revert this edit, but would like to ask you first what you think.

There are two potential issues. The first is that, though Stack Overflow may not be an authoritative source, it may still be an explanatory source. I am not aware that Wikipedia considers citing an explanatory source poor form, but of course am open to being taught otherwise.

The second issue is that your edit (maybe inadvertently) demands a citation to a mathematical/logical, non-empirical fact necessarily already supported within the very article you have edited. Consider by way of analogy that one may demand a citation to the empirical fact that Sweden lies north of Italy, plus further citations to the empirical facts that Stockholm and Rome are their countries' respective capitals—but that, having demanded these, one may not then logically demand yet a further citation that Stockholm lies north of Rome. This is equally true, whether that Stockholm lies north of Rome has been directly attested by a competent authority or whether the fact is merely, implicitly inferred by the article from the earlier mentioned facts. Further analogies include that one may demand a citation that Herbert von Bismarck was Otto von Bismarck's son, but may not then demand a further citation that Herbert was younger than Otto; and so on.

Actually, citations in mathematics (and by extension in this instance in the mathematical facts of computer science) are unusual in that they are seldom accepted, or demanded, as valid reasons that one should believe a fact. Consider: if a well-known cartographer asserts that Sweden lies north of Italy, then you will probably believe him; but if a well-known mathematician asserts that the sum of the squares of the legs of a right triangle equals the square of the hypotenuse—well, if you are mathematically inclined then you will expect the mathematician to have supplied (or at least obviously to have been able to supply) at least the outline of a proof.

The principal purpose of a mathematical citation is usually to credit the source, rather than to rely upon it.

At any rate, the fact to which citation is demanded is already supported within the Red-black tree article, itself. I wonder whether therefore the edit in question should not be reverted. Tbtkorg (talk) 15:53, 12 July 2013 (UTC)

Hello Tbtkorg!

I think there are a few different problems with that article and the reference.

One is that the statement made in the topic ("Red–black trees are in general not weight-balanced, that is sibling nodes can have hugely differing numbers of descendants.") is inherently unverifiable. The subject of this article is a data structure used in computer programs; to make a general statement about the shape of that data structure, we would need to survey representative implementations of that data structure, see if they were balanced or not, and extrapolate our observations to all the other implementations that we haven't surveyed. Further, the article doesn't explain when this generality is or is not discretely established. I suspect the author meant that "red-black trees are not weight-balanced by definition". This might be an easier claim to find reliable references to support.

A minor problem is that the term "weight" of a node is a bit muddled; Wikipedia's Weight-balanced tree article uses a very different definition of "weight" than the reference does, and a different definition than the red-black tree article does. While that's confusing, it's easy to stipulate that we're concerned only with the definition in the article at hand.

Of course, that still leaves us short of the issue that StackOverflow isn't a reliable reference. If we want this explanation in the article, we need to find a reliable source for the explanation. Or, we need to move the explanation into the article and cite it appropriately--that might be easier. -- Mikeblas (talk) 17:38, 14 July 2013 (UTC)

Acknowledged. Tbtkorg (talk) 14:54, 18 July 2013 (UTC)