DataStructures\Trees\BinarySearchTree

Complexity

Total Complexity

28

Size/Duplication

Total Lines	203
Duplicated Lines	15.27 %

Coupling/Cohesion

Components	1
Dependencies	2

Importance

Changes	1
Bugs	0	Features	0

11 Methods

Rating	Name	Duplication	Size	Complexity
A	__construct()	0	4	1
C	put()	0	34	7
A	putOrUpdate()	0	3	1
A	delete()	0	9	2
B	_delete()	0	27	5
A	preorder()	0	3	1
A	_preorder()	10	10	3
A	inorder()	0	3	1
A	_inorder()	11	11	3
A	postorder()	0	3	1
A	_postorder()	10	10	3

<?php
/**
 * DataStructures for PHP
 *
 * @link      https://github.com/SiroDiaz/DataStructures
 * @copyright Copyright (c) 2017 Siro Díaz Palazón
 * @license   https://github.com/SiroDiaz/DataStructures/blob/master/README.md (MIT License)
 */
namespace DataStructures\Trees;

use DataStructures\Trees\Nodes\BSTNode;
use DataStructures\Trees\Interfaces\BinaryNodeInterface;
use DataStructures\Trees\BinaryTreeAbstract;

/**
 * BinarySearchTree
 * 
 * Represents a BST actions that can be realized.
 * At the beginning root is null and it can grow up to a O(n) in search,
 * delete and insert (in worst case). In best cases it will be O(log n).
 *
 * @author Siro Diaz Palazon <siro_diaz@yahoo.com>
 */
class BinarySearchTree extends BinaryTreeAbstract {

    public function __construct() {
        $this->root = null;
        $this->size = 0;
    }

    /**
     * Inserts data in the correct position.
     *
     * @param integer|string $key the key used to store.
     * @param mixed $data the data to store.
     * @param bool $update if false the node isn't updated
     *  else if the key matches is updated.
     */
    public function put($key, $data, $update = false) {
        $newNode = new BSTNode($key, $data);
        
        if($this->root === null) {
            $this->root = &$newNode;
            $this->size++;
            return;
        }

        $parentNode = null;
        $current = &$this->root;
        while($current !== null) {
            $parentNode = &$current;
            if($key < $current->key) {
                $current = &$current->left;
            } else if($key > $current->key) {
                $current = &$current->right;
            } else {
                if($update) {
                    $current->data = $data;
                }
                return;
            }
        }

        $newNode->parent = &$parentNode;
        if($key < $parentNode->key) {
            $parentNode->left = &$newNode;
        } else {
            $parentNode->right = &$newNode;
        }

        $this->size++;
    }
    
    /**
     * Creates a new node or updates it if already exists.
     *
     * @param int|string $key the key.
     * @param mixed $data the data to be stored. 
     */
    public function putOrUpdate($key, $data) {
        $this->put($key, $data, true);
    }

    /**
     * Deletes the node with the maximum key and returns it. The most right and more bottom.
     * 
     * @param DataStructures\Trees\Nodes\BSTNode|null if null takes the root.
     * @return DataStructures\Trees\Nodes\BSTNode|null the maximum node or
     *  null if the tree is empty.
     */
    public function delete($key) {
        $deleteNode = $this->search($key);
        if($deleteNode !== null) {
            $this->_delete($deleteNode);
            return $deleteNode;
        }

        return null;
    }

