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!