算法学习十八、二叉树基础(下)

二叉查找树(Binary Search Tree)

二叉查找树要求,在树中的任意一个节点,其左子树中的每个节点的值,都要小于这个节点的值,而右子树节点的值都大于这个节点的值。

1. 二叉查找树的查找操作

我们先取根节点,如果它等于我们要查找的数据,那就返回。如果要查找的数据比根节点的值小,那就在左子树中递归查找;如果要查找的数据比根节点的值大,那就在右子树中递归查找。

class TreeNode
{
    public $data;


    public $left;


    public $right;


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


class Tree
{
    public $head;


    public function __construct($headData = null)
    {
        if (! empty($headData)) {
            $this->head = new TreeNode($headData);
        } else {
            $this->head = null;
        }
    }
    
    public function find($data)
    {
        if ($this->head == null) {
            return null;
        }
    
        $node = $this->head;
        while ($node != null) {
            if ($data === $node->data) {
                return $node;
            } else if ($data > $node->data) {
                $node = $node->right;
            } else {
                $node = $node->left;
            }
        }
    
        return null;
   

2. 二叉查找树的插入操作

我们只需要从根节点开始,依次比较要插入的数据和节点的大小关系。如果要插入的数据比节点的数据大,并且节点的右子树为空,就将新数据直接插到右子节点的位置;如果不为空,就再递归遍历右子树,查找插入位置。同理,如果要插入的数据比节点数值小,并且节点的左子树为空,就将新数据插入到左子节点的位置;如果不为空,就再递归遍历左子树,查找插入位置。

public function insert($data)
{
    if ($this->head == null) {
        $this->head = new TreeNode($data);
        return true;
    }


    $node = $this->head;
    while ($node != null) {
        if ($data > $node->data) {
            if ($node->right == null) {
                $node->right = new TreeNode($data);
                return true;
            }
            $node = $node->right;
        } else {
            if ($node->left == null) {
                $node->left = new TreeNode($data);
                return true;
            }
            $node = $node->left;
        }
    }
}

3. 二叉查找树的删除操作

针对要删除节点的子节点个数的不同,我们需要分三种情况来处理。

第一种情况是,如果要删除的节点没有子节点,我们只需要直接将父节点中,指向要删除节点的指针置为 null。比如图中的删除节点 55。

第二种情况是,如果要删除的节点只有一个子节点(只有左子节点或者右子节点),我们只需要更新父节点中,指向要删除节点的指针,让它指向要删除节点的子节点就可以了。比如图中的删除节点 13。

第三种情况是,如果要删除的节点有两个子节点,这就比较复杂了。我们需要找到这个节点的右子树中的最小节点,把它替换到要删除的节点上。然后再删除掉这个最小节点,因为最小节点肯定没有左子节点。比如图中的删除节点 18。

public function delete($data)
{
    // 找到需要删除节点
    $node   = $this->head;
    $pnode  = null; // pnode 为 node 的父节点
    while ($node != null) {
        $pnode = $node;
        if ($node->data == $data) {
            break;
        } elseif ($data > $node->data) {
            $node = $node->right;
        } else {
            $node = $node->left;
        }
    }
    // 未找到
    if ($node == null) {
        return false;
    }


    // 如果要删除的节点有两个子节点,删除右子树的最小节点
    // 这里找到右子节点的最小节点,并没有执行删除,只是把最小节点的值赋值给了要删除节点,而把要删除的节点变为了最小节点
    if ($node->left != null && $node->right != null) {
        $minPP  = $node;// minPP 是 minP 的父节点
        $minP   = $node->right;
        while ($minP->left != null) {
            $minPP  = $minP;
            $minP   = $minP->left;
        }
        $node->data = $minP->data;
        $node       = $minP;
        $pnode      = $minPP;
    }


    // 父节点指向的位置
    if ($node->left != null) {
        $child = $node->left;
    } elseif ($node->right != null) {
        $child = $node->right;
    } else {
        $child = null;
    }
    
    // 父节点开始指向
    if ($pnode == null) {
        // 删除的是根节点
        $this->head = $child;
    } elseif ($pnode->left == $node) {
        $pnode->left = $child;
    } else {
        $pnode->right = $child;
    }

4. 二叉查找树的其他操作

除了插入、删除、查找操作之外,二叉查找树中还可以支持快速地查找最大节点和最小节点、前驱节点和后继节点。

二叉查找树除了支持上面几个操作之外,还有一个重要的特性,就是中序遍历二叉查找树,可以输出有序的数据序列,时间复杂度是 O(n),非常高效。因此,二叉查找树也叫作二叉排序树。

支持重复数据的二叉查找树

前面讲二叉查找树的时候,我们默认树中节点存储的都是数字。很多时候,在实际的软件开发中,我们在二叉查找树中存储的,是一个包含很多字段的对象。我们利用对象的某个字段作为键值(key)来构建二叉查找树。我们把对象中的其他字段叫作卫星数据。

那如果存储的两个对象键值相同,这种情况该怎么处理呢?

第一种方法比较容易。二叉查找树中每一个节点不只存储一个数据,我们可以通过链表和支持动态扩容的数组等数据结构,把值相同的数据都存储在同一个节点上。

第二种方法。每个节点仍然只存储一个数据。在查找插入位置的过程中,如果碰到一个节点的值,与要插入数据的值相同,我们就将这个要插入的数据放到这个节点的右子树,也就是说,把这个新插入的数据当作大于这个节点的值来处理

当要查找数据的时候,遇到值相同的节点,我们并不停止查找操作,而是继续在右子树中查找,直到遇到叶子节点,才停止。这样就可以把键值等于要查找值的所有节点都找出来。

对于删除操作,我们也需要先查找到每个要删除的节点,然后再按前面讲的删除操作的方法,依次删除。

二叉查找树的时间复杂度分析

二叉查找树的形态各式各样,它们的查找、插入、删除操作的执行效率也是不一样的。图中第一种二叉查找树,根节点的左右子树极度不平衡,已经退化成了链表,所以查找的时间复杂度就变成了 O(n)。

最理想的情况,二叉查找树是一棵完全二叉树(或满二叉树)。这个时候,插入、删除、查找的时间复杂度是多少呢?

从前面的例子、图,以及还有代码来看,不管操作是插入、删除还是查找,时间复杂度其实都跟树的高度成正比,也就是 O(height)。既然这样,现在问题就转变成,如何求一棵包含 n 个节点的完全二叉树的高度?

树的高度就等于最大层数减一,为了方便计算,我们转换成层来表示。从图中可以看出,包含 n 个节点的完全二叉树中,第一层包含 1 个节点,第二层包含 2 个节点,第三层包含 4 个节点,依次类推,下面一层节点个数是上一层的 2 倍,第 K 层包含的节点个数就是 2^(K-1)。

不过,对于完全二叉树来说,最后一层的节点个数有点儿不遵守上面的规律了。它包含的节点个数在 1 个到 2^(L-1) 个之间(我们假设最大层数是 L)。如果我们把每一层的节点个数加起来就是总的节点个数 n。也就是说,如果节点的个数是 n,那么 n 满足这样一个关系:

n >= 1+2+4+8+...+2^(L-2)+1
n <= 1+2+4+8+...+2^(L-2)+2^(L-1)

借助等比数列的求和公式,我们可以计算出,L 的范围是[log2(n+1), log2n +1]。完全二叉树的层数小于等于 log2n +1,也就是说,完全二叉树的高度小于等于 log2n。

显然,极度不平衡的二叉查找树,它的查找性能肯定不能满足我们的需求。我们需要构建一种不管怎么删除、插入数据,在任何时候,都能保持任意节点左右子树都比较平衡的二叉查找树,这就是我们下一节课要详细讲的,一种特殊的二叉查找树,平衡二叉查找树。平衡二叉查找树的高度接近 logn,所以插入、删除、查找操作的时间复杂度也比较稳定,是 O(logn)。

有了散列表,为什么还有二叉查找树

第一,散列表中的数据是无序存储的,如果要输出有序的数据,需要先进行排序。而对于二叉查找树来说,我们只需要中序遍历,就可以在 O(n) 的时间复杂度内,输出有序的数据序列。

第二,散列表扩容耗时很多,而且当遇到散列冲突时,性能不稳定,尽管二叉查找树的性能不稳定,但是在工程中,我们最常用的平衡二叉查找树的性能非常稳定,时间复杂度稳定在 O(logn)。

第三,笼统地来说,尽管散列表的查找等操作的时间复杂度是常量级的,但因为哈希冲突的存在,这个常量不一定比 logn 小,所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时,也不一定就比平衡二叉查找树的效率高。

第四,散列表的构造比二叉查找树要复杂,需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题,而且这个问题的解决方案比较成熟、固定。

最后,为了避免过多的散列冲突,散列表装载因子不能太大,特别是基于开放寻址法解决冲突的散列表,不然会浪费一定的存储空间。