The Self-Balancing Binary Search Tree Protest

[Mike Bentley]

As most people are probably aware from the ACF Nationals thread, the final match ended up being decided on a protest on the following question (note that I do not have access to the version of this question that appeared in the packets—I’m almost positive it’s exactly the same as this, but if not I would greatly appreciate an update):

Proving the namesake property in one of these data structures relies on the Dynamic Finger Conjecture, and data structures without their characteristic property can obtain it by running an algorithm named for Day, Stout and Warren. In one of these data structures, their characteristic property is maintained through operations like a zig-zag during searches. Because they are often difficult to implement, skip lists are sometimes used instead. Data structures without this property are called degenerate and approximate linked lists. Some of these data structures impose requirements that all nodes and leaves be the same color. Exemplified by AVL and Red-Black Trees, for 10 points, name these special types of binary search trees that often perform tree rotations to guarantee tree heights of at most log n.
ANSWER: Self-_Balanced_ Binary Search Tree (or Self-_Balancing_ Binary Search Tree or Height-_Balanced_ Binary Search Tree; prompt on “Tree”, “Binary Tree” or “Binary Search Tree”)

From what I understand, Minnesota buzzed in with “Tree” somewhere around the “Because they are often difficult to implement clue”. They were prompted and then said “B-Tree”. They were then given an additional prompt and came up with the correct answer of “Balanced” at some point.

My ruling on this was as follows:

The Dynamic Finger Conjecture applies to Splay Trees, a type of self-balancing Binary Search Tree (see http://books.google.com/books?id=Sya5NZ ... re&f=false. While a regular “finger search” could hypothetically apply to a B-Tree, this specific conjecture does not).
The Day, Stout and Warren algorithm specifically applies to balancing a binary search tree that was previously unbalanced (see http://penguin.ewu.edu/~trolfe/DSWpaper/). I can’t find any references to this applying to a B-Tree.
The clue about zig-zag operations applies specifically to Splay Trees.

Thus, none of the previous clues applied specifically to a B-Tree. While a B-Tree is a type of self-balancing tree (although not a self-balancing binary tree), it was not referred to at all in the question prior to the buzz. All of the previously described clues did apply to trees, so that correctly prompted. Similarly, “Binary Tree” or “Binary Search Tree” would have also been a promptable buzz at that point in the question. I see this as similar to the following situation: If the question was on “Greedy Algorithms” and all of the previous clues had been on graph algorithms, a buzz with “Change Making Algorithms” would be incorrect, even though these are (often) a type of Greedy Algorithm.

One more further point of clarification: The “B” in a B-Tree is sometimes (although not officially) used to stand for “Balanced”. However, as the giveaway indicates, this question was on “special types of binary search trees”, data structures that are never classified as being a type of B-Tree. While a player could have inadvertently been correct by using the full, unofficial name of a B-Tree, it is not correct to classify self-balancing binary trees as a type of these “Balanced-Trees”, thus B-Tree should not have been promptable.

Anyway, congratulations to both Stanford and Minnesota for putting up an impressive final match. It’s regretful that the final decision came down to a protest, but I believe the correct call was made in the end.

[salamanca]

I want to reiterate my congratulations to both Minnesota A and Stanford and certify that the question Mike posted upthread was the question used in the packet.

Thanks,

[nobthehobbit]

I thought I'd add a note on this tossup, seeing as I was there when Mike playtested it.

I went down to Seattle for UW's Penn Bowl mirror (again: Mike, you're awesome for putting me up!) and while we were waiting around for people to show up for that (or maybe it was Penn Bowl trash on the Sunday) Mike decided to test the CS tossups he was writing for ACF Nationals on us. UW's resident CS expert got all but that one, which he negged midway through (with "red-black trees" initially, and then "binary search trees" after a prompt, if I recall correctly. I can't recall what the tossup looked like at the time, though). Mike then made a note that the clue was neg bait and presumably changed it after the fact; I got the tossup after the giveaway.

