PHP实现二分搜索树(BST)的原理与实现代码

PHP实现了一下二分搜索树(BST)，实现的代码还是很简单的，下面来总结一下。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

首先先来介绍一下二分搜索树。二分搜索树，本质上就是一棵二叉树，它并不一定是一棵满二树，也并不一定是一棵完全二叉树，但是二分搜索树中的每一个非叶子节点的值都要大于其左子节点的值，同时还要小于其右子节点的值。参考下面的图，可以更好的理解二分搜索树。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

二分搜索树的基本概念非常的简单，很好理解。根据上面的概念，我们可以很轻松的得到下面的结论:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

(1):任意一个非叶子节点的左子树中的所有的节点的值都要小于该非叶子节点，并且都要小于该非叶子节点的右子树中的所有节点，这一点对于后面实现节点的删除来说至关重要。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

(2):整棵二分搜索树中的最大值节点一定是处于该二分搜索树中最左边的叶子节点，最小值节点一定是处于该二分搜索树中最右边的叶子节点，根据这个规律我们后面可以很轻松的查找到整棵树中的最大值以及最小值。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

(3):由于上面的性质，二分搜索树被广泛用于"字典"这种数据类型的实现，比如说PHP中的array数据类型。参照上面的图片，假如我们每一个节点中的数值代表array中的key,那么如果我们再在每一个节点中设置一个value,那么我是不是就实现了key=>value这种键值对了那。说到这里，又得同学就会说了，为什么一定要使用树这种数据结构来实现key=>value这种键值对那，普通的数组也可以实现的啊。关于这一点，主要是因为通过数组来实现的话，查找，修改等操作的平均时间复杂度是O(N)，而采用二分搜索树来实现的话，平均时间复杂度只有O(logN)，下面我们有具体的代码来大家可以分析一下。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

上面说了一些二分搜索的基本概念，下面我们就用PHP来实现一个二分搜索树。这里需要先说一点，二分搜索树由于不具备堆的特殊性质，并且其还是链式结构，所以很难用数组进行实现。我最早学习算法与数据结构的时候，是通过C中的指针来实现这种典型的链式结构的，现在换成了PHP,没了指针，一开始真心不习惯，后来发现使用PHP中的对象完全可以模拟指针来实现二分搜索树。好了，废话不说了，下面直接用PHP来实现一个满足key=>value键值对的二分搜索树。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

(1):定义用来描述二分搜索树中节点的Node类文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

<?php
//Node类
class  Node{
    //当前节点的key
    public $key = null;
    //当前节点的value
    public $value = null;
    //当前节点的左子节点
     public $left = null;
    //当前节点的右子节点
     public $right = null;
}
//每一个实例化Node类的对象都用来描述二分搜索树中一个节点
//其中的属性key,value是来存放键值对信息
//属性right用来记录该节点的右子节点，属性left用来记录该节点的左子节点。
?>

(2):初始化构建一个二分搜索树文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

//使用数组构建二分搜索树
//将数组传递到函数中,遍历循环数组，将数组中的元素依次添加到二分搜索树中
function bulid_binary_search_tree($arr){
    if(empty($arr)){
        return null;
    }
    //初始情况下，创建一个根节点
    $root = new Node();
    $level = 1;
    foreach($arr as $key=>$value){
        //为根节点进行赋值操作
        if($level == 1){
            $root->key = $key;
            $root->value = $value;
        }else{
            //创建一个新节点
            $new_node = new Node();
            $new_node->key = $key;
            $new_node->value = $value;
            //将新创建的节点，添加到初始化好的二分搜索树中
            /*
            添加操作，是初始化二分搜索树的关键操作
            因为在处理添加节点的过程之中要根据传入的数据的大小，不断的分析新节点需要存放的位置
            */
            insert_binary_search_tree($root,$new_node);
        }
        $level++;
    }
    return $root;
}

//添加节点到二分搜索树中
//思路如下:如果待添加的节点的key大于(小于)根节点，就将该节点与根节点的右(左)子节点继续比较
          //如果根节点的右(左)节点为空，也就是说根节点并不存在右(左)子节点，就将该节点放置到
          //根节点的右(左)子节点的位置上。如果存在右(左)子节点，就将该新增的节点与右(左)子节
          点继续按照上面的方式比较，直到放置到合适的位置为止 
