二叉搜索树(Binary Search Tree,BST)

这篇具有很好参考价值的文章主要介绍了二叉搜索树(Binary Search Tree,BST)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

二叉搜索树(Binary Search Tree,BST)

二叉搜索树(Binary Search Tree),也称二叉查找树或二叉排序树,是一种特殊的二叉树,它满足以下性质

  1. 对于二叉搜索树的每个节点
    • 左子树中的所有节点的值都小于该节点的值
    • 右子树中的所有节点的值都大于(或等于)该节点的值
  2. 对于二叉搜索树的任意节点,其左子树和右子树也是二叉搜索树。
    二叉搜索树(Binary Search Tree,BST)

由于这种特性,二叉搜索树可以支持高效地进行查找、插入和删除操作。对于查找操作,可以通过比较目标值与当前节点的值来决定向左子树还是右子树进行搜索。对于插入操作,可以按照比较结果找到合适的位置并插入新节点。对于删除操作,则需要按照一定规则来处理不同情况下的节点删除

插入节点

在二叉搜索树中插入一个新节点的步骤如下:

  1. 如果树为空,将新节点作为根节点。
  2. 如果树不为空,从根节点开始遍历树。
  3. 比较要插入的值与当前节点的值。
    • 如果要插入的值小于当前节点的值,向左子树方向继续遍历。
    • 如果要插入的值大于当前节点的值,向右子树方向继续遍历。
    • 如果要插入的值等于当前节点的值,根据具体需求决定是替换当前节点的值还是忽略该值。
  4. 当遇到空节点时,表示找到了合适的位置插入新节点。
  5. 创建一个新节点,并将其插入到空节点的位置。
  6. 完成插入操作。

示例代码:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}


class BinarySearchTree {
    private TreeNode root;

    public BinarySearchTree() {
        root = null;
    }

    // 插入节点
    public void insert(int val) {
        root = insertNode(root, val);
    }

    private TreeNode insertNode(TreeNode root, int val) {
        // 如果当前节点为空,说明找到了应该插入的位置,创建新节点并返回
        if (root == null) {
            return new TreeNode(val);
        }

        // 如果插入的值小于当前节点的值,向左子树插入
        if (val < root.val) {
            root.left = insertNode(root.left, val);
        } else if (val > root.val) {
            // 如果插入的值大于当前节点的值,向右子树插入
            root.right = insertNode(root.right, val);
        }

        return root;
    }
}

搜索节点(查找)

在二叉搜索树中搜索一个特定值的步骤如下:

  1. 从根节点开始,将要搜索的值与当前节点的值进行比较。
  2. 如果要搜索的值等于当前节点的值,返回true,表示找到了目标值。
  3. 如果要搜索的值小于当前节点的值,则向左子树方向继续搜索。
  4. 如果要搜索的值大于当前节点的值,则向右子树方向继续搜索。
  5. 如果遇到空节点,则表示未找到目标值,返回false。
  6. 重复步骤2至步骤5,直到找到目标值或搜索完整个树。
    下面是使用上述步骤实现搜索方法的示例代码:
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    // 搜索节点
    public boolean search(int val) {
        return searchNode(root, val);
    }

    private boolean searchNode(TreeNode root, int val) {
        // 当前节点为空,未找到目标值
        if (root == null) {
            return false;
        }

        // 目标值与当前节点的值相等,找到目标值
        if (val == root.val) {
            return true;
        } else if (val < root.val) {
            // 目标值小于当前节点的值,在左子树中继续搜索
            return searchNode(root.left, val);
        } else {
            // 目标值大于当前节点的值,在右子树中继续搜索
            return searchNode(root.right, val);
        }
    }
}

删除节点

在二叉搜索树中删除一个节点的步骤如下:文章来源地址https://www.toymoban.com/news/detail-707861.html

  1. 从根节点开始,找到要删除的节点。
  2. 如果要删除的值等于当前节点的值,根据下面不同的情况进行处理:
    a. 若该节点为叶节点(没有子节点),直接删除该节点。
    b. 若该节点只有一个子节点,将其子节点替代该节点的位置。
    c. 若该节点有两个子节点,找到右子树中最小的节点(或左子树中最大的节点),将该节点的值替代要删除的节点的值,然后递归删除该最小节点(或最大节点)。
  3. 如果要删除的值小于当前节点的值,则向左子树方向继续搜索。
  4. 如果要删除的值大于当前节点的值,则向右子树方向继续搜索。
  5. 当遇到空节点时,表示未找到要删除的节点。
  6. 完成删除操作。
    下面是使用上述步骤实现删除方法的示例代码:
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    private TreeNode deleteNode(TreeNode root, int val) {
        // 当前节点为空,未找到要删除的节点
        if (root == null) {
            return null;
        }

        // 如果要删除的值小于当前节点的值,在左子树中继续搜索
        if (val < root.val) {
            root.left = deleteNode(root.left, val);
        } else if (val > root.val) {
            // 如果要删除的值大于当前节点的值,在右子树中继续搜索
            root.right = deleteNode(root.right, val);
        } else {
            // 找到要删除的节点
            // 情况1: 当节点没有子节点时,直接返回 null
            if (root.left == null && root.right == null) {
                return null;
            }
            // 情况2: 当节点只有一个子节点时,返回子节点作为当前节点的替代
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }
            // 情况3: 当节点有两个子节点时,找到右子树中最小的节点,
            //       用该节点的值替代当前节点的值,并删除右子树中最小的节点
            TreeNode successor = findMin(root.right);
            root.val = successor.val;
            root.right = deleteNode(root.right, successor.val);
        }

        return root;
    }

    private TreeNode findMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}

