PHP AVL Binary Tree

AceInfinity · Oct 7, 2013

AVL Binary Search Tree

Wikipedia said:
In computer science, an AVL tree (Adelson-Velskii and Landis' tree, named after the inventors) is a self-balancing binary search tree, and it was the first such data structure to be invented.[1] In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.

The AVL tree is named after its two Soviet inventors, G. M. Adelson-Velskii and E. M. Landis, who published it in their 1962 paper "An algorithm for the organization of information".[2]

AVL trees are often compared with red-black trees because both support the same set of operations and take O(log n) time for the basic operations. For lookup-intensive applications, AVL trees are faster than red-black trees because they are more rigidly balanced.[3] Similar to red-black trees, AVL trees are height-balanced, but in general not weight-balanced nor μ-balanced for any \scriptstyle \mu\leq\tfrac12;[4] that is, sibling nodes can have hugely differing numbers of descendants.

More information: AVL tree - Wikipedia, the free encyclopedia

The objective is to keep the height of these trees Θ(log

), which requires the heights of the left and right subnodes to differ by at most +/- 1. (|left_h - right_h| = 1). This means we want to try to keep the height of the right side at most the height of the left side + 1, for every node within the tree. The way this is done to keep a relatively balanced tree (an AVL tree), is through a process known as a binary tree rotation. Worst case scenario is when the height of the tree == the number of nodes within the tree - 1 (because the last leaf node will have a height of 0, not 1. Think of an array where the first index starts at 0, instead of 1).

A recurrence formula for the height of a node in question is:
N_h = N_h-1 + N_h-2 + 1

1 is added onto the other two heights because we also need to include the root node as a level which is used to calculate the height.

Let's look at an example of an AVL tree, then go through what the height of the tree is and each of the nodes are, then I'll show an example of a rotation...

AVL Tree:

Now with an indication of what the height of the tree is (height from the root node), and all other subnodes:

And you can see by the images above how this is also a great structure for sorting as well. The significance of an AVL tree is not defined by it's levels but rather left and right halves. Notice how the numbers that branch off of each parent node are all numbers greater than or less than the main parent node. Node elements on the left are less than the parent node element, and nodes below the parent on the right are greater than the parent node element, reversely. There are ways to traverse this implementation of a binary tree to grab all of these numbers in order, known as the in-order traversal.

Now for an example of a tree rotation... We do this in order to "AVL-itize" a binary tree to maintain an AVL format as much as possible. So, say for instance, using the above AVL tree, we were to add an element of the value 51. Now we've got a difference of 2 nodes, and not +/- 1 like mentioned earlier:

Here the objective is to move 51 to the 3rd level essentially to make this binary tree more balanced. The AVL tree looks like this after the final rotation:

This rotation actually happens in constant time (more specifically O(1) time). The procecure above actually a combination of rotations (Because not all the time a single minor rotation of 3 nodes will do the trick). The rotations are minor rotations of 3 nodes however, formatted in a small triangular form. If there is no node to make up the 3rd node then we assume we are rotating an invisible node because the rotation is still the same with or without that 3rd node. (FYI: If a parent node has no child nodes or has one child node, the other missing node(s) are defined to typically have a height (h) of -1, because this makes our formula for calculating the height of nodes easier. This is because the height of node N is the max height of subnode N_a, and subnode N_b + 1. If there are no child nodes at a particular place in the tree, then both child nodes have a height of -1, and the max of -1 and -1 is -1, and -1 + 1 == 0. So N has a height of 0.)

I'm currently writing a wrapper implementation of AVL trees in C++, I've got pretty much all of it down other than the predecessor and successor, as well as maybe some other methods to count total nodes and such, but, I'm still doing bugtesting at this point.

Code for output above:

Code:

[NO-PARSE]node *p = 0;
avl_tree avlbst;
avlbst.insert(65, p);
avlbst.insert(41, p);
avlbst.insert(50, p);
avlbst.insert(20, p);
avlbst.insert(26, p);
avlbst.insert(29, p);
avlbst.insert(11, p);

std::cout << "In-order traversal:\n";
avlbst.inorder(p); std::cout << '\n' << std::endl;

std::cout << "Tree height (root node height): " << avlbst.node_height(p) << std::endl;
std::cout << "Max element: " << avlbst.minimum(p)->element << std::endl;
std::cout << "Min element: " << avlbst.maximum(p)->element << std::endl;[/NO-PARSE]

You'll notice that sorting is as easy as insertion and doing an in-order traversal of the binary (AVL) tree. Insertion takes a max of Θ(n*log

) time (because each insertion takes h time, but h is guaranteed to be Θ(n*log

)), and the in-order traversal itself is in linear Θ

time.

AceInfinity · Oct 13, 2013

Here's my implementation so far... I've still got methods to work on as you can see, needs to be more thouroughly tested, but it works from the first few tests I did yet:

