How to create a Binary Search Tree in PHP

.NET PHP Sorting
Storing a set of objects in sorted order is a crucial tool for programmers. PHP provides array manipulation functoins such as ksort() and asort(), which work well with numbers and strings, but lack the ability to sort more complex objects. The usort() function also provides a parameter to specify a callback function to compare two objects, but it is tricky to use and needs to be called every time you want to sort the set.

In .NET, the SortedSet class is an implementation of ISet which automatically maintains objects in sorted order and allows for additions and removals through simple methods like .Add() and .Remove()

Such a class requires an underlying sorting algorithm, of which different ones exist. One of the most interesting sorting algorithms is the Red-Black Binary Tree, which has a worst-case time complexity of O(log n), meaning that the time to sort (or rather, maintain sorted order) progresses non-linearly in regards to the size of the set. That is a huge advantage when sorting a vast amount of objects.

Another type of sorting tree is the Binary Search Tree (BST). This has an average time complexity of O(log n), but at the worst case, the time complexity becomes O(n). This means, that for some binary search trees, for example, those in purely ascending or descending order become as slow as shuffling elements in a Linked List.

The main feature of a BST is that each node has a left and right child. All nodes on the left of a node, and all subnodes of that left node, should have a value smaller than the node itself. Likewise, all nodes and subnodes on the right should have a value greater than the node itself.

As part of a project to create a SortedSet in PHP, I have created my own implementation of a Binary Search Tree.


<?php

