Location: PHPKode > scripts > LLRB Tree > llrb-tree/LLRBTree.php
<?php

/*
 * 		LLRBTree is copyright � 2009. EarthWalk Software.
 * 		Licensed under the Academic Free License version 3.0
 *      Refer to the file named Copyright provided with the source.
 */
/**
 * 
 * LLRBTree (Left Leaning Red Black Tree).
 * 
 * LLRBTree implements the bTree abstract class to create a LLRB tree container (object).
 * @author Jay Wheeler.
 * @version 1.0
 * @copyright � 2009. EarthWalk Software.
 * @license refer to Copyright file provided with the source.
 * @package LLRBTree.
 * @subpackage LLRBTree.
 */
class LLRBTree extends bTree
{
	private $keyNode;
	protected $traversal;

	/**
	 * __construct.
	 * 
	 * Class constructor.
	 * @return tree object
	 */
	public function __construct()
	{
		parent::__construct();
		$this->keyNode = null;
		$this->traversal = array();
	}

	/**
	 * __destruct.
	 * 
	 * Class destructor.
	 * @return null
	 */
	public function __destruct()
	{
		parent::__destruct();
		unset($this->keyNode);
	}

	/**
	 * search.
	 *
	 * lookup a key in the tree.
	 * @param $key is the key to lookup in the tree.
	 * @param $data is the value to store in the key-ed node.
	 * @param $okayToAdd = true to add unfound node, false to return null if not found.
	 * @return $node = pointer to the node, null if not found.
	 */
	public function search($key, $data=null, $okayToAdd=false)
	{
		$this->allocateKeynode($key, $data);
		$node = $this->root;
		while ($node != null)
		{
			switch($node->compare($this->keyNode))
			{
			case 0:
				return $node;

			case -1:
				$node = $node->left();
				break;

			case 1:
				$node = $node->right();
				break;
			}
		}

		if (! $okayToAdd)
		{
			return null;
		}
		
		return $this->insert($key, $data);
	}

	/**
	 * insert.
	 *
	 * insert a key node in the tree.
	 * @param $key is the key to add to the tree.
	 * @param $data is the (optional) data to add to the key node.
	 * @return $node = pointer to the inserted key node.
	 */
	public function insert($key, $data=null)
	{
		$this->allocateKeynode($key, $data);
		$this->root = $this->insertNode($this->root, $this->keyNode);
		if ($this->root != null)
		{
			$this->root->flag(LLRBNode::BLACK);
		}
	}

	/**
	 * root.
	 * 
	 * Return the current tree root.
	 * @return $root = current tree root.
	 */
	public function root()
	{
		return $this->root;
	}

	/**
	 * nodes.
	 * 
	 * Return the number of unique nodes in the tree.
	 * @return $nodes = count of the unique nodes.
	 */
	public function nodes()
	{
		return $this->nodes;
	}

	/**
	 * firstNode.
	 * 
	 * Return the first item in the tree (in key order).
	 * @return $node = the first node in the tree, null if the tree is empty.
	 */
	public function firstNode()
	{
		$this->traversal = array();
		$this->current = $this->traverseBranch($this->root);
		return $this->current;
	}

	/**
	 * nextNode.
	 * 
	 * Return the next item in the tree (in key order).
	 * @return $node = the next node in the tree, null if at the tree end.
	 */
	public function nextNode()
	{
		$this->current = null;
		if (count($this->traversal) > 0)
		{
			$this->current = array_pop($this->traversal);
			if ($this->current != null)
			{
				if ($this->current->right() != null)
				{
					$this->current = $this->traverseBranch($this->current->right());
					return $this->current;
				}
			}
			
			if (count($this->traversal) > 0)
			{
				$this->current = array_pop($this->traversal);
				array_push($this->traversal, $this->current);
			}
			else
			{
				$this->current = null;
			}
		}
		
		return $this->current;
	}

	/**
	 * currentNode.
	 * 
	 * Returns the current tree node.
	 * @return $current = current tree node.
	 */
	public function currentNode()
	{
		return $this->current;
	}

	/**
	 * valid.
	 * 
	 * Returns the validity of the current node pointer
	 * @return boolean true = the current node pointer is valid.
	 */
	public function valid()
	{
		return ! is_null($this->current);
	}
	
	/**
	 * key.
	 * 
	 * Returns the current tree node key value.
	 * @return $key = current tree node value.
	 */
	public function key()
	{
		return $this->current->key();
	}
	
