You could use the "?" operator, but that has its own problems. For example, you could do int* link = (cond?) &left : &right. A short comment at the definition of link should be enough, I think.
>You might want to consider #define BST_LEFT 0 and #define BST_RIGHT 1.
That would defeat the point of using the array. The issue that I addressed was avoiding redundant code by using a boolean test to determine left or right and saving that value in the variable dir. It may look strange at first, but you get used to it quickly.
You are correct that it is plural of datum. I even looked it up in the webster's dictionary to be sure. :) But the singular construction may also be correct if you are referring to data as an "abstract mass noun," whatever that is.
Singular is datum, plural is data. But according to the rule of common use, either "data is" or "data are" would be acceptable even though the latter is grammatically correct while the former is not.
Yes, my counter example was a mix of these two cases.
Actually, it is true. The only way to get a degenerate tree is if only one path is available at each step along a search. Barring cases where different degenerate input is mixed together so that the tree is still degenerate, there are only two unique cases where this would happen (ignoring symmetric cases):
Hmm, how about: "However, despite a larger average height, Red Black trees can be more efficient than AVL trees because they spend less time maintaining a balanced structure".
I think the 2-3-4 tree is a B-tree with n=4. In that case, 2-3-4 trees are somewhat of an abstraction of B-trees. But are RB trees really an abstraction of the 2-3-4 trees? Aren't they more like a different representation that could be switched if needed? And if both trees convey the same information, abeit differently, then they are not really abstracting each other.(at least in my understanding of abstraction)
No, a special case is a 2-3-4 tree because it's a specialized B-tree. A Red Black binary search tree is most definitely an abstraction because it is a representation of the 2-3-4 tree using a more comfortable and simpler implementation than that of a B-tree. Maybe an abstraction of a special case?
I kind of like the "not necessarily a bad thing". Maybe even you could try something like "Not necessarily a bad thing: Red Black trees do not work nearly as hard to maintain their tree structure." I've written another way below.
Red Black trees are an abstraction of the infamous B-tree that is generally used for database applications. This abstraction has largely been forgotten because Red Black trees are believed to be simpler without it, but I feel that knowing the rationale behind the red black scheme helps to understand the concept. Red Black trees are not as optimal as AVL trees; they have a maximum height of 2 * log N. This is not necessarily a bad thing because Red Black trees do not work nearly as hard to maintain the strucutre. Thus, a Red Black tree may perform better than an AVL tree despite having a larger average height. Red Black trees are best suited to applications where the input is largely random with occasional spouts of ordered data.
Red Black trees are not as asymtotically efficient as AVL trees; they have a maximum height of 2 * log N. But they do have their advantages: Red Black trees do not work nearly as hard maintain their structure. Thus, a Red Black tree, with larger average height, may perform faster than an AVL tree. And if the data is random with occasional spouts of ordered data, choose a Red Black tree; reduced operation costs may more than make up for an increased tree size.
I've changed a few words here and there. Nothing too major.