namespace ACA\Collections
{
use System\Collections\ISet;
use System\Collections\IComparer;
use ACA\Collections\Types\Node;

/**
* A binary search tree for keeping objects in sorted ascending order
* @author Antony Charles Allen
* @since 24th October 2020
*/
class BinarySearchTree extends GenericBase implements ISet, \Countable
{
private IComparer $comparer;
private ?Node $root = null;

private int $count = 0;

public function __construct(string $T, IComparer $comparer)
{
parent::__construct($T);

$this->comparer = $comparer;
}

function Add(object $item) : bool
{
if (!$this->IsValid($item)) throw new \InvalidArgumentException("Invalid object, type: ".get_class($item));

if (is_null($this->root))
{
$this->root = new Node($item);
$this->count = 1;
return true;
}

$node = $this->root;

while (true)
{
$compare = $this->comparer->Compare($item, $node->Data());

if ($compare === 0) return false;

if ($compare < 0)
{
if ($node->HasLeftNode())
{
$node = $node->GetLeft();
}
else
{
$node->AddLeftData($item);
$this->count++;
return true;
}
}
else
{
if ($node->HasRightNode())
{
$node = $node->GetRight();
}
else
{
$node->AddRightData($item);
$this->count++;
return true;
}
}
}
}

function Clear() : void
{
$this->count = 0;
$this->root = null;
}

function count() : int
{
return $this->count;
}

function Contains(object $item) : bool
{
$node = $this->FindNode($item);

return !is_null($node);
}

private function FindNode(object $item) : ?Node
{
if (!$this->IsValid($item)) throw new \InvalidArgumentException("Cannot search for type: ".get_class($item));

if (is_null($this->root)) return null;

$node = $this->root;

while (true)
{
$compare = $this->comparer->Compare($item, $node->Data());

if ($compare === 0) return $node;

if ($compare < 0)
{
if ($node->HasLeftNode())
{
$node = $node->GetLeft();
}
else return null;
}
else
{
if ($node->HasRightNode())
{
$node = $node->GetRight();
}
else return null;
}
}
}

function CopyTo(array & $array, int $arrayIndex = 0) : void
{
if ($arrayIndex === 0) $array = $this->ToArray();

else throw new \Exception("To do - implement array indexing in ".__METHOD__);
}

private function Validate() : void
{
if (is_null($this->root)) return;

else
{
if (!$this->root->IsRoot()) throw new \Exception("Root node ".$this->root." is actually a parent [".$this->root->Parent()."]!");

$this->root->Validate();
}
}

function Remove(object $item) : bool
{
$this->Validate();

$node = $this->FindNode($item);

if (is_null($node)) return false;

#region Case 1 - Leaves
if ($node->IsLeaf())
{
if ($node->IsRoot())
{
$this->root = null;
}
else
{
// We should remove the node from its parent

$node->Remove();
}

$this->count--;
return true;
}
#endregion

#region Case 2 - Single child on left side
if ($node->HasOneChild() && $node->HasLeftNode())
{
$child = $node->GetLeft();

if ($node->IsRoot())
{
$child->DisconnectFromParent();
$this->root = $child;
}
else
{
// Non-root node with a single left child
// Move the child and attach the parent of the node

$parent = $node->Parent();
$parent->ReplaceChild($node, $child);
}

$node->Disconnect();
$this->count--;
return true;
}
#endregion

#region Case 3 - Single child on the right side
if ($node->HasOneChild() && $node->HasRightNode())
{
$child = $node->GetRight();

if ($node->IsRoot())
{
$child->DisconnectFromParent();
$this->root = $child;
}
else
{
$parent = $node->Parent();
$parent->ReplaceChild($node, $child);
}

$node->Disconnect();
$this->count--;
return true;
}
#endregion

#region Case 4 - Two children
if ($node->HasTwoChildren())
{
// Locate the leftmost child in the right subtree

$leftmost = Node::GetLeftMostChild($node->GetRight());

if ($leftmost->IsLeaf())
{
// The leftmost child in the right subtree is a leaf

$leftmost_parent = $leftmost->Parent();

if ($leftmost === $node->GetRight())
{
// Leftmost child is actually the right child of the node to delete
// The node to delete also has a left child
// The leftmost child in the right subtree doesn't have children, because it is a leaf

$leftmost->SetLeft($node->GetLeft());

if ($node->IsRoot())
{
$this->root = $leftmost;
$leftmost->DisconnectFromParent();
}
else $node->Parent()->ReplaceChild($node, $leftmost);

$this->count--;
return true;
}
else
{
// Leftmost child is further down in the right subtree
// Remove the leftmost leaf child and set new children

$leftmost->Remove();
$leftmost->SetLeft($node->GetLeft());
$leftmost->SetRight($node->GetRight());
}

if ($node->IsRoot())
{
// The root node should become the leftmost

$this->root = $leftmost;
}
else
{
// Replace the node with the leftmost deep leaf

$node->Parent()->ReplaceChild($node, $leftmost);
}

$node->Disconnect();
$this->count--;
return true;
}
else
{
// Leftmost child is not a leaf
// There, it MUST have a right child

if ($leftmost->Parent() === $node)
{
// Leftmost non-leaf is the right child of the node

$leftmost->SetLeft($node->GetLeft());

if ($node->IsRoot())
{
$this->root = $leftmost;
$this->root->DisconnectFromParent();
}
else $node->Parent()->ReplaceChild($node, $leftmost);

$this->count--;
return true;
}
else
{
// Leftmost non-leaf child is further down in the right subtree
// Take the right child of the leftmost child and attach it to its parent

$leftmost_parent = $leftmost->Parent();
$leftmost_parent->SetLeft($leftmost->GetRight());

$leftmost->Disconnect();
$leftmost->SetLeft($node->GetLeft());
$leftmost->SetRight($node->GetRight());

if ($node->IsRoot())
{
$this->root = $leftmost;
}
else
{
$node->Parent()->ReplaceChild($node, $leftmost);
}

$node->Disconnect();
$this->count--;
return true;
}
}
}
#endregion

throw new \Exception("Unable to remove node $node");
}

public function ToArray() : array
{
if (is_null($this->root)) return array();

$this->Validate();

$array = static::GetValues($this->root);

return $array;
}

private static function GetValues(Node $node) : array
{
$array = array();

if ($node->HasLeftNode())
{
$array = array_merge($array, static::GetValues($node->GetLeft()));
}

$array[] = $node->Data();

if ($node->HasRightNode())
{
$array = array_merge($array, static::GetValues($node->GetRight()));
}

return $array;
}


public function TryGetValue(object $equalValue, object & $actualValue) : bool
{
$actualValue = null;

$node = $this->FindNode($equalValue);

if (!is_null($node))
{
$actualValue = $node;
return true;
}
else return false;
}
}
}


The node class is written as follows:


<?php

