PHP Data Structure: Binary Search Tree (BST)

data-structure-binary-search-tree.php

<?php
class BST {
    protected $root;

    /**
     * Abstracts away root selection.
     * 
     * @param $data
     * @return BSTNode
     * @throws Exception
     */
    public function search( $data ) {
        return $this->binarySearch($data, $this->root);
    }

    /**
     * Perform Binary search.
     * 
     * @param $data
     * @param BSTNode $root
     * @return BSTNode
     * @throws Exception
     */
    protected function binarySearch($data, BSTNode $root = null ) {
        if ( is_null( $root ) )
            throw new Exception('No node with that value');

        if( $root->data == $data ) {
            return $root;
        } elseif ( $data > $root->data ) {
            return $this->binarySearch( $data, $root->right );
        } else {
            return $this->binarySearch( $data, $root->left );
        }
    }

    /**
     * Abstracts away root
     * 
     * @param $data
     */
    public function insert( $data )
    {
        $this->root = $this->add($data, $this->root);
    }

    /**
     * Inserts data and keeps tree balanced.
     * 
     * @param $data
     * @param BSTNode $root
     * @return BSTNode
     */
    protected function add( $data, BSTNode $root = null )
    {
        if (is_null($root)) {
            $root = new BSTNode($data);
        } else if ($data > $root->data) {
            $root->right = $this->add($data, $root->right);
        } else {
            $root->left = $this->add($data, $root->left);
        }

        return $root;
    }

    /**
     * Deletes data and keeps tree balanced.
     * 
     * @param $data
     * @param BSTNode $root
     * @return BSTNode|null
     */
    public function delete($data, BSTNode $root = null) {
        if ( is_null( $root ) )
            $root = $this->search($data);

        if ( is_null( $root->left ) && is_null( $root->right ) ) {
            // Leaf node -- just delete
            $root = ( $this->replaceNode( $root, null ) );
        } elseif( is_null( $root->left ) ) {
            // Has one branch, replace self with it
            $root = $this->replaceNode( $root, $root->right );
        } elseif( is_null( $root->right ) ) {
            // Has one branch, replace self with it
            $root = $this->replaceNode( $root, $root->left );
        } else {
            // Has two nodes, need to find the replacement
            $min_node = $this->findMin($root->right);
            $temp = $min_node->data;
            
            // Recursively go through the tree to keep balanced
            $this->delete( $min_node->data, $min_node );
            $root->data = $temp;
        }

        return $root;
    }

    /**
     * Finds the minimum value in a tree and returns node.
     * 
     * @param BSTNode $root
     * @return BSTNode
     */
    protected function findMin( BSTNode $root ) {
        if ( is_null( $root ) )
            return $root;

        if ( is_null( $root->left ) )
            return $root;

        return $this->findMin( $root->left );
    }

    /**
     * In PHP we can't have references to objects, so deleting or
     * nullifying a node won't remove that link from the parent. 
     * Instead find the parent node and remove its child node.
     * 
     * @param $data
     * @param BSTNode $root
     * @return BSTNode|null
     */
    protected function findParent( $data, BSTNode $root = null ) {
        if ( is_null( $root ) )
            $root = $this->root;

        if ( $data == $root->data ) {
            $root = null;
        } elseif ( $data <= $root->data ) {
            if ( $data != $root->left->data )
                $root = $this->findParent( $data, $root->left );
        } else {
            if ( $data != $root->right->data )
                $root = $this->findParent( $data, $root->right );
        }

        return $root;
    }

    /**
     * Replaces a given node with another node or null.
     * 
     * @param BSTNode $replace
     * @param BSTNode $with
     * @return BSTNode|null
     */
    protected function replaceNode( BSTNode $replace, BSTNode $with = null ) {
        $parent = $this->findParent($replace->data);

        if ( is_null( $parent ) )
            return null;

        if ( $parent->data <= $replace->data ) {
            $parent->right = $with;
        } else {
            $parent->left = $with;
        }

        return $with;
    }
}

class BSTNode {
    public $data;
    public $left = null;
    public $right = null;

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