2分探索木 Binary Search Tree : PHPで実装

Tweet

Pocket

2分探索木を使うと値の探索がO(lonN)で行えます。PHPで2分探索木を実装するサンプルです。

下記書籍を参考にPHPで実装しています。
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造　

/**
 * Class Node
 */
class Node
{
    public $id;
    public $parent;
    public $left;
    public $right;
    public $key;
    function __construct($id)
    {
        $this->id = $id;
    }
}

/**
 * Class BinarySearchTree
 *
 * 2分探索木
 */
class BinarySearchTree
{
    /** @var Node[] $node */
    private $nodes = [];
    /** @var Node $root */
    private $root = null;

    /**
     * 先行順巡回
     *
     * ルートから先行順巡回でキーを取得します。
     *
     * @param Node      $node
     * @param integer[] $keys
     * @return integer[]
     */
    private function preOrder($node, $keys)
    {
        if (is_null($node)) {
            return $keys;
        }
        array_push($keys, $node->key);
        if (!is_null($node->left)) {
            $keys = $this->preOrder($node->left, $keys);
        }
        if (!is_null($node->right)) {
            $keys = $this->preOrder($node->right, $keys);
        }

        return $keys;
    }

    /**
     * 先行順巡回ですべてのノードのキー(重み)取得
     *
     * @return integer[]
     */
    public function getKeysPreOrder()
    {
        $keys = [];

        return $this->preOrder($this->root, $keys);
    }

    /**
     * 中間順巡回
     *
     * ルートから中間順巡回でキーを取得します。
     *
     * @param Node      $node
     * @param integer[] $keys
     * @return integer[]
     */
    private function inOrder($node, $keys)
    {
        if (is_null($node)) {
            return $keys;
        }
        if (!is_null($node->left)) {
            $keys = $this->inOrder($node->left, $keys);
        }
        array_push($keys, $node->key);
        if (!is_null($node->right)) {
            $keys = $this->inOrder($node->right, $keys);
        }

        return $keys;
    }

    /**
     * 中間順巡回ですべてのノードのキー(重み)取得
     *
     * @return integer[]
     */
    public function getKeysInOrder()
    {
        $keys = [];

        return $this->inOrder($this->root, $keys);
    }

    /**
     * ノード追加
     *
     * @param integer $key
     */
    public function insert($key)
    {
        $id      = count($this->nodes);
        $current = new Node($id);
        array_push($this->nodes, $current);
        $current->parent = null;
        $current->left   = null;
        $current->right  = null;
        $current->key    = $key;

        $comparision = $this->root;
        $parentNode  = null;
        while (!is_null($comparision)) {
            $parentNode = $comparision;
            if ($current->key < $comparision->key) {
                $comparision = $comparision->left;
            } else {
                $comparision = $comparision->right;
            }
        }
        $current->parent = $parentNode;
        if (is_null($parentNode)) {
            $this->root = $current;
        } else {
            if ($current->key < $current->parent->key) {
                $parentNode->left = $current;
            } else {
                $parentNode->right = $current;
            }
        }
    }

    /**
     * 探索
     *
     * キーでノードを探索します。
     *
     * @param integer $key
     * @return Node
     */
    private function findNodeByKey($key)
    {
        $node = $this->root;
        while (!is_null($node) && $key !== $node->key) {
            if ($key < $node->key) {
                $node = $node->left;
            } else {
                $node = $node->right;
            }
        }

        return $node;
    }

    /**
     * キーを持つノードの存在判定
     *
     * @param integer $key
     * @return boolean
     */
    public function hasKey($key)
    {
        $node = $this->findNodeByKey($key);
        if (is_null($node)) {
            return false;
        }

        return true;
    }

    /**
     * 次節取得
     *
     * @param Node $node
     * @return Node
     */
    private function getSuccessor($node)
    {
        if (!is_null($node->right)) {
            return $this->getMinimum($node->right);
        }
        $target = $node->parent;
        while (!is_null($target) && $node == $target->right) {
            $node   = $target;
            $target = $target->parent;
        }

        return $node;
    }

    /**
     * 左部分木から最小ノード取得
     *
     * @param Node $node
     * @return Node
     */
    private function getMinimum($node)
    {
        while (!is_null($node->left)) {
            $node = $node->left;
        }

        return $node;
    }

    /**
     * ノードをnodes配列から削除
     *
     * @param Node $node
     */
    private function remove($node)
    {
        unset($this->nodes[$node->id]);
        array_values($this->nodes);
    }

    /**
     * ノード削除
     *
     * キーを持つノードを削除します。
     *
     * @param integer $key
     */
    public function delete($key)
    {
        // target 削除対象
        $current = $this->findNodeByKey($key);
        if (is_null($current)) {
            return false;
        }
        if (is_null($current->left) || is_null($current->right)) {
            $target = $current;
        } else {
            $target = $this->getSuccessor($current);
        }
        if (!is_null($target->left)) {
            $tmp = $target->left;
        } else {
            $tmp = $target->right;
        }
        if (!is_null($tmp)) {
            $tmp->parent = $target->parent;
        }
        if (is_null($target->parent)) {
            $this->root = $tmp;
        } elseif ($target == $target->parent->left) {
            $target->parent->left = $tmp;
        } else {
            $target->parent->right = $tmp;
        }
        if ($target !== $current) {
            $current->key = $target->key;
        }
        $this->remove($target);

        return true;
    }
}