Efficient Searching with AVL Trees

The JavaScript code below implements demonstrates an AVL tree, which is a kind of self-balancing binary search tree. The program creates a new tree, inserts a bunch of values into it, displays the tree, then deletes half of the values and displays the tree again.

A binary search tree is a common method of sorting data that makes it possible to make large data sets searchable in a reasonable amount of time.  The basic idea is this.  The tree consists of a collection of nodes, each of which has some data value, as well as links to a pair of child nodes, often referred to as the “left” and “right” children.  The tree has only one “root” node, which has no parent node.  Values are “inserted” into the tree by starting at the root node and comparing the value to be inserted to the value in the node.  If the value to be inserted is less than the value present, then the process is repeated for the left child.  If greater, the right child is used instead.  The process repeats until there is no node at the end the left or right child link, at which time a new node with the inserted value is created in that position.  The values in the tree can then be sorted by starting at the root again and recursively adding the values from the left, current, and right tree nodes to an array.

One problem with this is that the tree can become “unbalanced” in certain situations.  For instance, if the values to be inserted into the tree were already sorted in ascending order, the resulting tree would consist entirely of a single branch of “right” children.  This structure would not provide any performance improvement over a simple list, and therefore would defeat the purpose using a binary search tree in the first place.  Still more problems crop up if values can be deleted from the tree as well as inserted.

The purpose of a self-balancing tree, then, is to modify the tree after each insert or delete to keep the tree from becoming unbalanced, and therefore preserve its performance advantages.  There are many algorithms out there that attempt to do this in various ways.  The method implemented below is called the “AVL” tree, after its creators, G. Adelson-Velskii and E.M. Landis.

<html>
<body>
<script type='text/javascript'>

// main

function main()
{
	// This function creates a list of random values,
	// inserts them in an AVL tree, and displays the tree.
	// It then deletes half of the values
	// and displays the tree again.

	var newline = "<br />";

	var treeToSortWith = new TreeAVL();	

	var valuesToSort = [];
	var numberOfValuesToSort = 16;
	
	for (var i = 0; i < numberOfValuesToSort; i++)
	{
		var valueRandom = Math.floor
		(
			Math.random() * numberOfValuesToSort
		);

		valuesToSort.push(valueRandom);
	}

	document.write
	(
		"valuesToSort is: " + valuesToSort + newline
	);

	document.write
	(
		"valuesToSort.length is: " + valuesToSort.length + newline
	);

	treeToSortWith.insertValuesMany(valuesToSort);

	document.write
	(
		"treeToSortWith after inserts is: " + newline
	);
	
	document.body.appendChild
	(
		treeToSortWith.toPreElement()
	);

	var treeNodesSorted = treeToSortWith.addDescendantsToListInOrder([]);

	var valuesSorted = [];

	for (var i = 0; i < treeNodesSorted.length; i++)
	{
		var treeNode = treeNodesSorted[i];
		valuesSorted.push(treeNode.value);
	}

	document.write
	(
		"valuesSorted after inserts but before deletes is: " + valuesSorted + newline
	);

	document.write
	(
		"valuesSorted.length after inserts but before deletes is: " + valuesSorted.length + newline
	);


	var numberOfValuesToDelete = valuesToSort.length / 2;
	var valuesToDelete = [];

	for (var i = 0; i < numberOfValuesToDelete; i++)
	{
		var valueToDelete = valuesToSort[i];
		valuesToDelete.push(valueToDelete);
	}

	document.write
	(
		"valuesToDelete is: " + valuesToDelete + newline
	);

	document.write
	(
		"valuesToDelete.length is: " + valuesToDelete.length + newline
	);

	for (var i = 0; i < valuesToDelete.length; i++)
	{
		var valueToDelete = valuesToDelete[i];
		treeToSortWith.deleteValue(valueToDelete);
	}	

	document.write
	(
		"treeToSortWith after deletes is: " + newline
	);

	document.body.appendChild(treeToSortWith.toPreElement());

	var treeNodesSorted = treeToSortWith.addDescendantsToListInOrder([]);

	var valuesSorted = [];

	for (var i = 0; i < treeNodesSorted.length; i++)
	{
		var treeNode = treeNodesSorted[i];
		valuesSorted.push(treeNode.value);
	}

	document.write
	(
		"valuesSorted after deletes is: " + valuesSorted + newline
	);

	document.write
	(
		"valuesSorted.length after deletes is: " + valuesSorted.length + newline
	);	
}

// classes

