PHP::Binary Search Tree

A simple implementation of binary search tree in PHP.

<?php
/**
 * Binary Search Tree
 * A simple bst implementation in PHP
 * @author J Wolfe <odwolfe@yahoo.com>
 */

/**
 * Class Node
 */
class Node {
    public $left  = null;
    public $right = null;
    public $data  = null;

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

    // Actually this method isn't working in this context.
    // If anyone knows how to get this work, please email me.
    public function __toString() {
        return $this->data;
    }
}

/**
 * Class BST
 * Basic binary search tree functionality
 */
class BST {
    /**
     * Root of the tree
     * @var null
     */
    public $root = null;

    /**
     * Insert a node order based
     * @param $data
     */
    public function insertNode($data) {
        $node = new Node($data);
        if (is_null($this->root)) {
            $this->root = $node;
        }
        else {
            $c_node =& $this->root;
            while (!is_null($c_node)) {
                if ($c_node->data > $data) {
                    $c_node =& $c_node->left;
                }
                // NOTE:: the following condition creates empty nodes
                // if ($c_node->data < $data) {
                else {
                    $c_node =& $c_node->right;
                }
            }
            $c_node = $node;
        }
    }

    /**
     * Search a node by a data
     * @param $data
     * @return Node
     */
    public function searchNode($data) {
        $c_node = $this->root;
        while (!is_null($c_node)) {
            if ($c_node->data == $data) {
                break;
            }
            else {
                if ($c_node->data > $data) {
                    $c_node = $c_node->left;
                }
                else {
                    $c_node = $c_node->right;
                }
            }
        }
        return $c_node;
    }

    /**
     * Find a node that holds the minimum data 
     * @param $c_node Node 
     * @return Node
     */
    public function &findMinNode($c_node) {
        $p_node = $c_node;
        while (!is_null($c_node->left)) {
            $p_node = $c_node;
            $c_node = $c_node->left;
        }
        return $p_node;
    }

    /**
     * Delete a node
     * The best resource I've found for node deletion logic:
     * http://www.algolist.net/Data_structures/Binary_search_tree/Removal
     *
     * TODO:: Delete orphans after a deletion occurs
     * @param $data
     */
    public function deleteNode($data) {
        $c_node =& $this->root;
        while (!is_null($c_node)) {
            if ($c_node->data == $data) {
                // has both children
                if (!is_null($c_node->left) && !is_null($c_node->right) ) {
                    // check right->left node to see if it is searchable
                    if (!is_null($c_node->right->left)) {
                        // get a parent node of a min node 
                        // in order to remove a child node
                        $p_node =& $this->findMinNode($c_node->right);
                        $c_node->data = $p_node->left->data;
                        $p_node->left = null;
                    }
                    // if not, it just takes a right node
                    else {
                        $c_node->data = $c_node->right->data;
                        $c_node->right = null;
                    }
                }
                // has one left child
                elseif (!is_null($c_node->left)) {
                    $c_node = $c_node->left;
                }
                // has one right child
                elseif (!is_null($c_node->right)) {
                    $c_node = $c_node->right;
                }
                // no children
                else {
                    $c_node = null;
                }
                break;
            }
            else {
                // loop for searching
                if ($c_node->data > $data) {
                    $c_node =& $c_node->left;
                }
                else {
                    $c_node =& $c_node->right;
                }
            }
        }
    }

    /**
     * Pre Order traverse
     * @param null $c_node
     */
    public function dispPreOrder($c_node = null) {
        if (!is_null($c_node)) {
            echo $c_node->data . " ";
            $this->dispPreOrder($c_node->left);
            $this->dispPreOrder($c_node->right);
        }
    }

    /**
     * In Order traverse
     * @param null $c_node
     */
    public function dispInOrder($c_node = null) {
        if (!is_null($c_node)) {
            $this->dispInOrder($c_node->left);
            echo $c_node->data . " ";
            $this->dispInOrder($c_node->right);
        }
    }

    /**
     * Post Order traverse
     * @param null $c_node
     */
    public function dispPostOrder($c_node = null) {
        if (!is_null($c_node)) {
            $this->dispPostOrder($c_node->left);
            $this->dispPostOrder($c_node->right);
            echo $c_node->data . " ";
        }
    }
}


/*
 * Sample data and usage of the class
 */
// test elements
$arr_test = array(23, 45, 16, 37, 3, 1, 99, 22);

$bst = new BST();

// insert elements to a bst tree
foreach ($arr_test as $val) {
    $bst->insertNode($val);
}

echo $bst->dispPreOrder($bst->root) . "<br/>";
echo $bst->dispInOrder($bst->root) . "<br/>";
echo $bst->dispPostOrder($bst->root) . "<br/>";

// search testing
$t_node = $bst->searchNode(23);
echo ($t_node ? $t_node->data . "is found!" : "Not found!") . "<br/>";
$t_node = $bst->searchNode(100);
echo ($t_node ? $t_node->data . "is found!" : "Not found!") . "<br/>";