function insert_binary_search_tree($root,$new_node){
    //新添加的节点与根节点进行比较
    //如果新节点的key与根节点的key一致的话,就使用新的节点中的value替换root节点的value
    if($root->key == $new_node->key){
        //进行替换操作
        $root->value = $new_node->value;
        return true;
    }elseif($root->key > $new_node->key){ //如果新添加的节点的key小于root节点的key
        if($root->left == null){
            $root->left = $new_node;
            return true;
        }else{
            $root = $root->left;
            insert_binary_search_tree($root,$new_node);
        }
    }else{ //如果新添加的节点的key大于root节点的key
        if($root->right == null){
            $root->right = $new_node;
            return true;
        }else{
            $root = $root->right;
            insert_binary_search_tree($root,$new_node);
        }
    }
}
//已经准备好的初始化的数组
$node_arr = [2=>"222",1=>"111",0=>"000",4=>"444",3=>"333"];
//调用初始化函数，创建二分搜索树
$result = build_binary_search_tree($node_arr);
echo "<pre/>";
//打印生成的二分搜索树
var_dump($result);

OK,上面的代码就实现了二分搜索树，下面是打印的结果，怎么样是不是一目了然那？文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

这里需要说明的是，我们插入的数组node_arr中第一个新节点是key=2的节点，所以该节点就是我们整个二分搜索树中的根节点。上面我们已经初始化成功了一个二分搜索树，这只是一小步，我们还要实现二分搜索树中元素的查找，遍历以及节点删除等功能。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

(3):查找二分搜索树中是否存在某个key值文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

我们一开始就已经提到过了，采用二分搜索树这种数据结构进行数据的查找的平均时间复杂度是O(logN)，是要优与顺序数据的O(N)的。下面是两个实现查找key的函数，一个用来查找key是否存在，一个是返回key所对用的value,在功能上和PHP中的isset()函数以及数组名[key]非常的相像。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

<?php
//查找key是否存在
function contain_key($root,$key){
    //如果递归到null,直接进行返回
    if($root == null){
        return false;
    }
    //比较当前节点的key是否和需要查询的key相等
    if($root->key == $key){
        return true;
    }elseif($root->key > $key){ //如果当前节点的key大于需要查找的key
        return contain_key($root->left,$key);
    }elseif($root->key < $key){ //如果当前节点的key小于需要查找的key
        return contain_key($root->right,$key);
    }
}

//查找key所对应的value
function get_value($root,$key){
    //如果递归到null,直接进行返回
    if($root == null){
        return false;
    }
    //比较当前节点的key是否和需要查询的key相等
    if($root->key == $key){
        return $root->value;
    }elseif($root->key > $key){ //如果当前节点的key大于需要查找的key
        return get_value($root->left,$key);
    }elseif($root->key < $key){ //如果当前节点的key小于需要查找的key
        return get_value($root->right,$key);
    }
}
?>

我们之前还提到过，二分搜索树中最大值以及最小值的所处位置的特性，下面我们就利用上面提到的特性来查找的二分搜素中的最大值以及最小值,在功能上非常类似PHP中的max()函数以及min()函数。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

<?php
//获取最大值
function find_max($root){
    if($root->right !=null ){
        return find_max($root->right);
    }else{
        return $root->key;
    }
}

//获取最小值
function find_min($root){
    if($root->left !=null ){
        return find_min($root->left);
    }else{
        return $root->key;
    }
}
?>

上面的代码逻辑很简单，相信大家都能看的明白，这里就不赘述了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

(4):上面我们已经完成了数据的查找，下面我们实现一下二分搜索树的遍历操作文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

二分搜索树的遍历操作分为两大类，一种是深度优先遍历，一种是广度优先遍历。深度优先遍历就是不断的递归向下遍历，广度优先遍历就是按照二分搜索树的层级，从上到下，每次遍历出一层所有的节点，然后再向下查找。平常人家经常谈论的前序遍历，中序遍历以及后序遍历都属于深度优先遍历，三者之间的差别在于获取当前节点的先后顺序不一样而已，下面我们就用代码实现一下上面提到的各种遍历方式。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

1):前序遍历文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

<?php
function tree_before($root){
    if($root != null){
        echo $root->value."<br/>";
        tree_before($root->left);
        tree_before($root->right);
    }
}
?>

打印结果如下: 222,111,000,444,333文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

2):中序遍历文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

<?php
function tree_mid($root){
    if($root != null){
        tree_mid($root->left);
        echo $root->value."<br/>";
        tree_mid($root->right);
    }
}
?>

