Tree
Input
Assignment
-
We are trying to invent a game called Double Cross the Boss.
It works by applying a rotate at a selected tree node if certain
conditions apply. If the rotate occurs you have double crossed the
boss because you have done something to take his/her job.
-
The condition can be either answering a (phoney) question and perhaps
measuring your support, as in the descendents of your node as a proportion
of the descendents of your bosses node.
-
You might also use flattery, where you select an ancestor node and
try to say nice things so you go up past your boss.
-
My imagination seems to be failing me. However, we do have an assignment:
implement rotations. You have the skeleton here. We can also implement splay
trees if you like.
Note: I find it easier to describe rotations by the child node before
the rotation, that way whether the rotation is a left rotation or
a right rotation is implicit.
-
Also implement deletions.
References