ignl / binarysearchtrees

Java binary search trees implementations and tests: AVL Tree, Red black tree, Scapegoat tree, Splay tree, Treap

BinarySearchTrees

Java binary search trees implementations and tests: AVL Tree, Red black tree, Scapegoat tree, Splay tree, Treap

Blog post and benchmarks: https://intelligentjava.wordpress.com/2015/04/09/self-balancing-binary-search-trees-comparison/

To run benchmarks:
cd Trees
mvn clean install
java -jar target/benchmarks.jar

binarysearchtrees's Issues

BenchmarkList file disappears

Trying to run individual benchmark files in Eclipse is running into this:
java -jar benchmarks.jar

Exception in thread "main" java.lang.RuntimeException: ERROR: Unable to find the resource: /META-INF/BenchmarkList
at org.openjdk.jmh.runner.AbstractResourceReader.getReaders(AbstractResourceReader.java:96)
at org.openjdk.jmh.runner.BenchmarkList.find(BenchmarkList.java:104)
at org.openjdk.jmh.runner.Runner.internalRun(Runner.java:251)
at org.openjdk.jmh.runner.Runner.run(Runner.java:203)
at org.openjdk.jmh.Main.main(Main.java:69)

Running the Eclipse-generated benchmarks.jar file also gives the same error.

It works fine when using from CLI, as per your instructions. Upon doing so, I see the BenchmarkList and CompilerHints files under target/classes/META-INF, and so too in the generated jar. This is not the case when running from within Eclipse. I've tried recreating the project a couple of times, making sure to use the same JMH archetype and version (1.7.1), but no dice.

This appears to be an issue with the IDE not generating or not keeping around the BenchmarkList and CompilerHints files, somehow related to the JMH library and possibly its maven archetype. Are these generated, or hand written? If they're hand written, a workaround would be to stash them in a resource directory.

I'm wondering what your IDE setup looks like, if you're using one, and if so - how you may have managed to avoid or got around this issue.

Right to use

Hi @ignl ,

I wish to use and modify your AVL Tree code to use in a data structure visualizing application for the "Advanced Data Structures" course of the university in which I study Computer Science. However, your repository has no license, so I can't. Would you mind adding a license?

Thanks for sharing your code,

AVLTree insert problem

Hi ignl, I am learning the data struct lessons, and now about AVL tree. I'm glad to find your code here, it's helpful.

But I have a question about the AVLTree implementaion. It will not work properly in some situations I think, the problem code is below:

@Override
public Node insert(int element) {
    Node newNode = super.insert(element);
    rebalance((AVLNode)newNode);
    return newNode;
}

The problem is, for an AVL tree, we need to reanlance the subtree from the parent of the inserted node, along with it's ancestor, until the root node, to guarantee the whole tree is balanced. But it's not done in your code, just one balancing here.

For example, if we insert serial numbers of 20 21 18 17 19, we got an AVL tree, now if we insert number 15, this tree will not be balanced.

What do you think about this, did I misunderstood your code?

AVL delete too many break statements

Great idea trying to re-use the same rebalancing code in the AVL delete algorithm but it will not correctly handle Fibonacci trees although this is probably very rare in practice. The AVL delete conditions are described here (there are two additional cases to handle compared to insert):
http://adtinfo.org/libavl.html/Deleting-an-AVL-Node-Step-3-_002d-Update.html