二叉搜索树(BST)详解及代码实现

news/2024/10/30 10:25:21/

推荐可视化插入、删除节点的二叉树网站Binary Search Tree Visualization (usfca.edu)

1. 概述

        二叉搜索树(Binary Search Tree,简称BST)是一种特殊的二叉树结构,它具有以下特点:

  1. 有序性:对于BST中的每个节点,其左子树中的所有节点的值都小于该节点的值,而右子树中的所有节点的值都大于该节点的值。
  2. 递归性:BST的每个子树也是BST,即子树中的节点仍然满足有序性和递归性。
  3. 无重复值:BST中不允许存在相同值的节点。

        由于BST的有序性,它具有快速的查找、插入和删除操作的特点,因此被广泛应用于数据结构和算法中。

2. BST的查找操作

  • 当需要查找某个值时,从根节点开始,比较要查找的值与当前节点的值的大小关系。
  • 若相等,则找到目标节点;
  • 若小于当前节点的值,则在左子树中继续查找;
  • 若大于当前节点的值,则在右子树中继续查找。
  • 如果找到叶子节点仍然没有找到目标值,则说明目标值不存在于BST中。

3. BST的插入操作

  • 从根节点开始,比较要插入的值与当前节点的值的大小关系。
  • 若小于当前节点的值,则在左子树中继续插入;
  • 若大于当前节点的值,则在右子树中继续插入。
  • 直到找到一个空位置,将新节点插入其中。

4. BST的删除操作

BST(二叉搜索树)的删除操作涉及到以下几种情况:

  1. 删除叶子节点:如果要删除的节点是叶子节点(没有子节点),直接将其删除即可。

  2. 删除节点有一个子节点:如果要删除的节点只有一个子节点,将子节点替代要删除的节点的位置即可。

  3. 删除节点有两个子节点:如果要删除的节点有两个子节点,可以采用以下两种方法之一来替代删除节点:

    • 找到删除节点的右子树中的最小节点,将最小节点的值复制到删除节点,然后删除最小节点。
    • 找到删除节点的左子树中的最大节点,将最大节点的值复制到删除节点,然后删除最大节点。

如删除下面这个BST的节点5,会把节点 4 的值复制到节点4上,然后删除原来的节点4: 

 

5. 性能        

        在普通的二叉搜索树(Binary Search Tree,BST)中,各种操作的平均时间复杂度取决于树的平衡性。各种操作的平均时间复杂度: O(log n)

        需要注意的是,这里的时间复杂度是基于平衡的二叉搜索树的情况。如果树不平衡,例如出现倾斜树(所有节点都集中在一条路径上),则各种操作的时间复杂度可能退化为 O(n),其中 n 是树中节点的数量。

下图描述了BST退化成线性表:

 

        因此,为了确保较好的性能,可以使用自平衡的二叉搜索树(如AVL树、红黑树)或其他平衡树的变种来保持树的平衡性,从而保证各种操作的时间复杂度在对数级别。

6. 代码实现

(1)树节点

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

(2)BST

public class BST {private TreeNode root;public BST() {root = null;}//插入操作public void insert(int val) {root = insertNode(root, val);}private TreeNode insertNode(TreeNode root, int val) {if (root == null) {root = new TreeNode(val);return root;}if (val < root.val) {root.left = insertNode(root.left, val);} else if (val > root.val) {root.right = insertNode(root.right,val);}return root;}// 查找操作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);}}// 删除操作public void delete(int val) {root = deleteNode(root, val);}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 {// 找到要删除的节点if (root.left == null) {return root.right;} else if (root.right == null) {return root.left;}// 如果要删除的节点有两个子节点// 找到右子树中的最小节点,将其值赋给要删除的节点// 然后在右子树中删除最小节点TreeNode minNode = findMin(root.right);root.val = minNode.val;root.right = deleteNode(root.right, minNode.val);}return root;}private TreeNode findMin(TreeNode node) {while (node.left != null) {node = node.left;}return node;}
}
  • insert 方法用于插入节点。它通过调用 insertNode 方法实现。在 insertNode 方法中,首先判断根节点是否为空,如果为空则直接创建一个新节点作为根节点。如果根节点不为空,则比较要插入的值与当前节点的值的大小关系,如果小于当前节点的值,则递归地插入到左子树中,如果大于当前节点的值,则递归地插入到右子树中。
  • search 方法用于查找节点。它通过调用 searchNode 方法实现。在 searchNode 方法中,首先判断当前节点是否为空,如果为空则说明没有找到目标值,返回 false。如果当前节点的值等于目标值,则说明找到了,返回 true。如果目标值小于当前节点的值,则递归地在左子树中查找。如果目标值大于当前节点的值,则递归地在右子树中查找。
  • delete 方法用于删除节点。它通过调用 deleteNode 方法实现。在 deleteNode 方法中,首先判断当前节点是否为空,如果为空则直接返回 null如果目标值小于当前节点的值,则递归地在左子树中删除。如果目标值大于当前节点的值,则递归地在右子树中删除。如果目标值等于当前节点的值,则分三种情况处理删除操作:如果要删除的节点没有子节点,则直接将其置为 null;如果要删除的节点只有一个子节点,则将其子节点替换为要删除的节点;如果要删除的节点有两个子节点,则找到右子树中的最小节点,将其值赋给要删除的节点,并在右子树中递归地删除最小节点。
  • 另外还定义了一个辅助方法 findMin,用于找到给定节点下的最小节点,即最左子节点。