AVL_Tree.h

Code:

[plain]// AVL_Tree.h

// AVL Binary Search
// Copyright © AceInfinity
// Tech.Reboot.Pro - 2013

#ifndef __AVL_TREE__
#define __AVL_TREE__

#include <Windows.h>
#include <iostream>

template <typename T> struct node
{
	T element;
	node *left;
	node *right;
	T height;
};

template <typename T> class avl_tree
{
public:
	typedef node<T>* nodeptr;
	avl_tree() { }
	bool insert(T, node<T>* &);
	node<T>* find(T, node<T>* &);
	node<T>* minimum(node<T>*);
	node<T>* maximum(node<T>*);
	void empty(node<T>* &);
	bool is_empty(node<T>* &);
	node<T>* copy_node(node<T>* &);
	void copy_node(node<T>* &, node<T>* &);
	bool remove(T, node<T>* &);
	T remove_min(node<T>* &);
	T remove_max(node<T>* &);
	node<T>* predecessor(node<T>*); // TODO
	node<T>* successor(node<T>*); // TODO
	int node_height(node<T>*);
	void preorder(node<T>*);
	void inorder(node<T>*);
	void postorder(node<T>*);
	int count(node<T>* &); // TODO
private:
	void init_node(T, node<T>* &);
	int count_nodes(node<T>* &, node<T>* &); // TODO
	node<T>* rotate_left(node<T>* &);
	node<T>* rotate_right(node<T>* &);
	node<T>* dbl_rl(node<T>* &);
	node<T>* dbl_rr(node<T>* &);
};


// Insert a node with the specified value.
template <typename T>
bool avl_tree<T>::insert(T x, node<T>* &p)
{
	if (is_empty(p)) init_node(x, p);
	else
	{
		if (x < p->element)
		{
			insert(x, p->left);
			if ((node_height(p->left) - node_height(p->right)) == 2)
			{
				if (x < p->left->element) p = rotate_left(p);
				else p = dbl_rl(p);
			}
		}
		else if (x>p->element)
		{
			insert(x, p->right);
			if ((node_height(p->right) - node_height(p->left)) == 2)
			{
				if (x > p->right->element) p = rotate_right(p);
				else p = dbl_rr(p);
			}
		}
		else return false;
	}
	T m, n, d;
	m = node_height(p->left);
	n = node_height(p->right);
	d = max(m, n);
	p->height = d + 1;
	return true;
}

// Finds an element within the tree, and returns a pointer to
// the node if found, otherwise a null pointer.
template <typename T>
node<T>* avl_tree<T>::find(T x, node<T>* &p)
{
	if (is_empty(p)) return 0;
	if (x < p->element) return find(x, p->left);
	if (x>p->element) return find(x, p->right);
	return p;
}

// Finds the node with the minimum value and returns a pointer
// to that node if found, otherwise a null pointer.
template <typename T>
node<T>* avl_tree<T>::minimum(node<T>* p)
{
	if (is_empty(p)) return p;
	while (!is_empty(p->left)) { p = p->left; }
	return p;
}

// Find the node with the maximum value, and returns a pointer
// to that node if found, otherwise a null pointer.
template <typename T>
node<T>* avl_tree<T>::maximum(node<T>* p)
{
	if (is_empty(p)) return p;
	while (!is_empty(p->right)) { p = p->right; }
	return p;
}

// Empty the tree from the specified root node
template <typename T>
void avl_tree<T>::empty(node<T>* &p)
{
	if (!is_empty(p))
	{
		empty(p->left);
		empty(p->right);
		delete p;
		p = 0;
	}
}

// Checks if the tree is empty
template <typename T>
bool avl_tree<T>::is_empty(node<T>* &p)
{
	return p == 0;
}

// Return a pointer to a copy of the specified node
template <typename T>
node<T>* avl_tree<T>::copy_node(node<T>* &p)
{
	if (is_empty(p)) return p;
	node<T>* x = new node<T>;
	x->element = p->element;
	x->left = copy_node(p->left);
	x->right = copy_node(p->right);
	return x;
}

// Copy a tree to a destination
template <typename T>
void avl_tree<T>::copy_node(node<T>* &src_p, node<T>* &dest_p)
{
	empty(dest_p);
	dest_p = copy_node(src_p);
}

// Removes a node with the specified element from the tree.
// Returns true of the value was removed, false if the value
// was not removed because it could not be found or the node<T>* is null.
template <typename T>
bool avl_tree<T>::remove(T x, node<T>* &p)
{
	if (is_empty(p)) return false;
	if (x < p->element) return remove(x, p->left);
	else if (x > p->element) return remove(x, p->right);
	else if ((p->left == 0) && (p->right == 0))
	{
		delete p;
		p = 0;
	}
	else if (p->left == 0)
	{
		delete p;
		p = p->right;
	}
	else if (p->right == 0)
	{
		p = p->left;
		delete p;
	}
	else p->element = remove_min(p->right);
	return true;
}

