Chapter 10: Self-Balancing Tree - bug in the removeNode(node, key) method

[thinktinker]

Attempted a removeNode using both the github's and site's downloadable code for the Self-balancing tree.

Error received are as follows:

const tmp = node.right;
TypeError: Cannot read property 'right' of undefined

Insertion of keys were carried out first, as reflected below:

const avltree = new AVLTree(); //used the AVLTree class
avltree.insert(10);
avltree.insert(30);
avltree.insert(20);
avltree.insert(15);
avltree.insert(35);
avltree.insert(25);
avltree.insert(28);

avltree.remove(30);

[loiane]

@thinktinker - thanks for opening the issue. I'll review it and get back to you!

[XwBourne]

change:
if (this.getBalanceFactor(node.left) === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {
return this.rotationLR(node.left);
}
to:
if (this.getBalanceFactor(node.left) === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {
return this.rotationLR(node);
}
Same thing on the right

[Jeffzholy]

@XwBourne agree with you that the equals should be removed here, and furthermore, we can even use the same code logic in the insertNode function, because the key comparison function can tell where the removed node comes from, which can save some function calls of getTreeHeight as the getBalanceFactor is calling it every time

@loiane I raised a PR on this #193, on this PR I also add some fixes and updates, details are included in the PR.

In addition, the "static" graph explanation in this book might not very intuitive, I found this article about AVL tree https://www.codingninjas.com/codestudio/library/deletion-in-avl-tree, and a very helpful animation https://www.cs.usfca.edu/~galles/visualization/AVLtree.html, you can just reproduce the example from the first link and test the insertNode and removeNode functions

[loiane]

@Jeffzholy merged, thanks!