Бинарное дерево поиска на PHP

Этот пост явился следствием прочтения вот этого перевода статьи о структурах данных для PHP-прогрммистов. В посте было рассказано о некоторых структурах данных, в том числе о бинарном дереве поиска, но самую интересную часть, то есть удаление узлов бинарного дерева, автор обошел стороной.

После прочтения перевода у меня появилось жгучее желание реализовать это дерево на PHP полнофункционально, то есть, включая удаление узлов из него, что я и сделал ниже по тексту:)
Обратите внимание, что я не призываю использовать бинарное дерево поиска написанное на PHP в реальном коде, реализация носит исключительно образовательный характер).

И так, реализация дерева и операции вставки нового узла, я думаю, в комментариях не нуждаются, так как практически ничем не отличаются от реализации в переводе:

class BinaryNode
{
	public $value;
	public $left  = NULL;
	public $right = NULL;

	public function __construct ($value)
	{
		$this->value = $value;
	}
}

class BinaryTree
{
	protected $root = NULL;

	public function isEmpty ()
	{
		return is_null($this->root);
	}

	public function insert ($value)
	{
		$node = new BinaryNode($value);
		$this->insertNode($node, $this->root);
	}

	protected function insertNode (BinaryNode $node, &$subtree)
	{
		if (is_null($subtree)) 
		{ 
			$subtree = $node; 
		}
		else
		{
			if ($node->value < $subtree->value)
			{
				$this->insertNode($node, $subtree->left);
			}
			elseif ($node->value > $subtree->value)
			{
				$this->insertNode($node, $subtree->right);
			}
		}
		return $this;
	}
}

Что бы удалить узел дерева, нам сначала понадобится его найти. Для этого напишем рекурсивную функцию поиска узла в нашем дереве:

protected function &findNode ($value, &$subtree)
{
	// Если элемент не найден, возвращаем FALSE
	if (is_null($subtree)) 
	{ 
		return FALSE; 
	}

	// Для искомого значения меньшего, чем значение узла, продолжаем искать в левом поддереве
	if ($subtree->value > $value)
	{
		return $this->findNode($value, $subtree->left);
	}
	// Для искомого значения большего, чем значение узла, продолжаем искать в правом поддереве
	elseif ($subtree->value < $value)
	{
		return $this->findNode($value, $subtree->right);
	}
	// Если искомое значение равно значению узла, то возвращаем этот узел
	else 
	{ 
		return $subtree; 
	}
}

Приступим к реализации алгоритма удаления узла из дерева. Суть алгоритма такова:

• если у узла нет потомков (поддеревьев), то смело его удаляем;
• если есть один потомок (только правое или левое поддерево), то заменяем удаляемый узел потомком;
• если есть оба потомка, то:
  
  • если у правого поддерева нет левого потомка, то заменяем удаляемый узел правым потомком, сохраняя левую ветвь удаляемого узла;
  • если у правого поддерева есть левый потомок, то копируем его значение в удаляемый узел и рекурсивно удаляем.

Непосредственно метод удаления узла:

public function delete ($value)
{
	// Выьрасываем исключение при попытке удаления элемента из пустого дерева
	if ($this->isEmpty())
	{
		throw new UnderflowException('Tree is empty!');
	}

	// Ищем нод в дереве
	$node = &$this->findNode($value, $this->root);
	// Если нод найден в дереве, то рекурсивно удаляем его
	if ($node)
	{
		$this->deleteNode($node);
	}
	return $this;
}

// Метод рекурсивного удаления, найденого нода из дерева
protected function deleteNode (BinaryNode &$node)
{
	// Если у узла нет потомков, удаляем его
	if (is_null($node->left) && is_null($node->right)) 
	{ 
		$node = NULL; 
	}
	// Если у узла нет левого поддерева, заменяем его правым поддеревом
	elseif (is_null($node->left)) 
	{
		$node = $node->right;
	}
	// Если у узла нет правого поддерева, заменяем его левым поддеревом
	elseif (is_null($node->right))
	{
		$node = $node->left;

	}
	// Если у узла есть оба потомка
	else
	{
		// Если у правого поддерева нет левого потомка, то заменяем удаляемый узел правым потомком, сохраняя левую ветвь удаляемого узла
		if (is_null($node->right->left))
		{
			$node->right->left = $node->left;
			$node = $node->right;
		}
		// если у правого поддерева есть левый потомок, то копируем его значение в удаляемый узел и рекурсивно удаляем
		else
		{
			$node->value = $node->right->left->value;
			$this->deleteNode($node->right->left);
		}
	}
}

Бинарное дерево поиска готово.

P.S.: В листингах кода, я намеренно вырезал phpdoc-комментарии и не использовал пространства имен, чтобы их не загромождать.
Полные версии исходных кодов бинарного дерева поиска (а так же реализации еще нескольких структур данных, — одно/двухсвязные списков и стека/очереди, реализованных с помощью этих списков) можно посмотреть на githubе.