The AVL tree is a self-balancing tree, meaning the tree tries to self-balance whenever a node is added to it or removed from it. The height of the left or right subtree of any node (and any level) differs by 1 at most. This means the tree will try to become a complete tree whenever possible while adding or removing a node.
Let’s start by creating our AVLTree class, which is declared as follows:
class AVLTree extends BinarySearchTree { constructor(compareFn = defaultCompare) { super(compareFn); this.compareFn = compareFn; this.root = null; } }
Since the AVL tree is a BST, we can extend the BST class we created and only overwrite the methods which are needed to maintain the AVL tree's balance, which ...