	/**
	 * current.
	 * 
	 * Returns the current tree node data.
	 * @return $current = current tree node data.
	 */
	public function current()
	{
		return $this->current->data();
	}

	/**
	 * next.
	 * 
	 * Moves current to the next node in the tree in In-Order Traversal.
	 * @return null.
	 */
	public function next()
	{
		return $this->nextNode();
	}
	
	/**
	 * rewind.
	 * 
	 * Moves the current node pointer to the first item in the tree.
	 * @return null.
	 */
	public function rewind()
	{
		$this->firstNode();
	}

	/**
	 * traverseBranch.
	 * 
	 * Traverse the supplied branch to the left leaf, storing the nodes met along the way.
	 * Returns the first node with no left child (a left leaf).
	 * @param $node = root of the branch to be traversed.
	 * @return $node = the pointer to the left leaf found, null if none found.
	 */
	protected function traverseBranch($node)
	{
		while(($node != null) && ($node->left() != null))
		{
			array_push($this->traversal, $node);
			$node = $node->left();
		}

		if ($node != null)
		{
			array_push($this->traversal, $node);
		}

		return $node;
	}

	/**
	 * insertNode.
	 * 
	 * Insert the node into the tree at the proper place, then balance the tree.
	 * @param $node is the tree root node.
	 * @param $key is the key to insert.
	 * @param $data is the (optional) data to store in the key.
	 * @return $node = the inserted node
	 */
	protected function insertNode($node, $keyNode)
	{
		if ($node == null)
		{
			$this->nodes++;
			return new LLRBNode($keyNode->key(), $keyNode->data());
		}

		switch($node->compare($keyNode))
		{
		case 0:
			$node->data($data);
			break;

		case -1:
			$node->left($this->insertNode($node->left(), $keyNode));
			break;

		case 1:
			$node->right($this->insertNode($node->right(), $keyNode));
			break;
		}

		return $this->fixUp($node);
	}

	/**
	 * fixUp.
	 * 
	 * Balance the tree and fix up the colors on the way up the tree.
	 * @param $node is the tree root node.
	 * @param $deleting = true if deleting a node, false if inserting
	 * @return $node = the root node following all fixUps.
	 */
	protected function fixUp($node, $deleting=false)
	{
		if ($this->isRed($node->right()))
	    {
	    	if ($deleting ||
	    	    ((! $deleting) && (! $this->isRed($node->left()))))
	    	{
	    		$node = $this->rotateLeft($node);
	    	}
		}

		if (($this->isRed($node->left())) &&
		    ($this->isRed($node->left()->left())))
	    {
	    	$node = $this->rotateRight($node);
	    }

	    if (($this->isRed($node->left())) &&
	        ($this->isRed($node->right())))
        {
        	$this->flipColors($node);
        }

		return $node;
	}

	/**
	 * isRed.
	 * 
	 * Return true if the node is valid and colored red.
	 * @param $node = the node to check
	 * @return boolean result of validation (true = red).
	 */
	protected function isRed($node)
	{
		if (($node != null) && ($node->flag() == LLRBNode::RED))
		{
			return true;
		}
		return false;
	}

	/**
	 * rotateLeft.
	 * 
	 * Perform a rotate left operation around the node
	 * @param $node = node to rotate to root.
	 * @return $root is the new root node
	 */
	protected function rotateLeft($node)
	{
		$root = $node->right();
		$node->right($root->left());
		$root->left($node);
		$root->flag($node->flag());
		$node->flag(LLRBNode::RED);
		return $root;
	}

	/**
	 * rotateRight.
	 * 
	 * Perform a rotate right operation around the node
	 * @param $node = node to rotate to root.
	 * @return $root is the new root node
	 */
	protected function rotateRight($node)
	{
		$root = $node->left();
		$node->left($root->right());
		$root->right($node);
		$root->flag($node->flag());
		$node->flag(LLRBNode::RED);
		return $root;
	}

	/**
	 * flipColors.
	 * 
	 * Flip the colors of the current node and its (2) children.
	 * @param $node = node to rotate to root.
	 * @return $root is the new root node
	 */
	protected function flipColors($node)
	{
		$node->flag(! $node->flag());
		$child = $node->left();
		$child->flag(! $child->flag());
		$child = $node->right();
		$child->flag(! $child->flag());
	}

	/**
	 * treeTop.
	 * 
	 * Return the minimum item in the tree (the top).
	 * @return $node = node containing the smallest item.
	 */
	public function treeTop()
	{
		return $this->leaf($this->root);
	}