namespace ACA\Collections\Types
{
/**
* A node in a BST
* @author Antony Charles Allen
* @since 24th October 2020
*/
class Node
{
private object $data;

private ?self $parent = null;

private ?self $left = null;
private ?self $right = null;

public function Data() : object
{
return $this->data;
}

public function Parent() : ?self
{
return $this->parent;
}

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

public function HasLeftNode() : bool
{
return !is_null($this->left);
}

public function HasRightNode() : bool
{
return !is_null($this->right);
}

public function AddLeftData(object $data) : self
{
if (is_a($data, self::class)) throw new \InvalidArgumentException("Cannot assign Node as data!");

$node = new self($data);

$this->left = $node;
$node->SetParent($this);

return $node;
}

public function AddRightData(object $data) : self
{
if (is_a($data, self::class)) throw new \InvalidArgumentException("Cannot assign Node as data!");

$node = new self($data);

$this->right = $node;
$node->SetParent($this);

return $node;
}

public function GetLeft() : self
{
return $this->left;
}

public function GetRight() : self
{
return $this->right;
}

public function IsLeaf() : bool
{
return is_null($this->left) && is_null($this->right);
}

public function IsRoot() : bool
{
return is_null($this->parent);
}

/**
* Remove this node from its parent
*/
public function Remove() : void
{
$this->parent->RemoveChild($this);
}

private function SetParent(self $node) : void
{
$this->parent = $node;
}

public function SetLeft(self $node) : void
{
$this->left = $node;
$node->SetParent($this);
}

public function SetRight(self $node) : void
{
$this->right = $node;
$node->SetParent($this);
}

public function RemoveChild(self $node) : void
{
if (!$node->IsLeaf()) throw new \InvalidArgumentException("Cannot remove child [$node] because it is not a leaf!");

if ($this->left === $node)
{
$node->DisconnectFromParent();
$this->left = null;
return;
}
else if ($this->right === $node)
{
$node->DisconnectFromParent();
$this->right = null;
return;
}
else throw new \InvalidArgumentException("Node $node is not a child of this [$this]!");
}

public function HasOneChild() : bool
{
$i = 0;

if (!is_null($this->left)) $i++;

if (!is_null($this->right)) $i++;

return $i === 1;
}

public function HasTwoChildren() : bool
{
return !is_null($this->left) && !is_null($this->right);
}

/**
* Remove the link to the parent from this node.
* This function effectively turns the node temporarily into a root node.
* @throws \Exception
*/
public function DisconnectFromParent() : void
{
if (!is_null($this->parent))
{
$this->parent = null;
}
else throw new \Exception("Node $this is already disconnected from parent!");
}

/**
* Disconnect from parent and both children.
* This turns the node into a root node with no children.
*/
public function Disconnect() : void
{
$this->parent = null;
$this->left = null;
$this->right = null;
}

function __toString() : string
{
return 'Node '.(string)$this->data;
}

public function ReplaceChild(self $oldChild, self $newChild) : void
{
if ($this->left === $oldChild)
{
$this->left = $newChild;
$newChild->SetParent($this);
$oldChild->DisconnectFromParent();
return;
}

if ($this->right === $oldChild)
{
$this->right = $newChild;
$newChild->SetParent($this);
$oldChild->DisconnectFromParent();
return;
}

throw new \Exception("Old child $oldChild is not a child of $this");
}

public static function GetLeftMostChild(self $node) : self
{
while ($node->HasLeftNode())
{
$node = $node->GetLeft();
}

return $node;
}

public function Validate() : void
{
if ($this->HasLeftNode())
{
if ($this->left->Parent() !== $this) throw new \Exception("Left child ".$this->left." does not have correct parent [$this], but instead has [".$this->left->Parent()."]!");

$this->left->Validate();
}

if ($this->HasRightNode())
{
if ($this->right->Parent() !== $this) throw new \Exception("Right child ".$this->right." does not have correct parent [$this], but instead has [".$this->right->Parent()."]!");

$this->right->Validate();
}
}
}
}


I will describe the base class of the BST in another blog post about generic type collections, but this will have to do for now.

Happy Coding!
Hey you! I need your help!

Thanks for reading! All the content on this site is free, but I need your help to spread the word. Please support me by:

  1. Sharing my page on Facebook
  2. Tweeting my page on Twitter
  3. Posting my page on LinkedIn
  4. Bookmarking this site and returning in the near future
Thank you!