http://www.ppmy.cn/news/107926.html

相关文章

Python - numpy basic

目录 数组array的创建 1 通过list创建array 2 通过list创建二维数组 3 通过arange函数创建 等差数组 4 通过zeros函数创建 零矩阵 5 通过eyes函数创建 单位矩阵 数组array的访问 1 访问形状/元素个数/数据类型 2 访问一维数组的位置/范围 3 访问二维数组的位置/范围 4…

Pytorch神经网络常用函数介绍(持续更新……)

1. nn.Linear() 在深度学习中&#xff0c;nn.Linear()是 PyTorch 中用于定义线性层的类。它用于构建神经网络模型的线性层&#xff0c;将输入数据进行线性变换。nn.Linear()的参数用法如下&#xff1a; nn.Linear(in_features, out_features, biasTrue)参数解释如下&#xff…

【尔嵘】感恩四周年,感谢支持

前言 注意&#xff1a;为感谢各位铁粉支持&#xff0c;【尔嵘】将随机一个号码赠送一本vue.js书籍&#xff0c;欢迎评论区留言&#xff01; 在当前互联网领域中&#xff0c;CSDN是一个非常知名的技术社区&#xff0c;在这里你可以接触到很多高质量的技术文章和技术交流。对于技…

Oracle实现主键字段自增

Oracle实现主键自增有4种方式&#xff1a; Identity Columns新特性自增&#xff08;Oracle版本≥12c&#xff09; 创建自增序列&#xff0c;创建表时&#xff0c;给主键字段默认使用自增序列 创建自增序列&#xff0c;使用触发器使主键自增 创建自增序列&#xff0c;插入语句&…

测试环境部署hadoop

两台服务器的主机名 hostname ssh ecs-qar1-0001 ssh ecs-qar1-0002 配置jdk vim /etc/profile 旧有的 export JAVA_HOME/usr/java/openjdk-8u41 export JAVA_HOME/bigdata/server/jdk export PATH P A T H : PATH: PATH:JAVA_HOME/bin export MAVEN_HOME/work/apache-m…

越秀地产K2流程平台年度报告出炉,来看看“别人家”的流程平台

前不久&#xff0c;越秀地产K2流程平台2022年度运营报告新鲜出炉&#xff0c;K2流程平台再次递交出色成绩单。 2022年&#xff0c;越秀地产在K2流程平台上审批完成的流程共计103万条&#xff0c;日均发起流程数达2800条&#xff0c;日均点击量5万。在大体量、高负荷情形下&…

(2022,MoCA)Few-shot 图像生成的原型记忆(Prototype Memory)和注意力机制

Prototype Memory and Attention Mechanisms for Few Shot Image Generation 公众号&#xff1a;EDPJ 目录 0. 摘要 1. 简介 2. 相关工作 3. 方法 3.1 原型记忆学习 3.2 记忆概念注意力&#xff08;MEMORY CONCEPT ATTENTION&#xff0c;MoCA&#xff09; 3.3 空间上…

clipboard复制粘题问题

clipboard复制粘贴问题 简单的clipboard用法引入clipboard使用方法 通过监听获取剪切板数据自定义获取clipboard剪切板值 记录下项目中使用clipboard复制粘题问题 简单的clipboard用法 引入clipboard npm install clipboard --save官网地址:传送门 使用方法 通过监听获取剪切…