PHPで2分木の追加、検索、削除

#PHPで2分木の追加、検索、削除

##テストに使用した木構造と削除ルール
![2分木.png](https://qiita-image-store.s3.amazonaws.com/0/25382/7303e0ae-00a6-aa7e-e398-192c64f8b4ef.png)

##コード
```php:TreeNode.php
/* 
木構造で使用するノード
 */

class TreeNode {
    public $value;
    public $leftNode;
    public $rightNode;
}
```

```php:BinaryTree.php
/*
バイナリーツリー
 */

require_once 'TreeNode.php';

class BinaryTree {
    public static function createNewNode($value) {
        $node            = new TreeNode();
        $node->value     = $value;
        $node->leftNode  = null;
        $node->rightNode = null;
        return $node;
    }

    public static function insertNode($value, $node) {
        if ($node->value == $value) {
            return false;
        }

        if ($node->value > $value) {
            //ノードの値より小さい時。左の子のノードに
            if ($node->leftNode != null) {
                //既に左のノードにデータがある時、次のノードに進む
                self::insertNode($value, $node->leftNode);
            } else {
                //左のノードにデータを挿入
                $node->leftNode = self::createNewNode($value);
                return true;
            }
        } else {
            //ノードの値より大きい時。右の子のノードに
            if ($node->rightNode != null) {
                //既に右のノードにデータがある時、次のノードに進む
                self::insertNode($value, $node->rightNode);
            } else {
                //右のノードにデータを挿入
                $node->rightNode = self::createNewNode($value);
                return true;
            }
        }
    }

    public static function find($value, $node) {
        if ($node->value == $value) {
            //値が見つかった時
            return true;
        }

        if ($node->value > $value) {
            if (empty($node->leftNode)) {
                return false;
            }
            //探している値が対象のノードより小さい時は左のノードへ
            return self::find($value, $node->leftNode);
        } else {
            if (empty($node->rightNode)) {
                return false;
            }
            //右のノードへ
            return self::find($value, $node->rightNode);
        }
    }

    public static function delete($value, &$tree) {
        $rootNode  = &$tree; //ルートノードのアドレス
        $node      = &$tree; //1個ずつ調べ、最後は削除対象のノード
        $parent    = null;   //$nodeの親のノードのアドレス
        $direction = 0; //根の場合は0。左の子に進む時は-1を右の時は1

        //削除対象のノードを探索
        while ($node !== null && $node->value != $value) {
            if ($node->value > $value) {
                $parent    = &$node;
                $node      = &$node->leftNode;
                $direction = -1;
            } else {
                $parent    = &$node;
                $node      = &$node->rightNode;
                $direction = 1;
            }
        }
        //削除対象が木に無かった時
        if ($node == null) {
            return false;
        }

        //削除対象のノードがある時
        if ($node->leftNode == null && $node->rightNode == null) {
            //右と左のノードが無い時。つまり、リーフを削除
            if ($direction == -1) {
                $parent->leftNode = null;
            } else {
                $parent->rightNode = null;
            }
        } else if ($node->leftNode == null && $node->rightNode != null) {
            //左のノードが無くかつ右のノードがある時
            if ($direction == -1) {
                $parent->leftNode = $node->rightNode;
            } else if ($direction == 1) {
                $parent->rightNode = $node->rightNode;
            } else if ($direction == 0) {
                //木構造で右のノードしかなくルートを削除する時
                $rootNode = $node->rightNode;
            }
        } else if ($node->leftNode != null && $node->rightNode == null) {
            //左のノードがあってかつ右のノードが無い時
            if ($direction == -1) {
                $parent->leftNode = $node->leftNode;
            } else if ($direction == 1) {
                $parent->rightNode = $node->leftNode;
            } else if ($direction == 0) {
                //木構造で左のノードしかなくルートを削除する時
                $rootNode = $node->leftNode;
            }
        } else {
            //右と左の子がある場合。
            //左のノードの最大値と削除したいノードと交換する
            $leftBiggest = &$node->leftNode;
            $parent = &$node;
            $direction = -1;
            //右のノードがある限り上書きしていく。
            while ($leftBiggest->rightNode != null) {
                $parent = &$leftBiggest;
                $leftBiggest = &$leftBiggest->rightNode;
                $direction = 1;
            }

            $node->value = $leftBiggest->value;
            if ($direction == -1) {
                $parent->leftNode = &$leftBiggest->leftNode;
            } else {
                $parent->rightNode = &$leftBiggest->leftNode;
            }
        }
        return true;
    }
}
```

##テストコード
```php:binaryTreeTest.php
/*
2分木のテスト
 */

require_once './../part/TreeNode.php';
require_once './../part/BinaryTree.php';

$tree = new TreeNode();
$tree->value = 1000;
BinaryTree::insertNode(2000, $tree);
BinaryTree::insertNode(300, $tree);
BinaryTree::insertNode(4000, $tree);
BinaryTree::insertNode(5000, $tree);
BinaryTree::insertNode(100, $tree);
BinaryTree::insertNode(50, $tree);
BinaryTree::insertNode(10, $tree);
BinaryTree::insertNode(200, $tree);
BinaryTree::insertNode(400, $tree);
echo '<pre>';
var_dump($tree);
echo '</pre>';

echo '<br>';
echo 'ここから検索テスト';
var_dump(BinaryTree::find(1000, $tree));
var_dump(BinaryTree::find(2000, $tree));
var_dump(BinaryTree::find(300, $tree));
var_dump(BinaryTree::find(4000, $tree));
var_dump(BinaryTree::find(5000, $tree));
var_dump(BinaryTree::find(100, $tree));
var_dump(BinaryTree::find(50, $tree));
var_dump(BinaryTree::find(10, $tree));
var_dump(BinaryTree::find(200, $tree));
var_dump(BinaryTree::find(400, $tree));
var_dump(BinaryTree::find(1, $tree));
echo '<br>';
echo 'ここから消去テスト';
var_dump(BinaryTree::delete(1, $tree));
echo '<br>';
//リーフの削除テスト
//var_dump(BinaryTree::delete(400, $tree));
//右のノードしかない時の削除テスト
//var_dump(BinaryTree::delete(2000, $tree));
//左のノードしかない時の削除テスト
//var_dump(BinaryTree::delete(50, $tree));
//右と左のノードがある時のテスト
//var_dump(BinaryTree::delete(300, $tree));
//右と左のノードがある時のテスト
////var_dump(BinaryTree::delete(100, $tree));
//ルートの削除テスト
//var_dump(BinaryTree::delete(1000, $tree));
//木を左のノードしかないようにしてルートを削除
//木を右のノードにしてルートを削除
var_dump(BinaryTree::delete(1000, $tree));

echo '<pre>';
var_dump($tree);
echo '</pre>';
```
##ソース全部
https://github.com/Khanashima/algorithm