打印结果如下: 000,111,222,333,444文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

3):后续遍历文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

<?php
function tree_next($root){
    if($root != null){
        tree_next($root->left);
        tree_next($root->right);
        echo $root->value."<br/>";
    }
}
?>

打印结果如下: 000,111,333,444,222文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

大家可以看到，上面的遍历代码非常的简单，三则之间不同在于访问当前节点的顺序不一样，其他完全一致，都是采用递归的方式进行调用的。这里需要说的是，二分搜索树这种数据结构非常适合使用递归的方式来进行处理，这也算是其特性之一了。还有一点非常的重要，就是中序遍历的结果是有序的，这一点大家可以简单分析一下节点的访问路径就明白了，所以，如果想要对二分搜索树中的元素进行排序的话，使用二分搜索树再合适不过了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

接下来咱们再说说广度优先遍历的实现。广度优先遍历的实现，需要借助队列来实现，下面看代码。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

<?php
function tree_level($root,&$queue){
    if($root == null){
        return;
    }else{
        echo $root->key."<br/>";
    }
    if($root->left != null){
        $queue[] = $root->left;
    }
    if($root->right != null){
        $queue[] = $root->right;
    }
    if(count($queue)>=1){
        $item = array_shift($queue);
        tree_level($item,$queue);
    }
}
$array = [];
tree_level($result,$array);
?>

基本的思路如下:我们首先访问根节点，然后将根节点的两个子节点存放到array()中，然后每次从array()中取出一个没有遍历的节点，输出该节点的值，并将该节点的左右两个节点存储到array()中，依次类推，直到取到到所有节点的都没有左右子节点为止。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

(5):最后看一下如何删除二分搜索中的一个节点文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

删除一个节点的方式，也非常的简单，通常情况下，我们都是采用Hubbard deletion思想来实现。基本的思路如下:如果要删除一个节点，如果其不含有子节点，可以直接进行删除。如果其含有子节点，就需要在其子节点中找到一个节点来替换掉这个需要被删除的节点。这里需要注意的是，继续替换操作的子节点，要能够继续维持二分搜索树的基本性质，那么哪个子节点才能做到那？答案就是需要删除的节点的左子树中最大值或者是右子树中的最小值。为什么那？因为根据二分搜索树的基本性质，左子树中的所有节点都要小于父节点，右子节点中的所有节点都大于父节点。删除掉该节点后，左子树中的最大值肯定小于右子树中的所有值，那么它就可以来替换需要删除的节点。反之,右子树中的最小值也可以。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

看下面的代码:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html

<?php

function find_min_node(&$root){
    if($root->left !=null ){
        return find_min_node($root->left);
    }else{
        return $root;
    }
}

function delete_node(&$root,$key){
    //根据传递进来的key,找到这个节点，并且要找到这个节点的父节点
    //如果需要删除的节点是根节点
    if($root->key == $key){
        $parent_node = $root->right;
        //根据$parent_node，查找到右子树中的最小的节点
        $node = find_min_node($parent_node);
        //将root节点进行替换
        $root->key = $node->key;
        $root->value = $node->value;
        //删除子节点
        unset($node);
        return $root;
    }else{
        //如果需要删除的节点并不是根节点
        //如果这个节点没有子节点
        if($root->left == null && $root->right == null){
            //直接删除这个节点
            //pass
            //return
        }
        //如果这个节点没有右子节点
        if($root->right ==null ){
            //获取左子树中的最大值节点
            //进行替换删除的操作
            //pass
            //return
        }else{
            //获取右子树中的最小值节点
            //进行替换删除的操作
            //pass
            //return
        }
    }
}
?>

在最后，我们还得说一下，二分搜索树的缺点。假设我们需要将数组[1,2,3,4,5]中的元素依次存放到一个空的二分搜索树中，那么就会生成一个以1为根节点，2为1的右子节点，3为2的右子节，4为3的右子节点，5为4的右子节点的二分搜索树，你回发现这棵二分搜索树的任意一个非叶子节点都不存在左子树。我们可以将这种情况视为二分搜索树的最坏情况，整棵树的高度为n(平均情况下为logN),再进行查找等操作的时候，时间复杂度将会下降到O(N)级别。对于这种情况的出现，并不是没有解决的办法，使用平衡树就可以解决，有兴趣的同学可以研究一下。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/bc/948.html