Assume in each case that you are inserting the items into a Binary Search tree that is initially empty. There are of course 4! permutations, but in many cases multiple permutations lead to the same tree. For example, 2134 and 2314 lead to the same tree (2 is the root, 1 is 2’s left child, 3 is 2’s right child, 4 is 3’s right child. That's why different trees have different probabilities (each permutation has probability 1/24, but some trees come form multiple permutations; the total of all of the probabilities should be 1). As another example, the permutation 2413 leads to the tree (expressed in "displayable" notation) chars="2143", children="20L0".
(40 points) This problem, though part of the written assignment, involves actually getting your code working on your computer. But, since it requires you to write a very small amount of code, and because the thought process involved is more along the lines of written problems in this course, I am including it in a written assignment.
When it comes to implementing ordered sets, Binary
Search Trees are generally better than array lists or linked lists,
because many O(n) operations on lists or vectors
become (on average) O(log n)
on BSTs. But there is at least one operation that is less efficient in
most cases on a BST than on a list: given an element of the structure,
find the next or previous in-order element of the structure. This is
especially true for nodes in the BST that have no children. Weiss’s
InOrder iterator class (page 594) has to maintain an
auxiliary stack in order to be able to do the next
advance(). It would also be nice to be able to have a
retreat() method in the InOrder
class as well. A call to advance() moves
the current position to the in-order successor of the current node,
while a call to retreat() would move to
the in-order predecessor of the current node. The obvious approaches to
efficiently supporting both advance() and
retreat() require a lot of extra space and time. So
let’s try an un-obvious approach.
There is a well-known way to make these operations more
efficient. We
can take advantage of the fact (we will prove it later) that more than
half of the references in a binary tree are null.
We replace each null left reference in the
tree by a reference to that node’s in-order predecessor, and replace
each null
right reference by a reference to the node’s in-order successor.
Traditionally, these in-order references have been called threads (same
word but no relation to “threads of execution”). If we use threads, we
need to be able to distinguish a thread from a regular left or right
pointer. Doing so only requires two additional bits in each node ,
although it’s easier to write the code (and thus we do it here) with
two boolean instance variables,
isLeftThread and isRightThread.
When one of these fields contains true, it indicates that the
corresponding reference in the node is a thread, rather than a “normal”
tree pointer.
You can do the
problem without reading this note; it is here for enlightenment of those who may
be concerned about the extra space needed for these new boolean fields.
This explanation uses some terminology that is outside the background
required of this course, so don't worry about it if you don't
understand all of it. I would be happy to talk with you about "masking"
if it is a new concept for you; it is not a required concept for this
course.
Generally there would be some field of the node that does not really
use all of the bits allotted to it, and some masking would allow us to
grab two of the bits of that field to use for the “is it a thread?”
information without taking up any extra space. In a language (like C or
C++) that allows typecasting between integers and pointers, we can
definitely do this: The value of a pointer will probably always end in
two 0 bits (because things “pointed to” will be aligned on longword
boundaries); we can use those bits “for free” (use masking to zero out
the last two bits when using the value as a pointer. Zero out
the
first 30 bits when testing for thread existence) That is, the extra
space would come at no cost. But this approach obviously requires (a
constant multiple) more time.
In the diagram below, normal pointers are shown as
solid lines, while threads are dotted lines. The threads from the left-
and right-most nodes represent null
references. These two null
references could be treated either as threads or regular pointers, but
since the former makes the code that you will write easier, the diagram
shows them as threads.
I am providing a complete
ThreadedBinaryNode class and JUnit tests in
ThreadedBinarySearchTreeTest. To help you with debugging,
I’m also providing a TestThreadedTree
class that prints results rather than doing unit tests. The file
expected_output_of_TestThreadedTree.txt gives the
results of a correct run of TestThreadedTree.
While these printed results should be useful for debugging, the JUnit
tests are what we will use to judge the correctness of your code.
Your job is to complete the
ThreadedBinarySearchTree class. I provided part of the
class to help you get oriented, so you only have to write three methods
(insert, toStringInOrder,
and toStringInReverseOrder). In fact, we
have provided the driver for insert; you
only need to write the recursive helper method that does the real work.
In order to get full credit, you must meet the following constraints:
-
insertmust have running time that is O(height of the tree). -
toStringInOrderandtoStringInReverseOrdermust not use a stack (nor any other additional collection, including an array) or recursion. - The code that you write for
toStringInOrderandtoStringInReverseOrdermay not referencerootat all. (To be specific, you can use the two given references torootbut you must not add any others).
Ideally,
ThreadedBinarySearchTree would implement the entire
SortedSet
interface. But that would have made this problem too long and
complicated for a small exercise. So I am only having you implement two
methods that are similar to methods from that interface.
Also, it would be desirable to
implement ThreadedInOrder, an in-order
iterator class for ThreadedBinarySearchTree.
But I did not want to add the complication of having you write yet
another class, so I chose to settle for the
toStringInOrder and toStringInReverseOrder
methods, which bring out the same threading issues.
Getting the code: The
starting code is available in your SVN repository in the
Threaded project. Treat the comments in that code as
part of the requirements for this problem.
I suggest that you begin by studying the
ThreadedBinaryNode code. Notice that this class and its
fields default (package friendly) visibility. In order to facilitate
debugging, I have written an unusual toString()
method for the ThreadedBinaryNode class.
It shows the node’s contents, the contents of its left and right
“children”, and the value of its boolean isLeftThread
and isRightThread fields. This
toString() method should be called whenever you need a
text representation of a node’s contents.
You should also study the
ThreadedBinarySearchTree code. This class has a single
instance variable, root, of type
ThreadedBinaryNode. No explicit constructor is needed; the
default constructor does what we need. Study the provided
find() method and its recursive helper method as an
example of how to work with the threads.
Testing: TestThreadedTree
is just provided for your convenience. The JUnit tests in
ThreadedBinarySearchTreeTest are how we will evaluate
the correctness of your program.
Turnin: Commit to your repository.
When we run your program for grading purposes, we may alter the test cases to use some different input strings, but we will not change the test code in any other way.