    /**
     * Deletes the selected node if is not null and returns the node
     * that replaces the deleted node. Also decrease the size of tree.
     *
     * @param DataStructures\Trees\Nodes\BSTNode|null The node to be deleted.
     * @return the node that replaces the deleted.
     */
    protected function _delete(BinaryNodeInterface &$node) {
        if($node !== null) {
            $nodeToReturn = null;
            if($node->left === null) {

Accessing left on the interface DataStructures\Trees\Interfaces\BinaryNodeInterface suggest that you code against a concrete implementation. How about adding an instanceof check?

                $nodeToReturn = $this->replace($node, $node->right);

Accessing right on the interface DataStructures\Trees\Interfaces\BinaryNodeInterface suggest that you code against a concrete implementation. How about adding an instanceof check?

$node is of type object<DataStructures\Trees\Interfaces\BinaryNodeInterface>, but the function expects a object<DataStructures\Trees\DataStructures\Trees\Nodes\BSTNode>.

The expression $this->replace($node, $node->right); of type DataStructures\Trees\DataStructures\Trees\Nodes\BSTNode|null adds the type DataStructures\Trees\DataStructures\Trees\Nodes\BSTNode to the return on line 130 which is incompatible with the return type declared by the abstract method DataStructures\Trees\BinaryTreeAbstract::_delete of type DataStructures\Trees\the.

            } else if($node->right === null) {

Accessing right on the interface DataStructures\Trees\Interfaces\BinaryNodeInterface suggest that you code against a concrete implementation. How about adding an instanceof check?

                $nodeToReturn = $this->replace($node, $node->left);

Accessing left on the interface DataStructures\Trees\Interfaces\BinaryNodeInterface suggest that you code against a concrete implementation. How about adding an instanceof check?

$node is of type object<DataStructures\Trees\Interfaces\BinaryNodeInterface>, but the function expects a object<DataStructures\Trees\DataStructures\Trees\Nodes\BSTNode>.

The expression $this->replace($node, $node->left); of type DataStructures\Trees\DataStructures\Trees\Nodes\BSTNode|null adds the type DataStructures\Trees\DataStructures\Trees\Nodes\BSTNode to the return on line 130 which is incompatible with the return type declared by the abstract method DataStructures\Trees\BinaryTreeAbstract::_delete of type DataStructures\Trees\the.

            } else {
                $successorNode = $this->getMinNode($node->right);

The method getMinNode() cannot be called from this context as it is declared private in class DataStructures\Trees\BinaryTreeAbstract.

Accessing right on the interface DataStructures\Trees\Interfaces\BinaryNodeInterface suggest that you code against a concrete implementation. How about adding an instanceof check?

The expression $this->getMinNode($node->right); of type DataStructures\Trees\DataStructures\Trees\Nodes\BSTNode|null adds the type DataStructures\Trees\DataStructures\Trees\Nodes\BSTNode to the return on line 130 which is incompatible with the return type declared by the abstract method DataStructures\Trees\BinaryTreeAbstract::_delete of type DataStructures\Trees\the.

                if($successorNode->parent !== $node) {
                    $this->replace($successorNode, $successorNode->right);
                    $successorNode->right = &$node->right;

Accessing right on the interface DataStructures\Trees\Interfaces\BinaryNodeInterface suggest that you code against a concrete implementation. How about adding an instanceof check?

                    $successorNode->right->parent = &$successorNode;
                }

                $this->replace($node, $successorNode);
                $successorNode->left = &$node->left;
                $successorNode->left->parent = &$successorNode;
                $nodeToReturn = &$successorNode;
            }

            $this->size--;
            return $nodeToReturn;
        }

        return null;
    }

    /**
     * Traverse in preorder. This is: first visit the root, then
     * the left subtree and finally the right subtree.
     *
     * @param Callable|null $callback the callback function to apply to each
     *  node.
     */
    public function preorder(Callable $callback = null) {
        $this->_preorder($this->root, $callback);
    }

    /**
     * Private preorder traverse method that is recursive and is called by
     * the public preorder method.
     *
     * @param DataStructures\Trees\Nodes\BSTNode|null $node.

There is no parameter named $node.. Was it maybe removed?

     * @param Callable|null $callback the callback function to apply to each
     *  node.
     */
    private function _preorder($node, Callable $callback = null) {

This method seems to be duplicated in your project.

        if($node === null) {
            return;
        }
        if($callback !== null) {
            call_user_func($callback, $node);
        }
        $this->_preorder($node->left, $callback);
        $this->_preorder($node->right, $callback);
    }

    /**
     * Traverse in inorder. This is: first visit the left subtree,
     * then the root and finally the right subtree.
     *
     * @param Callable|null $callback the callback function to apply to each
     *  node.
     */
    public function inorder(Callable $callback = null) {

The parameter $callback is not used and could be removed.

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

    /**
     * Private inorder traverse method that is recursive and is called by
     * the public inorder method.
     *
     * @param DataStructures\Trees\Nodes\BSTNode|null $node.

There is no parameter named $node.. Was it maybe removed?

     * @param Callable|null $callback the callback function to apply to each
     *  node.
     */
    private function _inorder($node, Callable $callback = null) {

This method seems to be duplicated in your project.

        if($node === null) {
            return;
        }

        $this->_inorder($node->left, $callback);
        if($callback !== null) {
            call_user_func($callback, $node);
        }
        $this->_inorder($node->right, $callback);
    }

    /**
     * Traverse in postorder. This is: first visit the left subtree,
     * then the right subtree and finally the root.
     *
     * @param Callable|null $callback the callback function to apply to each
     *  node.
     */
    public function postorder(Callable $callback = null) {
        $this->_postorder($this->root, $callback);
    }

    /**
     * Private postorder traverse method that is recursive and is called by
     * the public postorder method.
     *
     * @param DataStructures\Trees\Nodes\BSTNode|null $node.

There is no parameter named $node.. Was it maybe removed?

     * @param Callable|null $callback the callback function to apply to each
     *  node.
     */
    private function _postorder($node, Callable $callback = null) {

This method seems to be duplicated in your project.

        if($node === null) {
            return;
        }
        $this->_postorder($node->left, $callback);
        $this->_postorder($node->right, $callback);
        if($callback !== null) {
            call_user_func($callback, $node);
        }
    }
}