// Removes the node with the minimum value from the tree and
// returns the element of the node which was deleted.
template <typename T>
T avl_tree<T>::remove_min(node<T>* &p)
{
	T c;
	if (p->left == 0)
	{
		c = p->element;
		p = p->right;
	}
	else c = remove_min(p->left);
	return c;
}

// Removes the node with the maximum value from the tree and
// returns the element of the node which was deleted.
template <typename T>
T avl_tree<T>::remove_max(node<T>* &p)
{
	T c;
	if (p->right == 0)
	{
		c = p->element;
		p = p->left;
	}
	else c = remove_max(p->right);
	return c;
}

// Finds and returns a node<T>* to the predecessor of the specified node.
// Returns a null pointer if not found.
template <typename T>
node<T>* avl_tree<T>::predecessor(node<T>* p)
{
	// p->left if node exists, otherwise highest node on left without branding right
	// return 0 if there is no successor
	return 0;
}

// Finds and returns a node<T>* to the successor of the specified node.
// Returns a null pointer if not found.
template <typename T>
node<T>* avl_tree<T>::successor(node<T>* p)
{
	// p->right if node exists, otherwise highest node on right without branding left
	// return 0 if there is no successor
	return 0; // TODO
}

// Returns -1 if the node is null, otherwise the
// height of the specified tree
template <typename T>
int avl_tree<T>::node_height(node<T>* p)
{
	int t;
	if (is_empty(p)) return -1;
	t = p->height;
	return t;
}

// Preorder traversal
template <typename T>
void avl_tree<T>::preorder(node<T>* p)
{
	if (!is_empty(p))
	{
		std::cout << p->element << std::endl;
		preorder(p->left);
		preorder(p->right);
	}
}

// Inorder traversal
template <typename T>
void avl_tree<T>::inorder(node<T>* p)
{
	if (!is_empty(p))
	{
		inorder(p->left);
		std::cout << p->element << std::endl;
		inorder(p->right);
	}
}

// Postorder traversal
template <typename T>
void avl_tree<T>::postorder(node<T>* p)
{
	if (!is_empty(p))
	{
		postorder(p->left);
		postorder(p->right);
		std::cout << p->element << std::endl;
	}
}

template <typename T>
int avl_tree<T>::count(node<T>* &p)
{
	if (is_empty(p)) return -1;
	return dbl_rl(p)->element;
}

template <typename T>
void avl_tree<T>::init_node(T x, node<T>* &p)
{
	p = new node<T>;
	p->element = x;
	p->left = 0;
	p->right = 0;
	p->height = 0;
}

template <typename T>
int avl_tree<T>::count_nodes(node<T>* &a, node<T>* &b)
{
	return 0;
}

// Rotations

template <typename T>
node<T>* avl_tree<T>::rotate_left(node<T>* &original)
{
	node<T>* x;
	x = original->left;
	original->left = x->right;
	x->right = original;
	original->height = max(node_height(original->left), node_height(original->right)) + 1;
	x->height = max(node_height(x->left), original->height) + 1;
	return x;
}

template <typename T>
node<T>* avl_tree<T>::rotate_right(node<T>* &original)
{
	node<T>* x;
	x = original->right;
	original->right = x->left;
	x->left = original;
	original->height = max(node_height(original->left), node_height(original->right)) + 1;
	x->height = max(original->height, node_height(x->right)) + 1;
	return x;
}

template <typename T>
node<T>* avl_tree<T>::dbl_rl(node<T>* &original)
{
	original->left = rotate_right(original->left);
	return rotate_left(original);
}

template <typename T>
node<T>* avl_tree<T>::dbl_rr(node<T>* &original)
{
	original->right = rotate_left(original->right);
	return rotate_right(original);
}

#endif

[/plain]

Example Usage:

Code:

[plain]int main(void)
{
	avl_tree<int>::nodeptr p = 0;
	avl_tree<int> avl;
	avl.insert(21, p);
	avl.insert(17, p);
	avl.insert(48, p);
	avl.insert(52, p);
	avl.insert(29, p);
	avl.insert(33, p);
	avl.insert(11, p);
	std::cout << "Min Element: " << avl.maximum(p)->element << std::endl;
	std::cout << "Max Element: " << avl.minimum(p)->element << std::endl;
	std::cout << "InOrder: " << std::endl;
	avl.inorder(p);
	return 0;
}[/plain]

If you don't like the explicit declaration of the nodeptr, you can make things easier by declaring your own instead:

Code:

[plain]typedef node<int>* nodeptr[/plain]

:thumbsup2:

PHP AVL Binary Tree

AceInfinity

Emeritus, Contributor

AceInfinity

Emeritus, Contributor