到了这里,关于二叉搜索树(Binary Search Tree,BST)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构第四天: Complete Binary Search Tree 【搜索二叉树,完全二叉树】

     这道题需要的操作时排序并且需要遍历,最重要的一点它是个完全二叉树,所以数组是最适合的 这道题我的思路来自于浙江大学课件7.0.2完全二叉树 这道题说白就是将输入的样例构造成一个完全搜索二叉树。因为完全线索二叉树的 根节点一定是是一个处于左右子树中间的那

    2024年02月06日
    浏览(54)
  • 数据结构英文习题解析-第五章 二叉搜索树Binary Search Tree

    前言:最近快到FDS考试了,po重刷了一下学校的题目,自己整理了一些解析orz 因为po在自己找解析和学习的过程中非常痛苦,所以在此共享一下我的题目和自己写的解题思路,欢迎各位指出错误~全章节预计会陆续更新,可在专栏查看~ HW5 1.In a binary search tree, the keys on the same

    2024年04月09日
    浏览(48)
  • 二叉查找树(binary search tree)(难度7)

    C++数据结构与算法实现(目录) 答案在此:二叉查找树(binary search tree)(答案) 写在前面 部分内容参《算法导论》 基本接口实现 1 删除 删除值为value的第一个节点 删除叶子节点1 删除叶子节点1 (3)删除叶子节点1 删除有两个孩子的节点z 分成下面几个步骤进行: 1 找到

    2024年02月10日
    浏览(44)
  • 浙大数据结构第四周之04-树6 Complete Binary Search Tree

    A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties: The left subtree of a node contains only nodes with keys less than the node\\\'s key. The right subtree of a node contains only nodes with keys greater than or equal to the node\\\'s key. Both the left and right subtrees must also be binary search trees. A Comple

    2024年02月16日
    浏览(49)
  • 「二分搜索Binary Search」

    二分搜索其实也是双指针,左右指针。 题解 直接二分搜索解决。 Code 但是这个数有缺陷,假如有重复的数,例如[1,2,2,2,3],想要找左边界的2,应该返回索引为1,;或者右边界的2,返回索引3,但是发现找不了,只会给你返回中间的2,返回索引2,改进在下边。 结果 Code 注意此

    2024年02月15日
    浏览(37)
  • 二叉树(binary tree)

    二叉树(Binary Tree)是一种常见的树状数据结构,它由一组节点组成,每个节点最多有两个子节点,分别称为左子节点和右子节点。二叉树具有以下特点: 每个节点最多有两个子节点,分别称为左子节点和右子节点。 左子树和右子树也是二叉树,它们的结构与父节点类似。

    2024年02月09日
    浏览(42)
  • 二叉搜索树(BST)详解

    二叉搜索树是一个有序树 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 左、右子树也分别为二叉搜索树; 如图所示,两棵都是二叉排序树; 如图所示,左右两棵树都是是二叉搜

    2024年02月02日
    浏览(44)
  • 平衡二叉树(Balanced Binary Tree)

    平衡二叉树是一种特殊的二叉搜索树,它具有以下特点: 每个节点的左子树和右子树的高度差不超过1。 所有的子树也都是平衡二叉树。 通过保持平衡性,平衡二叉树可以在最坏情况下仍然具有较好的性能,保证查找、插入和删除操作的时间复杂度为O(log n)。 平衡二叉树的常

    2024年02月09日
    浏览(36)
  • 【C++】二叉搜索树BST

    二叉搜索树又称二叉排序树,具有以下 性质 : 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 搜索二叉树不允许数据冗余,也就是说其中 没有重复的数据

    2023年04月25日
    浏览(43)
  • 数据结构与算法 | 二叉树(Binary Tree)

    二叉树(Binary Tree)是一种树形数据结构,由节点构成,每个节点最多有两个子节点:一个左子节点和一个右子节点。 \\\"二叉树\\\"(Binary Tree)这个名称的由来是因为二叉树的每个节点最多有两个子节点,一个左子节点和一个右子节点。其中,“二叉”指的是两个,因此“二叉树

    2024年02月08日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包