So I find it somewhat amusing that a tossup I playtested--and answered correctly in said playtesting, if only at the end of the question--decided the ACF Nationals final (if in a strange, and perhaps unfortunate, way).

Anyway, congratulations to Stanford, Minnesota, State College, and everyone else who competed at ACF Nationals.

[Captain Sinico]

I wasn't sure about this resolution at the time, but I agree with it currently as it seems that several clues apply only to splay trees and, therefore, that B trees, like anything other than splay trees or classes containing them (one of which is the answer,) is wrong. Therefore, even though any game, much less such a well-played championship, ending in that way is unsatisfying, justice was served to the extent possible given the circumstances.
I think this could have been avoided with a more precise question. I see some ways to adapt this question into a more precise one with minimal editing. The best of these is to slightly change the tossup such that the answer is "balance" or "self-balancing," which is especially easy since it's effectively what we have here already. In fact, one of the sentences ("Data structures without this property...") actually does have the answer "balance" while the others have "balanced trees" and some super/subclasses as acceptable answers. A second solution is to make the answer "splay trees," as the first three or so clues are about splay trees anyway. I consider this less optimal than the first solution since it reduces the importance of the answer while increasing difficulty as a trade-off for clarity.
Of course, the (slight) vagueness of the question would not have been a problem if the given answers had been judged correctly. Zeke negging Rob on his offer of "B trees" would have been been deemed satisfactory to all, I think, but I don't see how Zeke could have done anything about that. In fact, I think Zeke did exactly the right thing: prompting when not certain is exactly what a moderator ought to do and even I, who know a good deal more computer science than Zeke, wasn't certain that "B trees" shouldn't be prompt-worthy there.
That leads me to my last point: the "do not accept" is a lost art that should make a comeback, especially for science questions. In addition to the inappropriate further prompt on "B trees" by an outstanding moderator, I saw another top-shelf reader accept "carbocation" for "carbonanion," which was only noticed when I saw the moderator was in very brief trepidation for some reason and asked "It's not actually carbonanion, is it?" Nor are those anything like the first such instances of this issue. So, please try to include "do not accepts" for answers that are wrong but close phonically, ideologically, or especially both, to the right answer, especially in science.

MaS

[Susan]

That leads me to my last point: the "do not accept" is a lost art that should make a comeback, especially for science questions. In addition to the inappropriate further prompt on "B trees" by an outstanding moderator, I saw another top-shelf reader accept "carbocation" for "carbonanion," which was only noticed when I saw the moderator was in very brief trepidation for some reason and asked "It's not actually carbonanion, is it?" Nor are those anything like the first such instances of this issue. So, please try to include "do not accepts" for answers that are wrong but close phonically, ideologically, or especially both, to the right answer, especially in science.

This is a really good point; a lot of protests can be avoided by having scrupulously clear and complete answer lines. I tried to do that for a lot of my science, but it hadn't occurred to me to cover semi-related things that sound the same and could confuse a moderator without expertise in that area (like carbanion vs. carbocation).

[jonpin]

That leads me to my last point: the "do not accept" is a lost art that should make a comeback, especially for science questions. In addition to the inappropriate further prompt on "B trees" by an outstanding moderator, I saw another top-shelf reader accept "carbocation" for "carbonanion," which was only noticed when I saw the moderator was in very brief trepidation for some reason and asked "It's not actually carbonanion, is it?" Nor are those anything like the first such instances of this issue. So, please try to include "do not accepts" for answers that are wrong but close phonically, ideologically, or especially both, to the right answer, especially in science.

For what it's worth, there was a healthy sprinkle of DNAs throughout the packets, including some with explanations like "[answer] is not valid at any point, because [clue] refers only to [correct answer]". Without the set in front of me, I can't come up with concrete examples, but once they're online, you'll see what I'm talking about.

[Captain Sinico]

It's possible that I've overstated the case, in which case I'll just say that a well-placed "Do not accept" on this and several other questions would have gone a long way toward fixing things and that I feel and, indeed, have always felt that more attention ought be paid to answer lines.

MaS