	/**
	 * leaf.
	 * 
	 * Return the left leaf in the supplied branch.
	 * @param $node = branch to get the left leaf from
	 * @return $node = node containing the smallest item.
	 */
	public function leaf($node)
	{
		if ($node != null)
		{
			while($node->left() !== null)
			{
				$node = $node->left();
			}
		}
		return $node;
	}

	/**
	 * deleteMin.
	 * 
	 * Delete the smallest item in the tree.
	 * @return null
	 */
	public function deleteMin()
	{
		$this->root = $this->deleteMinNode($this->root);
		if ($this->root != null)
		{
			$this->root->flag(LLRBNode::BLACK);
		}
	}

	/**
	 * delete.
	 * 
	 * Delete a node in the tree.
	 * @param $key = name of the key to delete
	 * @return null
	 */
	public function delete($key)
	{
		$this->allocateKeynode($key);
		$this->root = $this->deleteNode($this->root, $this->keyNode);
		if ($this->root != null)
		{
			$this->root->flag(LLRBNode::BLACK);
		}
	}

	/**
	 * deleteMinNode.
	 * 
	 * Delete the minimum node in the branch.
	 * @param $node = branch to delete minimum node in.
	 * @return $node = new root after deletion.
	 */
	protected function deleteMinNode($node)
	{
		if ($node->left() == null) 
		{
			return null;
		}

		if ((! $this->isRed($node->left())) && (! $this->isRed($node->left()->left())))
		{
			$node = $this->moveRedLeft($node);
		}

		$node->left($this->deleteMinNode($node->left()));
		if ($this->nodes > 0)
		{
			$this->nodes--;
		}
		return $this->fixUp($node, true);
	}

	/**
	 * moveRedLeft.
	 * 
	 * Move the left red node.
	 * @param $node = node to be moved.
	 * @return $node is the new root.
	 */
	protected function moveRedLeft($node)
	{
		$this->flipColors($node);
		if (($node->right() != null) &&
		    ($this->isRed($node->right()->left())))
		{
			$node->right($this->rotateRight($node->right()));
			$node = $this->rotateLeft($node);
			$this->flipColors($node);
		}
		return $node;
	}

	/**
	 * moveRedRight.
	 * 
	 * Move the right red node.
	 * @param $node = node to be moved.
	 * @return $node is the new root.
	 */
	protected function moveRedRight($node)
	{
		$this->flipColors($node);
		if (($node->left() != null) && ($this->isRed($node->left()->left())))
		{
			$node = $this->rotateRight($node);
			$this->flipColors($node);
		}
		return $node;
	}

	/**
	 * deleteNode.
	 * 
	 * Delete a node in the tree.
	 * @param $node = node to delete.
	 * @param $keyNode = node containing the name of the key to delete
	 * @return null
	 */
	protected function deleteNode($node, $keyNode)
	{
		if ($node->compare($keyNode) < 0)
		{
			if ((! $this->isRed($node->left())) && 
			   	(! $this->isRed($node->left()->left())))
			{
				$node = $this->moveRedLeft($node);
			}
			$node->left($this->deleteNode($node->left(), $keyNode));
		}
		else
		{
			if ($this->isRed($node->left()))
			{
				$node = $this->rotateRight($node);
			}

			if (($node->compare($keyNode) == 0) && ($node->right() == null))
			{
				return null;
			}

			if ((! $this->isRed($node->right())) && 
			    (($node->right() != null) && (! $this->isRed($node->right()->left()))))
			{
				$node = $this->moveRedRight($node);
			}

			if ($node->compare($keyNode) == 0)
			{
				$leafNode = $this->leaf($node->right());
				$node->data($leafNode->data());
				$node->key($leafNode->key());
				$node->right($this->deleteMinNode($node->right()));
			}
			else
			{
				$node->right($this->deleteNode($node->right(), $keyNode));
			}
		}

		if ($this->nodes > 0)
		{
			$this->nodes--;
		}

		return $this->fixUp($node, true);
	}

	/**
	 * allocateKeynode.
	 * 
	 * Create a new class keynode if none exists.  Add key and data to the keynode.
	 * @param $key
	 * @param $data
	 * @return none
	 */
	protected function allocateKeynode($key, $data=null)
	{
		if ($this->keyNode == null)
		{
			$this->keyNode = new LLRBNode($key, $data);
		}
		else
		{
			$this->keyNode->key($key);
			$this->keyNode->data($data);
		}
	}

}
Return current item: LLRB Tree