function TreeAVL(rootNode)
{
	this.rootNode = rootNode;
}
{
	TreeAVL.prototype.addDescendantsToListInOrder = function(listToAddTo)
	{
		return this.rootNode.addDescendantsToListInOrder(listToAddTo);
	}

	TreeAVL.prototype.deleteValue = function(valueToDelete)
	{
		this.rootNode.deleteValue(this, valueToDelete);
	}

	TreeAVL.prototype.insertValue = function(valueToInsert)
	{
		if (this.rootNode == null)
		{
			this.rootNode = new TreeNodeAVL
			(
				null, // parent
				valueToInsert
			);	
		}
		else
		{
			this.rootNode.insertValue(this, valueToInsert);
		}
	}

	TreeAVL.prototype.insertValuesMany = function(valuesToAdd)
	{
		for (var i = 0; i < valuesToAdd.length; i++)
		{
			var valueToAdd = valuesToAdd[i];
			this.insertValue(valueToAdd);
		}
	}

	TreeAVL.prototype.toPreElement = function()
	{
		var returnValue = document.createElement("pre");
		returnValue.innerHTML = this.toString();
		return returnValue;
	}

	TreeAVL.prototype.toString = function()
	{	
		return this.rootNode.toString("");
	}
}

function TreeNodeAVL(parent, value)
{
	this.id = TreeNodeAVL.IDNext++;

	this.parent = parent;
	this.value = value;
	this.children = [];
	this._height = null;
}
{
	// static variables

	TreeNodeAVL.IDNext = 0;

	// instance methods

	TreeNodeAVL.prototype.addDescendantsToListInOrder = function(listToAddTo)
	{
		var child = this.children[0];
		if (child != null)
		{
			child.addDescendantsToListInOrder
			(
				listToAddTo
			);
		}

		listToAddTo.push(this);

		child = this.children[1];
		if (child != null)
		{
			child.addDescendantsToListInOrder
			(
				listToAddTo
			);
		}

		return listToAddTo;
	}

	TreeNodeAVL.prototype.balanceAncestors = function(tree)
	{
		// Adapted from an algorithm described at the URL
		// https://en.wikipedia.org/wiki/AVL_tree

		var parentBeforeRotations = this.parent;

		var balanceFactor = this.heightOfChild1MinusHeightOfChild0();
		var balanceFactorAbsolute = Math.abs(balanceFactor);

		if (balanceFactorAbsolute >= 2)
		{
			var signOfBalanceFactor = balanceFactor / balanceFactorAbsolute;
			var childIndex = (signOfBalanceFactor + 1) / 2;

			var child = this.children[childIndex];
			var balanceFactorOfChild = child.heightOfChild1MinusHeightOfChild0();
			if (balanceFactorOfChild * signOfBalanceFactor < 0)
			{
				child.rotate(tree, childIndex);
			}
			this.rotate(tree, 1 - childIndex);
		}

		if (parentBeforeRotations != null)
		{
			parentBeforeRotations.balanceAncestors(tree);
		}		
	}

	TreeNodeAVL.prototype.deleteValue = function(tree, valueToDelete)
	{
		if (this.value == valueToDelete)
		{
			// Adapted from an algorithm described at the URL
			// https://en.wikipedia.org/wiki/AVL_tree

			var childIndex = null;
			var numberOfChildren = 0;

			for (var i = 0; i < this.children.length; i++)
			{
				var child = this.children[i];
				if (child != null)
				{
					childIndex = i;
					numberOfChildren++;
				}
			}

			var descendantToPromote;
	
			if (numberOfChildren == 2)
			{
				descendantToPromote = this.successor();
				this.value = descendantToPromote.value;
			}
			else 
			{
				descendantToPromote = this;
			}

			this.heightInvalidate();
			descendantToPromote.heightInvalidate();

			var childOfDescendantToPromote = (numberOfChildren == 0 ? null : descendantToPromote.children[childIndex]);
			
			if (childOfDescendantToPromote != null)
			{
				childOfDescendantToPromote.parent = descendantToPromote.parent;
			}
			
			if (descendantToPromote.parent == null)
			{
				tree.rootNode = childOfDescendantToPromote;
			}
			else
			{
				var childIndexOfDescendantToPromote = descendantToPromote.parent.children.indexOf(descendantToPromote);
				descendantToPromote.parent.children[childIndexOfDescendantToPromote] = childOfDescendantToPromote;

				descendantToPromote.parent.balanceAncestors(tree);
			}
		}
		else 
		{
			var childIndex = (valueToDelete <= this.value ? 0 : 1);
			var child = this.children[childIndex];
			child.deleteValue(tree, valueToDelete);
		}
	}

	TreeNodeAVL.prototype.height = function()
	{
		if (this._height == null)
		{
			this._height = this.heightRecalculate();
		}

		return this._height;
	}

	TreeNodeAVL.prototype.heightRecalculate = function()
	{
		var returnValue = 1;
		
		var heightOfHighestChild = 0;

		for (var i = 0; i < this.children.length; i++)
		{
			var child = this.children[i];
			if (child != null)
			{
				var heightOfChild = child.height();
				if (heightOfChild > heightOfHighestChild)
				{
					heightOfHighestChild = heightOfChild;
				}
			}
		}

		returnValue += heightOfHighestChild;

		return returnValue;
	}

	TreeNodeAVL.prototype.heightInvalidate = function()
	{
		if (this._height == null)
		{
			// hack
			// This is probably being called too often,
			// so this prevents unnecessary redundant invalidations.
			return;
		}

		this._height = null;
		if (this.parent != null)
		{
			this.parent.heightInvalidate();
		}
	}

	TreeNodeAVL.prototype.heightOfChild1MinusHeightOfChild0 = function()
	{
		var returnValue = 0;

		for (var i = 0; i < this.children.length; i++)
		{
			var child = this.children[i];
			if (child != null)
			{
				var heightOfChild = child.height();
				returnValue += 
				(
					(i * 2 - 1)
					* heightOfChild
				);
			}
		}

		return returnValue;
	}

	TreeNodeAVL.prototype.insertValue = function(tree, valueToInsert)
	{
		var childIndex = (valueToInsert <= this.value ? 0 : 1);
		
		var child = this.children[childIndex];
		
		if (child == null)
		{
			child = new TreeNodeAVL
			(
				this,
				valueToInsert
			);

			this.children[childIndex] = child;
			this.heightInvalidate();
	
			this.balanceAncestors(tree);
		}
		else
		{
			child.insertValue(tree, valueToInsert);
		}					
	}

	TreeNodeAVL.prototype.rotate = function(tree, directionToRotate)
	{
		var directionOther = 1 - directionToRotate;

		var childToPromote = this.children[directionOther];

		if (childToPromote != null)
		{
			childToPromote.parent = this.parent;
			if (this.parent == null)
			{
				tree.rootNode = childToPromote;
			}
			else
			{
				var childIndexOfThis = (this.parent == null ? null : this.parent.children.indexOf(this));
				childToPromote.parent.children[childIndexOfThis] = childToPromote;
			}

			this.children[directionOther] = 
			(
				childToPromote.children[directionToRotate]
			);

			if (this.children[directionOther] != null)
			{
				this.children[directionOther].parent = this;
			}

			childToPromote.children[directionToRotate] = this;
			this.parent = childToPromote;

			this.heightInvalidate();
			childToPromote.heightInvalidate();
		}
	}

	TreeNodeAVL.prototype.sibling = function()
	{
		var childrenOfParent = this.parent.children;
		var childIndexOfThis = childrenOfParent.indexOf(this);
		var childIndexOfSibling = 1 - childIndexOfThis;
		var returnValue = childrenOfParent[childIndexOfSibling];

		return returnValue;
	}

	TreeNodeAVL.prototype.successor = function()
	{
		var returnValue = null;
		var nodeCurrent = this.children[1];
	
		while (nodeCurrent != null)
		{
			returnValue = nodeCurrent;
			nodeCurrent = nodeCurrent.children[0];
		}

		return returnValue;
	}

	TreeNodeAVL.prototype.toString = function(indentSoFar)
	{	
		var returnValue = "";

		var tab = "\t";
		var newline = "\n";

		returnValue += 
			indentSoFar 
			+ "[Node "
			+ "id='" + this.id + "' "
			+ "parent='" + (this.parent == null ? -1 : this.parent.id) + "' "
			+ "value='" + this.value + "' "
			+ "height='" + this.height() + "' "
			+ "balance='" + this.heightOfChild1MinusHeightOfChild0() + "' "
			+ "]"
			+ newline;

		for (var i = 0; i < this.children.length; i++)
		{
			var child = this.children[i];
			if (child != null)
			{
				returnValue += child.toString
				(
					indentSoFar + tab
				);
			}
		}
	
		return returnValue;
	}
}

// run

main();

</script>
</body>
</html>

Advertisements
This entry was posted in Uncategorized and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s