This web page publishes a Java binary tree class that supports insert and delete (among other things). This class was written to illustrate some of the difficulties imposed by Java's lack of pass-by-reference and pointers-to-pointers.
The Java class libraries are the best class libraries I have ever worked with. They dwarf the C++ standard template library. Even if you throw in the Boost library (www.boost.org) and commercial libraries like Rogue Wave, the Java libraries are far more extensive than anything available in C++. The Java Standard Edition and the Java Enterprise Edition libraries together include a vast body of code. If these libraries are joined with the libraries from Apache (www.apache.org), you can find almost any algorithm you might need.
The Java libraries allow complex systems to be implemented much faster than similar code could be implemented in C++. As with many virtues, there is another side to the advantages Java provides its users. Since so many algorithms are available from the library, some Java programmers have not developed a mastery of algorithms and data structures. As a result, they may never notice the effects of some of the design decisions that were made in the Java language.
Java supports pass-by-value arguments. Java does not have explicit pointers (although Java references are, obviously, pointers). This is good and bad. The lack of explicit pointers means that the dangers of memory corruption that exist in C and C++ are impossible in Java. But the lack of pointers-to-pointers and reference arguments in Java makes some algorithms more difficult to implement. For example, it would be nice to be able to implement a binary (no n-ary) tree that supports insert and delete, without including pointers back to the parent. This is possible in C/C++ because these languages support pointers to pointers. However, in Java the equivalent to a parent pointer is unavoidable.
This web page publishes a Java version of a binary tree class that supports insertion and deletion (among other things). The C++ version of this class uses pass-by-reference arguments and pointers to pointers. The C++ source code for this class can he found here.
I wrote the C++ binary tree class some time ago. More recently, I was working on a large Java project with a very tight deadline. I needed a binary tree class that would support both insert and delete. At the time I did not know about the java.util.TreeMap class, which is a Red-Black binary tree. So I thought that I would just convert my C++ code to Java. The lack of reference arguments and pointers to pointers made this more difficult than I expected. I found the TreeMap class and used this class. But I thought that it would be interesting to see how my binary tree algorithm turned out in Java. This is the result.
The conclusion from this translation from C++ is that not only are "parent pointers" needed in Java, but they would make the algorithm much simpler.
The BinaryTree class is a container for the binary tree. The root of the binary tree is a NodeReference object, which is a reference to a Node object (the node of the binary tree). The left and right branches of the Node object are themselves NodeReference objects. This is shown in the class diagram below:
The Java source code, Javadoc and Doxygen generated documentation are available in the links below.
Javadoc is great for documenting APIs and it does a good job of showing class hierarchy. Doxygen can generate documentation along with the source code, which can be a nice way to publish algorithms. So I thought that the contrast of the two tools would be interesting.
Ian Kaplan, September, 2003
Updated: December, 2005
back to Miscellaneous Java Related Topics
