数据结构和算法(二叉搜索树)

举报
林寻星辰 发表于 2023/03/22 15:02:47 2023/03/22
【摘要】 概述二叉搜索树是二叉树的一种特殊形式。 二叉搜索树具有以下性质:每个节点中的值必须大于(或等于)其左侧子树中的任何值,但小于(或等于)其右侧子树中的任何值。二叉搜索树(BST)是二叉树的一种特殊表示形式,它满足如下特性:每个节点中的值必须大于(或等于)存储在其左侧子树中的任何值。每个节点中的值必须小于(或等于)存储在其右子树中的任何值。在二叉搜索树中实现搜索操作 - 介绍二叉搜索树主要支持三...

概述

二叉搜索树是二叉树的一种特殊形式。 二叉搜索树具有以下性质:每个节点中的值必须大于(或等于)其左侧子树中的任何值,但小于(或等于)其右侧子树中的任何值。


二叉搜索树(BST)是二叉树的一种特殊表示形式,它满足如下特性:

每个节点中的值必须大于(或等于)存储在其左侧子树中的任何值。

每个节点中的值必须小于(或等于)存储在其右子树中的任何值。

在二叉搜索树中实现搜索操作 - 介绍

二叉搜索树主要支持三个操作:搜索、插入和删除。 在本章中,我们将讨论如何在二叉搜索树中搜索特定的值。

根据BST的特性,对于每个节点:

如果目标值等于节点的值,则返回节点;

如果目标值小于节点的值,则继续在左子树中搜索;

如果目标值大于节点的值,则继续在右子树中搜索。

在二叉搜索树中实现插入操作 - 介绍

二叉搜索树中的另一个常见操作是插入一个新节点。有许多不同的方法去插入新节点,这篇文章中,我们只讨论一种使整体操作变化最小的经典方法。 它的主要思想是为目标节点找出合适的叶节点位置,然后将该节点作为叶节点插入。 因此,搜索将成为插入的起始。

与搜索操作类似,对于每个节点,我们将:

  • 根据节点值与目标节点值的关系,搜索左子树或右子树;
  • 重复步骤 1 直到到达外部节点;
  • 根据节点的值与目标节点的值的关系,将新节点添加为其左侧或右侧的子节点。

举例:(来源力扣)

二叉搜索树中的插入操作

给定二叉搜索树(BST)的根节点 root 和要插入树中的值 value ,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ,新值和原始二叉搜索树中的任意节点值都不同。

注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

输入:root = [40,20,60,10,30,50,70], val = 25

输出:[40,20,60,10,30,50,70,null,null,25]

插入一个数,需要考虑的是判断跟根节点的大小来判断插入哪一个子树,如果下面没有子树,则直接进行插入就可以了,如果有子树,就需要继续比较大小,知道到达叶子节点.

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root==null){
            return new TreeNode(val);
        }
        if(root.val>val){
            root.left=insertIntoBST(root.left,val);
        }else{
            root.right=insertIntoBST(root.right,val);
        }
        return root;
    }
}
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        TreeNode pos = root;
        while (pos != null) {
            if (val < pos.val) {
                if (pos.left == null) {
                    pos.left = new TreeNode(val);
                    break;
                } else {
                    pos = pos.left;
                }
            } else {
                if (pos.right == null) {
                    pos.right = new TreeNode(val);
                    break;
                } else {
                    pos = pos.right;
                }
            }
        }
        return root;
    }
}

在二叉搜索树中实现删除操作 - 介绍

删除要比我们前面提到过的两种操作复杂许多。有许多不同的删除节点的方法,这篇文章中,我们只讨论一种使整体操作变化最小的方法。我们的方案是用一个合适的子节点来替换要删除的目标节点。根据其子节点的个数,我们需考虑以下三种情况:

  • 1. 如果目标节点没有子节点,我们可以直接移除该目标节点。
  • 2. 如果目标节只有一个子节点,我们可以用其子节点作为替换。
  • 3. 如果目标节点有两个子节点,我们需要用其中序后继节点或者前驱节点来替换,再删除该目标节点。

举例:(来源力扣)

删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。

一般来说,删除节点可分为两个步骤:

首先找到需要删除的节点;

如果找到了,删除它。

输入:root = [5,3,6,2,4,null,7], key = 3

输出:[5,4,6,2,null,null,7]

解释:给定需要删除的节点值是 3,所以我们首先找到 3 这个节点,然后删除它。

一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。

另一个正确答案是 [5,2,6,null,4,null,7]。

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        if (key < root.val) {
            // 待删除节点在左子树中
            root.left = deleteNode(root.left, key);
            return root;
        } else if (key > root.val) {
            // 待删除节点在右子树中
            root.right = deleteNode(root.right, key);
            return root;
        } else {
            // key == root.val,root 为待删除节点
            if (root.left == null) {
                // 返回右子树作为新的根
                return root.right;
            } else if (root.right == null) {
                // 返回左子树作为新的根
                return root.left;
            } else {
                // 左右子树都存在,返回后继节点(右子树最左叶子)作为新的根
                TreeNode successor = min(root.right);
                successor.right = deleteMin(root.right);
                successor.left = root.left;
                return successor;
            }
        }
    }

    private TreeNode min(TreeNode node) {
        if (node.left == null) {
            return node;
        }
        return min(node.left);
    }

    private TreeNode deleteMin(TreeNode node) {
        if (node.left == null) {
            return node.right;
        }
        node.left = deleteMin(node.left);
        return node;
    }
}
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        if (root.val > key) {
            root.left = deleteNode(root.left, key);
            return root;
        }
        if (root.val < key) {
            root.right = deleteNode(root.right, key);
            return root;
        }
        if (root.val == key) {
            if (root.left == null && root.right == null) {
                return null;
            }
            if (root.right == null) {
                return root.left;
            }
            if (root.left == null) {
                return root.right;
            }
            TreeNode successor = root.right;
            while (successor.left != null) {
                successor = successor.left;
            }
            root.right = deleteNode(root.right, successor.val);
            successor.right = root.right;
            successor.left = root.left;
            return successor;
        }
        return root;
    }
}

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。