Inserting a node in an AVL tree works the same way as in BST. In addition to inserting the node, we will also verify whether the tree is still balanced after the insertion, and if not, we will apply the rotation operations as needed.
The following code inserts a new node in an AVL tree:
insert(key) { this.root = this.insertNode(this.root, key); } insertNode(node, key) { // insert node as in BST tree if (node == null) { return new Node(key); } else if (this.compareFn(key, node.key) === Compare.LESS_THAN) { node.left = this.insertNode(node.left, key); } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) { node.right = this.insertNode(node.right, key); } else { return node; // duplicated key } // ...
