JavaScript AVL Tree

Question

I have been working through Introduction to Algorithms 3rd Edition, and have implemented an AVL tree through prototypal inheritance. The code presented here does work as expected based on the tests that I currently have.

What I am looking for

• Review of overall implementation in terms of efficiency, and correctness
• Potential missed test cases in test.js
• Potential simplifications
• Adherence to code style and generally accepted standards for formatting

What I am not looking for

• Review of overall structure of test.js (I plan on cleaning this up on my own)

There are some other files which create the Binary Search Tree (BST) and that handle the tree itself; Tree and TreeNode objects. I did not include these for the review, but can if deemed necessary.

EDIT: I did include all files required to run tests.

How to run tests

To run the tests, first install the dependencies: npm i chai mocha nyc (I included nyc to test code coverage as well. Then you can run the tests using mocha --ui bdd. To run tests with coverage report nyc --reporter=text --extension=.js mocha --ui bdd test.js

avl-tree.js

const TreeNode = require( "../tree-node.js" );
const BST = require( "../BST/bst" );
const BalanceState = {
 UNBALANCED_RIGHT: 1,
 SLIGHTLY_UNBALANCED_RIGHT: 2,
 BALANCED: 3,
 SLIGHTLY_UNBALANCED_LEFT: 4,
 UNBALANCED_LEFT: 5
};
/**
 * @description AVL Trees are a type of BST, which abides by the following
 * properties:
 * - Abides by all the properties of a BST (Binary Search Tree)
 * - The heights of the left and right subtrees of any node differ by no more
 * than 1
 *
 * AVL trees maintain a worst-case height of O(log N). All of the following
 * operations also have a worst-case time complexity of O(log N): search,
 * insert, delete. When an imbalance of the subtree heights is detected,
 * rotations are performed on the node's subtree with the following cases:
 *
 * Case: Where insertion took place | Type of rotation
 * ----------------------------------------------------------------
 * 1) Left subtree of left child of x | rotateRight
 * 2) Right subtree of left child of x | rotateLeft, then rotateRight
 * 3) Left subtree of right child of x | rotateLeft
 * 4) Right subtree of right child of x | rotateRight, then rotateLeft
 * @param bst
 * @constructor
 */
function AVL ( bst = new BST() ) {
 this.tree = bst.tree;
}
/**
 * @description Calculate the height difference between the left and right
 * subtrees
 * @param node {object} Node to calculate the height difference for subtrees
 * @returns {number} Returns the height difference between the left and right
 * subtrees
 */
AVL.prototype.heightDifference = function ( node ) {
 return Math.abs( node.leftHeight() - node.rightHeight() );
};
/**
 * @public
 * @description Attempts to insert the node into the AVL Tree, performs
 * rotations when necessary
 * @param node {object} Instance of the object object to insert into the AVL
 * tree
 * @returns {object} Returns new root node for AVL Tree
 */
AVL.prototype.insert = function ( node ) {
 this.tree.root = this._insert( node, this.tree.root );
 this.tree.size++;
 return node;
};
/**
 * @private
 * @description Attempts to insert the node into the AVL Tree, performs
 * necessary rotations when necessary
 * @param root {object} Root node of subtree, defaults to root of AVL tree
 * @param node {object} Instance of the object object to insert into the AVL
 * tree
 * @returns {object} Returns new root node for AVL Tree
 */
AVL.prototype._insert = function ( node, root = this.tree.root ) {
 if ( !root ) {
 // Insert the node
 root = new TreeNode( node.parent, node.left, node.right, node.key, node.data );
 } else if ( this.compare( node.key, root.key ) < 0 ) {
 // Recurse into left subtree
 root.left = this._insert( node, root.left );
 } else if ( node.key > root.key ) {
 // Recurse into right subtree
 root.right = this._insert( node, root.right );
 } else {
 // Duplicate key, reduce size to account for increment in insert method
 this.tree.size--;
 }
 // Update height and re-balance
 return this.balance( node, root );
};
/**
 * @public
 * @description Attempts to delete the node with key from the AVL Tree,
 * performs rotations when necessary
 * @param key {*} Key of the node to delete. Data type must match that of the
 * key for the node
 * @returns {Object} Returns key of the node that was deleted from the tree
 */
AVL.prototype.delete = function ( key ) {
 this.tree.root = this._delete( key, this.tree.root );
 this.tree.size--;
 return key;
};
/**
 * @description Attempts to delete the node from the subtree. Afterwards, the
 * subtree is rebalanced in the outward flow of recursion.
 * @param key {*} Key for the node that is to be deleted
 * @param root {object} Root of the subtree to search through
 * @returns {object} Returns the new subtree root, after any deletions/rotations
 * @private
 */
AVL.prototype._delete = function ( key, root ) {
 if ( !root ) {
 // Account for the decrement in size; no node found
 this.tree.size++;
 return root;
 }
 if ( this.compare( key, root.key ) < 0 ) {
 // Recurse down the left subtree for deletion
 root.left = this._delete( key, root.left );
 } else if ( this.compare( key, root.key ) > 0 ) {
 // Recurse down the right subtree for deletion
 root.right = this._delete( key, root.right );
 } else {
 // Key matches the root of this subtree
 if ( !( root.left || root.right ) ) {
 // This is a leaf node, and deletion is trivial
 root = null;
 } else if ( !root.left && root.right ) {
 // Node only has a right leaf
 root = root.right;
 } else if ( root.left && !root.right ) {
 // Node only has a left leaf
 root = root.left;
 } else {
 /*
 * Node has 2 children. To delete this node, a successor must be determined.
 * Successor is:
 * 1) Smallest key in the right subtree
 * 2) Largest key in the left subtree
 */
 const successor = this.tree.minimum( root.right );
 root.key = successor.key;
 root.data = successor.data;
 root.right = this._delete( successor.key, root.right );
 }
 }
 if ( !root ) {
 return root;
 }
 // Update height and balance tree
 return this.deleteBalance( root );
};
/**
 * @description Performs the necessary rotations in order to balance the subtree
 * @param node {object} Node that is either inserted or deleted from subtree
 * @param root {object} Root node of the subtree
 * @returns {object} Returns the new root of the subtree after rotations
 */
AVL.prototype.balance = function ( node, root ) {
 root.height = root.getMaxHeight( root.leftHeight(), root.rightHeight() );
 const balanceState = getBalanceState( root );
 if ( balanceState === BalanceState.UNBALANCED_LEFT ) {
 if ( this.compare( node.key, root.left.key ) < 0 ) {
 // Rotation case 1
 root = root.rotateWithLeftChild();
 } else {
 // Rotation case 2
 return root.doubleRotateLeft();
 }
 }
 if ( balanceState === BalanceState.UNBALANCED_RIGHT ) {
 if ( this.compare( node.key, root.right.key ) > 0 ) {
 // Rotation case 4
 root = root.rotateWithRightChild();
 } else {
 // Rotation case 3
 return root.doubleRotateRight();
 }
 }
 return root;
};
/**
 * @description
 * @param root {object} Root of subtree
 * @returns {object} Returns the new root node after rotations
 */
AVL.prototype.deleteBalance = function ( root ) {
 root.height = Math.max( root.leftHeight(), root.rightHeight() ) + 1;
 const balanceState = getBalanceState( root );
 if ( balanceState === BalanceState.UNBALANCED_LEFT ) {
 let leftBalanceState = getBalanceState( root.left );
 // Case 1
 if ( leftBalanceState === BalanceState.BALANCED ||
 leftBalanceState === BalanceState.SLIGHTLY_UNBALANCED_LEFT ) {
 return root.rotateWithLeftChild();
 }
 // Case 2
 if ( leftBalanceState === BalanceState.SLIGHTLY_UNBALANCED_RIGHT ) {
 return root.doubleRotateLeft();
 }
 }
 if ( balanceState === BalanceState.UNBALANCED_RIGHT ) {
 let rightBalanceState = getBalanceState( root.right );
 // Case 4
 if ( rightBalanceState === BalanceState.BALANCED ||
 rightBalanceState === BalanceState.SLIGHTLY_UNBALANCED_RIGHT ) {
 return root.rotateWithRightChild();
 }
 // Case 3
 if ( rightBalanceState === BalanceState.SLIGHTLY_UNBALANCED_LEFT ) {
 return root.doubleRotateRight();
 }
 }
 return root;
};
/**
 * @description Compares keys of objects
 * @param a {int} Key from first object to compare
 * @param b {int} Key from second object to compare
 * @returns {number} Returns 1 if a > b, -1 if a < b, and 0 if a === b
 */
AVL.prototype.compare = function ( a, b ) {
 return a - b;
};
/**
 * @private
 * @description Gets the balance state of a node, indicating whether the left
 * or right sub-trees are unbalanced.
 * @param {object} node The node to get the difference from.
 * @return {int} The BalanceState of the node.
 */
function getBalanceState ( node ) {
 const heightDifference = node.leftHeight() - node.rightHeight();
 return heightDifference === -2
 ? BalanceState.UNBALANCED_RIGHT
 : heightDifference === 2
 ? BalanceState.UNBALANCED_LEFT : 0;
}
module.exports = AVL;

test.js

const assert = require( "chai" ).assert;
const mocha = require( "mocha" );
const AVL = require( "./avl-tree" );
const TreeNode = require( "../tree-node" );
const util = require( "../../../util" );
describe( "AVL Tree", () => {
 let avl = new AVL();
 const nodesToInsert = 1000;
 it( "Should initialize as an empty tree", () => {
 assert.equal( avl.tree.size, 0, `Did not initialize properly` );
 } );
 it( `Should insert up to ${nodesToInsert} nodes`, () => {
 for ( let i = 0; i < nodesToInsert; i++ ) {
 let newNode = new TreeNode( null, null, null, util.randomNumber( Number.MAX_SAFE_INTEGER, 1 ), util.randomNumber( 1000, 0 ) );
 assert( avl.insert( newNode ), `Could not insert node ${newNode}` );
 }
 } );
 it( `Should have a size <= ${nodesToInsert}`, () => {
 assert.isAtLeast( avl.tree.size, nodesToInsert, `Did not insert correct number of nodes` );
 } );
 it( "Should be balanced", () => {
 assert.isBelow( avl.heightDifference( avl.tree.root ), 2, "Tree is unbalanced" );
 } );
 it( "Should ignore inserting a duplicate node", () => {
 const minNode = Object.assign( {}, avl.tree.get( avl.tree.minimum().key ) );
 const previousSize = avl.tree.size;
 minNode.data = "Attempting to replace node";
 avl.insert( minNode );
 assert.equal( avl.tree.size, previousSize, "Duplicate node was inserted" );
 } );
 it( "Should retrieve the minimum node in the tree", () => {
 assert.exists( avl.tree.minimum(), "Minimum node not retrieved" );
 } );
 it( "Should retrieve the maximum node in the tree", () => {
 assert.exists( avl.tree.maximum(), "Maximum node not retrieved" );
 } );
 it( "Should not delete a non-existent key", () => {
 const previousSize = avl.tree.size;
 const rootNode = avl.tree.root;
 avl.delete( Number.MIN_SAFE_INTEGER );
 assert.equal( avl.tree.size, previousSize, "Duplicate node was inserted" );
 assert.deepEqual( avl.tree.root, rootNode, "Root node changed unexpectedly" );
 } );
 it( "Should retrieve, and delete the minimum node, then update tree size", () => {
 const minNode = Object.assign( {}, avl.tree.get( avl.tree.minimum().key ) );
 const previousSize = avl.tree.size;
 assert.equal( avl.delete( minNode.key ), minNode.key, "Delete did not return the key of the minimum node" );
 assert.notExists( avl.tree.get( minNode.key ), "Minimum node was not deleted" );
 assert.equal( avl.tree.size, previousSize - 1, "Tree Size did not update after deletion" );
 } );
 it( "Should retrieve, and delete the maximum node, then update tree size", () => {
 const maxNode = Object.assign( {}, avl.tree.get( avl.tree.maximum().key ) );
 const previousSize = avl.tree.size;
 assert.equal( avl.delete( maxNode.key ), maxNode.key, "Delete did not return the key of the maximum node" );
 assert.notExists( avl.tree.get( maxNode.key ), "Maximum node was not deleted" );
 assert.equal( avl.tree.size, previousSize - 1, "Tree Size did not update after deletion" );
 } );
 it( "Should remain balanced after deleting node with 2 children", () => {
 const leftChildOfRoot = Object.assign( {}, avl.tree.root.left );
 const previousSize = avl.tree.size;
 avl.delete( leftChildOfRoot.key );
 assert.notExists( avl.tree.get( leftChildOfRoot.key ), "Left node was not deleted" );
 assert.equal( avl.tree.size, previousSize - 1, "Tree Size did not update after deletion" );
 assert.notDeepEqual( avl.tree.root.left, leftChildOfRoot, "Left child of root was not deleted" );
 assert.isBelow( avl.heightDifference( avl.tree.root ), 2, "Tree is unbalanced" );
 } );
} );

bst.js

const TreeNode = require( "../tree-node.js" );
const Tree = require( "../tree" );
const util = require( "../../../util" );
/**
 * @description Creates a new instance of a BST (Binary Search Tree) object
 * @param tree {Tree} Optional parameter. Can either pass an existing tree, or
 * if omitted creates a new empty tree
 * @constructor
 */
function BST ( tree = new Tree() ) {
 this.tree = tree;
}
/**
 * @description Inserts a TreeNode object into the tree, in the proper position
 * following BST properties
 * @param node {object} Instance of TreeNode object
 * @returns {*} Returns the inserted node
 */
BST.prototype.insert = function ( node ) {
 if ( node ) {
 if ( !this.tree.root ) {
 this.tree.root = node;
 this.tree.size++;
 } else {
 let parent = null;
 let current = this.tree.root;
 while ( current ) {
 parent = current;
 current = util.compare( node.key, current.key ) < 0 ? current.left : current.right;
 }
 node.parent = parent;
 if ( node.key < parent.key ) {
 node.parent = parent;
 parent.left = node;// Insert left child
 } else {
 node.parent = parent;
 parent.right = node; // Insert right child
 }
 this.tree.size++;
 return node;
 }
 }
 return node;
};
/**
 * @description Attempts to delete the node from the tree provided.
 * @param node {object} Instance of TreeNode object
 * @returns {*} Returns deleted node if node was found and deleted, otherwise
 * returns null
 */
BST.prototype.delete = function ( node ) {
 if ( node ) {
 if ( !node.left ) {
 this.transplant( node, node.right );
 } else if ( !node.right ) {
 this.transplant( node, node.left );
 } else {
 let min = this.tree.minimum( node.right );
 if ( min.parent !== node ) {
 this.transplant( min, min.right );
 min.right = node.right;
 min.right.parent = min;
 }
 this.transplant( node, min );
 min.left = node.left;
 min.left.parent = min;
 }
 this.tree.size--;
 return node;
 }
 return null;
};
/**
 * @description Starting from the root, search for a node that has the
 * matching key provided
 * @param key {*} The key to find in the BST
 * @return {null|Object} Returns null if the node is not found,
 * or the node if the node is found
 */
BST.prototype.search = function ( key ) {
 let node = this.tree.root;
 while ( node ) {
 if ( util.compare( key, node.key ) < 0 ) {
 node = node.left;
 } else if ( util.compare( key, node.key ) > 0 ) {
 node = node.right;
 } else {
 return node;
 }
 }
 if ( !node ) {
 return null;
 }
};
/**
 * @description Transplants a subtree to a new parent. This is used when
 * deleting nodes, and rearranging the BST
 * @param subtreeA {object} Instance of TreeNode object
 * @param subtreeB {object} Instance of TreeNode object
 */
BST.prototype.transplant = function ( subtreeA, subtreeB ) {
 if ( !subtreeA.parent ) {
 this.tree.root = subtreeB;
 } else if ( subtreeA === subtreeA.parent.left ) {
 subtreeA.parent.left = subtreeB;
 } else {
 subtreeA.parent.right = subtreeB;
 }
 if ( subtreeB ) {
 subtreeB.parent = subtreeA.parent;
 }
};
/**
 * @description Determines the minimum depth of a binary tree node.
 * @param {object} node The node to check.
 * @return {int} The minimum depth of a binary tree node.
 */
BST.prototype.minDepth = function ( node ) {
 return node ? 1 + Math.min( this.minDepth( node.left ), this.minDepth( node.right ) ) : 0;
};
/**
 * @description Determines the maximum depth of a binary tree node.
 * @param {object} node The node to check.
 * @return {int} The maximum depth of a binary tree node.
 */
BST.prototype.maxDepth = function ( node ) {
 return node ? 1 + Math.max( this.maxDepth( node.left ), this.maxDepth( node.right ) ) : 0;
};
/**
 * @description Determines whether a binary tree is balanced.
 * @returns {boolean} Whether the tree is balanced.
 */
BST.prototype.isBalanced = function () {
 return this.tree.root ? this.maxDepth( this.tree.root ) - this.minDepth( this.tree.root ) <= 1 : false;
};
module.exports = BST;

tree.js

/**
 * @description Constructor to create an instance of a Tree object
 * @param root {object} Optional parameter. Can provide a root node to
 * initialize tree with
 * @constructor
 */
function Tree ( root = null ) {
 this.root = root;
 this.size = 0;
}
/**
 * @description Adds keys from leftmost to right most (in ascending order of
 * keys) to an array, then returns the array
 * @returns {Array} Returns the tree keys sorted in order of key value
 */
Tree.prototype.inOrderWalk = function () {
 let result = [],
 traverse = function ( node ) {
 if ( node !== null ) {
 traverse( node.left );
 result.push( node.key );
 traverse( node.right );
 }
 };
 traverse( this.root );
 return result;
};
/**
 * @description Adds keys with the subtree roots first, then the keys in those
 * subtrees
 * @returns {Array} Returns the tree keys sorted in pre-order
 */
Tree.prototype.preOrderWalk = function () {
 let result = [],
 traverse = function ( node ) {
 if ( node !== null ) {
 result.push( node.key );
 traverse( node.left );
 traverse( node.right );
 }
 };
 traverse( this.root );
 return result;
};
/**
 * @description Adds keys of the subtrees first, then the root keys for those
 * subtrees
 * @returns {Array} Returns the tree keys sorted in post-order
 */
Tree.prototype.postOrderWalk = function () {
 let result = [],
 traverse = function ( node ) {
 if ( node !== null ) {
 traverse( node.left );
 traverse( node.right );
 result.push( node.key );
 }
 };
 traverse( this.root );
 return result;
};
/**
 * @description Retrieves the minimum key value of nodes in the tree
 * @returns {*} Returns the minimum key value for the provided tree
 */
Tree.prototype.minimum = function ( node = this.root ) {
 while ( node.left !== null ) {
 node = node.left;
 }
 return node;
};
/**
 * @description Retrieves the maximum key value of nodes in the tree
 * @returns {*} Returns the maximum key value for the provided tree
 */
Tree.prototype.maximum = function ( node = this.root ) {
 while ( node.right !== null ) {
 node = node.right;
 }
 return node;
};
/**
 * @description If all keys are distinct, the successor of the node is that
 * which has the smallest key greater than 'node'.
 * @param node {object} Instance of a TreeNode node
 * @returns {*} Returns the successor node for the provided node
 */
Tree.prototype.successor = function ( node ) {
 if ( node.right !== null ) {
 return this.minimum( node.right );
 }
 let successor = node.parent;
 while ( successor !== null && node === successor.right ) {
 node = successor;
 successor = successor.parent;
 }
 return successor;
};
/**
 * @description If all keys are distinct, the predecessor of the node is that
 * which has the smallest key less than 'node'.
 * @param node {object} Instance of a TreeNode node
 * @returns {*} Returns the predecessor node for the provided node
 */
Tree.prototype.predecessor = function ( node ) {
 if ( node.left !== null ) {
 return this.maximum( node.left );
 }
 let predecessor = node.parent;
 while ( predecessor !== null && node === predecessor.left ) {
 node = predecessor;
 predecessor = predecessor.parent;
 }
 return predecessor;
};
/**
 * @description Performs a recursive search for the value provided, across all
 * nodes in the tree, starting from 'node'
 * @param value {*} Key to search for, must match data type of the key
 * @returns {*} Returns the node found matching the key, or null if no node was
 * found
 */
Tree.prototype.get = function ( value ) {
 let node = this.root;
 let traverse = function ( node ) {
 if ( !node || node.key === value ) {
 return node;
 }
 if ( value < node.key ) {
 return traverse( node.left, value );
 } else {
 return traverse( node.right, value );
 }
 };
 return traverse( node );
};
module.exports = Tree;

tree-node.js

/**
 * @description Constructor to create an instance of the TreeNode object, which is used by the
 * Tree object to construct various types of trees.
 * @param parent {object} Parent TreeNode object of the node
 * @param left {object} Left TreeNode object of the node
 * @param right {object} Right TreeNode object of the node
 * @param key {*} Identifier used to Retrieve a node
 * @param data {object} Can be any satellite data needed to be stored in the node
 * @constructor
 */
function TreeNode ( parent = null, left = null, right = null, key = null, data = null ) {
 this.parent = parent;
 this.left = left;
 this.right = right;
 this.key = key;
 this.data = data;
}
/**
 * @description Retrieves the height of the left subtree for the node
 * @returns {number} Height of the left subtree of the node, or -1
 */
TreeNode.prototype.leftHeight = function () {
 return this.left ? this.left.height : -1;
};
/**
 * @description Retrieves the height of the right subtree for the node
 * @returns {number} Height of the right subtree of the node, or -1
 */
TreeNode.prototype.rightHeight = function () {
 return this.right ? this.right.height : -1;
};
/**
 * @description Calculates the maximum height between the two subtree heights
 * @param a {int} Height of node subtree as an integer
 * @param b {int} Height of node subtree as an integer
 * @returns {number} Returns the higher of the two values + 1 to account for root
 */
TreeNode.prototype.getMaxHeight = function ( a, b ) {
 return Math.max( a, b ) + 1;
};
/**
 * @description Rotate BST node with right child
 * @returns {TreeNode} Returns the rotated node, which is new subtree root
 */
TreeNode.prototype.rotateWithLeftChild = function () {
 let tempNode = this.left;
 this.left = tempNode.right;
 tempNode.right = this;
 this.height = this.getMaxHeight( this.leftHeight(), this.rightHeight() );
 tempNode.height = this.getMaxHeight( tempNode.leftHeight(), this.height );
 return tempNode;
};
/**
 * @description Rotate BST node with right child
 * @returns {TreeNode} Returns the rotated node, which is new subtree root
 */
TreeNode.prototype.rotateWithRightChild = function () {
 let tempNode = this.right;
 this.right = tempNode.left;
 tempNode.left = this;
 this.height = this.getMaxHeight( this.leftHeight(), this.rightHeight() );
 tempNode.height = this.getMaxHeight( tempNode.rightHeight(), this.height );
 return tempNode;
};
/**
 * @description Rotate BST node with left child
 * @returns {TreeNode} Returns the rotated node, which is new subtree root
 */
/**
 * @description Double Rotate BST node: first left child, with its right child.
 * Then node k3 with new left child.
 * @returns {TreeNode} Returns the rotated node, which is the new subtree root
 */
TreeNode.prototype.doubleRotateLeft = function () {
 this.left = this.left.rotateWithRightChild();
 return this.rotateWithLeftChild();
};
/**
 * @description Double rotate BST node: first right child with its left child.
 * Then node k1 with new right child.
 * @returns {TreeNode} Returns the rotated node, which is the new subtree root
 */
TreeNode.prototype.doubleRotateRight = function () {
 this.right = this.right.rotateWithLeftChild();
 return this.rotateWithRightChild();
};
module.exports = TreeNode;
````

• Evan Bechtol: @greybeard yes, I stepped away for lunch but I will update as soon as I am back! I’ll include all 3 files
• greybeard: In _insert, you use both this.compare( node.key, root.key ) < 0 and node.key > root.key, and you could skip balance handling went not actually inserting.
• Evan Bechtol: @greybeard I have updated the question with the files: bst.js, tree.js, and tree-node.js. I also included instructions for how to run the tests locally
• FreezePhoenix: Don't use _ as a prefix for private methods. Instead, use closure syntax (Or some other way of actually making them "private").