i guess i am just a bit hesitant becuase the definition given in the
homework:
public class TreeNode {
Object value;
TreeNode left;
TreeNode right;
}
is not the same as that used in the example you gave us (in Tree.java)
I have re-written the function insert in TreeNode.java and it works,
so is that a stopping point, or do i need to modify it to conform to the
definition above?
I see! My mistake: I should have explicitly listed the
lecture notes as a starting point.
On an unrelated note, a word about 3.5. My solution to
the problem is shorter than my solutions to 1.5 and 2.5.
However, I did spend more time thinking about the problem before
diving in. Be sure that you schedule some time mulling this
problem over in advance: time spent thinking will pay off.
Perhaps a few suggestions might start the process. Once you
understand the problem, you can think about it on the bus. I
found myself drawing pictures when stuck in meetings.
Hans has divised an alternative solution strategy to mine.
He creates a sorted binary decision tree and grows by inserting new
permutations. He generates each of the n! permutations in turn,
and walks the tree looking for the insertion point. Each node is
decorated with a decision (if (b < c)) which you test ("Hmm.
My permutation is (b, a, c, d), so b < c is true.") He found
it simpler to build the tree in this manner than to use the technique
I described.
There are various ways to generate all the permutations.
One that is simple to descibe generates the permutations recursively.
Starting with the list of all permutations of n-1 objects, we add
element n in each of the n slots.
Thus if n = 4, we have the 6 permutations of 3
items.
1 2 3
1 3 2
3 1 2
2 1 3
2 3 1
3 2 1
We take each in turn, and 'weave' the new value 4 in. (Best
viewed in monospace)
1 2 3 4
1 2 4 3
1 4 2 3
4 1 2 3
and so on for the next 5 permutations of 3 things. If
you look closely at the 6 permutations of 3 items, you will see that
that this was obtained from the 2 permutations of 2 items by the same
manner. This happens to be related to the steps of the insertion
sort algorithm, and I believe that the decisions Hans uses are the
same ones that Insertion Sort would use.
Another way to generate the permutations is to fix 4 in each
of the 4 slots and to permute the other 3 items. When
listing the permutations, all that start with 4 would be first, then
all with 4 in the second place, and so on.
Another approach would be to look for the 'best' questions to
ask, in hopes of getting a tree that is better balanced than the
Insertion Sort tree.
- jeff parker
