AVL-Tree

AVL-Tree copied to clipboard

Hi,

I cloned your repo to use it as a basis for an assignment to students (who have to extend it to support k-th smallest in log(n) time). One of my students (@EriGoldenberg) reported a potential bug with the remove method. Basically, after a removal, an element appears as a duplicate (and thus the size of the tree is not decreased). Here is the test case:

	@Test
	public void test1() {
	 AvlTree<Integer> tree = new AvlTree<Integer>();
	 tree.insert(16);
	 tree.insert(24);
	 tree.insert(36);
	 tree.insert(19);
	 tree.insert(44);
	 tree.insert(28);
	 tree.insert(17);
	 tree.insert(61);
	 tree.remove(17);
	 } 

After the removal, element 16 appears twice in the tree. Can you please confirm this is a problem in your implementation?

Best regards,

Nazareno

@nmaguirre @EriGoldenberg Glad you found the library useful and thanks for the report!

I do not have a test environment handy at the moment but have no doubts this is a bug.

This library is curated both from the original implementation by Mark Allen Weiss and an implementation of remove from https://www.dreamincode.net/forums/topic/214510-working-example-of-avl-tree-remove-method/ . So the implementation of remove most certainly needs work.

I welcome any fixes but also understand that may be asking a lot given the nature of the code.

@nmaguirre @EriGoldenberg Perhaps I spoke too soon. Would you be willing to test the fixes from https://github.com/justinethier/AVL-Tree/pull/3 to confirm if it solves your problem with duplicates?

Trying to apply the patch, but the code by @meysam81 doesn't compile. There are some methods missing (e.g., getBalance), and some fields/methods have not been fully renamed (e.g., rightChild).

@meysam81 perhaps you didn't upload one of your local commits?

Regards and thanks for the prompt response!

Hey everyone,

I don't remember much from the code right now, but I'm trying to get my head around it and hopefully you'll hear from me ASAP.