// check if deletion works
$bst->deleteNode(23);
echo $bst->dispInOrder($bst->root) . "<br/>";

PHP::Hash table

Sometimes I feel that I have to do something and this is, I guess, one of those “things.” It’s not that difficult and challenging, still I haven’t really tried to do in PHP; which I have used heavily.

<?php
/**
  * This is a simple PHP hash table class
  *
  * The hash functions (simple and better) and methods used here
  * are excerpted from the book called
  * "Data Structures and Algorithms with JavaScript" by Michael McMillan
  * You can find it here: http://shop.oreilly.com/product/0636920029557.do
  *
  * @author J Wolfe <odwolfe@yahoo.com>
  *
  */
class HashTable {
    /**
     * Constant for a prime number for better hashing
     * according to the book
     */
    const P_NUM = 37;

    /**
     * Hash table size
     * @access private
     * @var integer
     */
    private $tSize = 137;

    /**
     * Hash table space as array
     * @access private
     * @var mixed
     */
    private $hTable = array();

    /**
     * Get the simple hash position
     * @param data string
     * @return integer
     */
    private function simpleHash($data) {
        $total = 0;
        for ($i=0; $i<strlen($data); $i++) {
            $total += ord($data[$i]);
        }
        return $total % $this->tSize;
    }

    /**
     * Get the hash position better than simple hash method
     * but I found that results are not significantly different.
     * @param data string
     * @return integer
     */
    private function betterHash($data) {
        $total = 0;
        for ($i=0; $i<strlen($data); $i++) {
            $total += self::P_NUM * ord($data[$i]);
        }
        if ($total < 0) {
            $total += $tSize - 1;
        }
        return intval($total % $this->tSize);
    }

    /**
     * Put data into hash table after getting the hash position
     * If collision occurs, it does chaining.
     * This is really not a traditional chaining
     * since, in PHP, you can simply add an array.
     * @param key string
     * @param data string
     * @return none
     */
    public function putData($key, $data) {
        // using SimpleHash in order to create collisions
        $pos = $this->simpleHash($key);
        // alternatively you can use betterHash method instead
        // $pos = $this->betterHash($key);
        if (!isset($this->hTable[$pos])) {
            $this->hTable[$pos] = array($key => $data);
        }
        else {
            $this->hTable[$pos][$key] = $data;
        }
    }

    /**
     * Get data from hash table after getting the hash position
     * @param key string
     * @return string
     */
    public function getData($key) {
        $r_data = "Not found";
        $pos = $this->simpleHash($key);
        $h_data = array();
        if (isset($this->hTable[$pos])) {
            $h_data = $this->hTable[$pos];
            foreach ($h_data as $k => $v) {
                if ($key == $k) {
                    $r_data = $v;
                    break;
                }
            }
        }
        return $r_data;
    }

    /**
     * Display elements of the current hash table
     * @param none
     * @return none
     */
    public function showTable() {
        for ($i=0; $i<$this->tSize; $i++) {
            if ( isset($this->hTable[$i]) ) {
                foreach ($this->hTable[$i] as $v) {
                    echo $i . "::" . $v . "<br/>";
                }
            }
        }
    }
}


/*
 * Sample data and usage of the class
 */
$arr_phones = array(
    "Fore Lee"     => "(201) 614-3803",
    "Passaic"      => "(973) 458-6724",
    "East Orange"  => "(545) 680-3518",
    "Paterson"     => "(973) 977-4307",
    "Elizabeth"    => "(555) 820-3911",
    "Perth Amboy"  => "(732) 537-1125",
    "Hackensack"   => "(201) 996-8021",
    "Phillipsburg" => "(908) 859-5467",
    "Jersey City"  => "(201) 217-4602",
    "Plainfield"   => "(958) 412-7769",
    "Morris County"=> "(555) 328-6490",
    "Pleasantville"=> "(649) 441-7501",
    "Neptune"      => "(555) 715-5131",
    "Lakewood"     => "(555) 765-6532",
    "Galloway"     => "(456) 785-7133",
    "Jefferson"    => "(667) 788-8913",
    "Somerville"   => "(908) 704-3366",
    "New Brunswick"=> "(932) 937-4525",
    "Thorofare"    => "(856) 853-4177",
    "Newark"       => "(541) 648-7601",
    "Toms River"   => "(732) 286-6460",
    "Newton"       => "(571) 383-4432",
    "Trenton"      => "(419) 352-6850",
    "Vineland"     => "(555) 696-6591",
    "Princeton"    => "(555) 937-4525"
);

$ht = new HashTable();
foreach ($arr_phones as $k => $v) {
    $ht->putData($k, $v);
}
$ht->showTable();

// get the phone numbers via locations
echo $ht->getData("Newark") . "<br/>";
echo $ht->getData("Trenton") . "<br/>";
echo $ht->getData("Jefferson") . "<br/>"; // look through collision
echo $ht->getData("No Name") . "<br/>";