Learning JavaScript Data Structures and Algorithms - Third Edition

Adelson-Velskii and Landi’s tree (AVL tree)

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 ...