【Java 数据结构】实现一个二叉搜索树

article/2025/8/25 1:11:34


目录 

1、认识二叉搜索树

2、实现一个二叉搜索树

2.1 成员变量

2.2 insert 方法

2.3 search 方法 

2.4 remove 方法(重点)

3、二叉搜索树总结


1、认识二叉搜索树

从字面上来看,它只比二叉树多了搜索两个字,我们回想一下,如果要是在二叉树中查找一个元素的话,需要遍历这棵树,效率很慢,而二叉搜索树,则会效率高很多,为什么呢?

二叉搜索树,可以是一棵空树,或者是具有以下的性质:

  • 若它的左子树不为空,则左树上所有的节点都小于根节点
  • 若它的右子树不为空,则右树上所有节点的都大于根节点
  • 它的左子树和右子树也分别为二叉搜索树

通俗来讲,左孩子都小于父节点,右孩子都大于父节点,以此类推,这里我们画图来认识下二叉搜索树:

当然二叉搜索树不要求是完全二叉树或满二叉树,甚至会出现单分支的二叉搜索树,所以针对这种特殊的情况进行了优化也就延申而来的 AVL树,这个是后续的话题。

仔细观察上图,可以观察出二叉搜索树的一个新特性:

中序遍历二叉搜索树是有序的,所以二叉搜索树也被称为二叉排序树


2、实现一个二叉搜索树

2.1 成员变量

public class BinarySearchTree {private TreeNode root; //存放根节点private static class TreeNode {private int val;private TreeNode left;private TreeNode right;private TreeNode(int val) {this.val = val;}}
}

 这里跟我们的二叉树成员变量大同小异,主要是去实现插入,查找,删除的逻辑。

2.2 insert 方法

往二叉搜索树插入一个节点的时候,我们要注意两点,首先如果二叉搜索树为空,则直接令 root 为当前插入的节点即可,那如果二叉搜索树不为空,我们则需要利用二叉搜索树的性质,找到该节点要插入的位置即可,具体我们来看下图:

通过动图我们可以看到,当二叉搜索树不为空的时候,新的元素会依次节点比较,如果比根节点大,则去根的右边,比根节点小,则取根的左边,以此类推。(搜索二叉树不存在相同的元素)

但是我们用代码如何实现呢?定义一个 cur 引用,当 cur 等于 null 了,则表示是我要插入的位置,既然找到了要插入的位置,但是还得知道这个位置的父节点是谁,通过父节点的指针域给连接起来,于是代码可以这样写:

public boolean insert(int key) {// 二叉搜索树没有节点的情况if (root == null) {root = new TreeNode(key);return true;}// 二叉搜索树不为空的情况 -> 找到该节点要插入的位置进行插入// 如果已经存在该节点了, 则不用插入 -> 二叉搜索树中不能出现重复值TreeNode parent = null; // 记录cur的父节点TreeNode cur = root;while (cur != null) {if (cur.val < key) {parent = cur;cur = cur.right;} else if (cur.val > key) {parent = cur;cur = cur.left;} else {return false; // 插入重复的节点}}// 走到这, cur为空了, key 需要插入到 parent 的左节点或右节点中TreeNode newNode = new TreeNode(key);if (parent.val < key) {parent.right = newNode;} else {parent.left = newNode;}return true;
}

2.3 search 方法 

搜索方法,也就是给一个 key 你,让你在这颗二叉树找有没有这个元素,有的话返回该节点,没有的话返回 null,这个就很简单了, 跟上面的步骤一样无非就是碰到相同的元素返回 cur 嘛,当 cur 根据 key 遍历完这棵二叉搜索树的时候,也就是 cur 为 null 了,则表示没有该元素,直接返回 null即可。

代码如下:

public TreeNode search(int key) {TreeNode cur = root;while (cur != null) {if (cur.val < key) {cur = cur.right;} else if (cur.val > key) {cur = cur.left;} else {return cur;}}return null;
}

2.4 remove 方法(重点)

在二叉搜索树中,删除一个节点是一个比较麻烦的事,但是只要把各种删除的情况下列举出来,一一解决它即可,对于二叉搜索树来说,你删除了一个节点,它仍然满足二叉搜索树的性质。

设 cur 为要删除的节点,所以首先我们得判断这个二叉搜索树中,是否存在要删除的节点,这个逻辑上面已经写过了,找到要删除的节点后,我们一共会面临三种情况:

① 如果 cur 没有左子树的情况

  • 如果 cur 是 root 的情况,只需要 root = cur.right
  • 如果 cur 不是 root,cur 是 parent.left 的情况,只需要 parent.left = cur.right
  • 如果 cur 不是 root,cur 是 parent.right 的情况,只需要 parent.right = cur.right

图解: 

 ② 如果 cur 没有右子树的情况

  • 如果 cur 是 root 的情况,只需要 root = cur.left
  • 如果 cur 不是 root,cur 是 parent.left 的情况,只需要 parent.left = cur.left
  • 如果 cur 不是 root,cur 是 parent.right 的情况,只需要 parent.right = cur.left

图解: 

③ 如果 cur 既有左子树,又有右子树的情况

  • 使用替换法进行删除,即在 cur 的右子树中,一直往左寻找最小的元素,将这个最小值赋值给要删除节点的 val 值中,接着把这个最小元素的节点删除即可,删除的逻辑见下图和完整删除代码。

 

代码如下:

public boolean remove(int key) {TreeNode parent = null;TreeNode cur = root;while (cur != null) {if (cur.val < key) {parent = cur;cur = cur.right;} else if (cur.val > key) {parent = cur;cur = cur.left;} else {removeNode(parent, cur);return true;}}return false;
}private void removeNode(TreeNode parent, TreeNode cur) {if (cur.left == null) {if (cur == root) {root = cur.right;} else if (cur == parent.left) {parent.left = cur.right;} else {parent.right = cur.right;}} else if (cur.right == null) {if (cur == root) {root = cur.left;} else if (cur == parent.left) {parent.left = cur.left;} else {parent.right = cur.left;}} else {TreeNode target = cur.right;TreeNode targetParent = cur;while (target.left != null) {targetParent = target;target = target.left;}// 走到这, target就是要删除节点的右子树中最小的节点, 接下来进行覆盖cur.val = target.val;// 覆盖完成, 现在需要删除 target 节点// 如果 cur.right 没有左孩子的情况, 此时的target就是cur.right// 即直接将 cur.right 覆盖到 cur 位置, 也就是满足 target == targetParent.right 条件// 所以需要进行特殊处理.if (target == targetParent.right) {targetParent.right = target.right;} else {targetParent.left = target.right;}}
}

3、二叉搜索树总结

二叉搜索树在最好的情况下为完全二叉树,查找的平均比较次数为:logn

二叉搜索树在最差的情况下退化成但分支,查找的平均比较次数为:n/2

所以二叉搜索树在最差的情况下效率是不高的,为了解决单分支的情况,于是有了 AVL树,当发现二叉搜索树左右子树高度差太大,会自动旋转,以致平衡,避免旋转的次数太多,又引入了红黑树,给节点增加了颜色,细节部分后期讲解,这里有个概念即可,下期将会介绍由红黑树作为底层的集合:TreeSet 和 TreeMap


下期预告: 【Java 数据结构】TreeSet 和 TreeMap


http://chatgpt.dhexx.cn/article/nxcwSSE2.shtml

相关文章

java二叉搜索树详解

文章目录 一、概念二、相关操作2.0节点相关代码&#xff1a;2.1查找2.2插入2.3删除&#xff08;重难点&#xff09;2.4测试用例 三、小结 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 一、概念 二叉搜索树又称二叉排序树 它或者是一棵空树&#xff…

二叉搜索树

目录 二叉搜索树二叉搜索树概念 增删查改接口插入递归插入查找递归查找删除递归删除 成员函数拷贝构造拷贝赋值析构 二叉搜索树的应用二叉搜索树的性能分析 二叉搜索树 二叉搜索树概念 二叉搜索树又称二叉排序树&#xff0c;它或者是一棵空树&#xff0c;或者是具有以下性质的…

【数据结构】二叉搜索树

目录 一.二叉搜索树规则 二.框架 三.实现 1.查找, 插入, 删除 迭代法实现 递归法实现 2.构造, 赋值 默认构造 拷贝构造 赋值运算符重载 3.中序遍历 四.时间复杂度及稳定性 五.key模型与key/value模型 1.key模型 2.key/value模型 一.二叉搜索树规则 二叉搜索树又…

数据结构——二叉搜索树详解

二叉搜索树 一、什么是二叉搜索树 二叉搜索树&#xff08;BST&#xff0c;Binary Search Tree&#xff09;&#xff0c;也称二叉排序树或二叉查找树。 二叉搜索树&#xff1a;一棵二叉树&#xff0c;可以为空&#xff1b;如果不为空&#xff0c;满足以下性质&#xff1a; 非空…

【数据结构】——二叉搜索树

目录 前言 二叉搜索树的概念 二叉搜索树的操作 树的节点实现 搜索树的基本结构 插入数据 查找 删除 拷贝构造函数 二叉搜索树的应用 前言 在c中的容器里map和set的学习需要二叉搜索树的铺垫&#xff0c;也为后边的的红黑树和AVL树做铺垫&#xff0c;也就是说&#xff0c;…

二叉搜索树(二叉排序树)

一.概念 二叉搜索树又称二叉排序树&#xff0c;具有以下性质&#xff1a; 若它的左子树不为空&#xff0c;则左子树上所有节点的值都小于根节点的值若它的右子树不为空&#xff0c;则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树 注意&#xff1a;二…

二叉排序树(二叉查找树、二叉搜索树)(图解+完整代码)

目录 ⚽1.什么是二叉排序树 &#x1f3d0;2.构建二叉排序树 &#x1f3c0;3.二叉排序树的查找操作 &#x1f94e;4.二叉排序树的删除 &#x1f3b1;5.完整代码 ⚽1.什么是二叉排序树 我们直接看它的性质&#xff1a; 若它的左子树不空&#xff0c;则左子树上所有结点的值…

种树:二叉树、二叉搜索树、AVL树、红黑树、哈夫曼树、B树、树与森林

虽然今天不是植树节&#xff0c;但是我今天想种树。 文章目录 树&#xff0c;什么是树&#xff1f;二叉树定义二叉树的创建二叉树的前中后序遍历前序遍历&#xff1a;中序遍历后序遍历已知前序、中序遍历结果&#xff0c;还原二叉树已知后序、中序遍历结果&#xff0c;还原二叉…

java lrucache_Java LruCache 的使用及原理

概述 LRU (Least Recently Used) 的意思就是近期最少使用算法&#xff0c;它的核心思想就是会优先淘汰那些近期最少使用的缓存对象。 在我们日常开发中&#xff0c;UI 界面进行网络图片加载是很正常的一件事情&#xff0c;但是当界面上的图片过于多的时候&#xff0c;不可能每次…

LruCache和DiskLruCache

前言 Android中的三级缓存主要就是内存缓存和硬盘缓存。 Lru(least recently used)意为最近最少使用算法&#xff0c;核心思想就是当缓存满时&#xff0c;会优先淘汰最近最少使用的缓存对象。 LruCache的使用 在Android中可以直接使用LruCache&#xff0c;算法原理是&#xff1…

Android LruCache 缓存

使用场景 1、场景一&#xff1a;图片缓存利器。 可以规定缓存大小、有效避免OOM、自动移除队尾不用的图片缓存、避免HashMap各种问题。 2、场景二&#xff1a;通信缓存 从服务端需要获取数据&#xff0c;但是当访问的数据比较大&#xff0c;比较多&#xff0c;并且是重复数…

Java——LRUCache

概念 简单来说&#xff0c;由于我们的空间是有限的&#xff0c;所以发明了这个数据结构&#xff0c;当我们的空间不够添加新的元素时&#xff0c;就会删除最近最少使用的元素。 其底层逻辑通过哈希表和链表共同实现。哈希表中存储链表的每一个元素&#xff0c;方便进行元素的…

LruCache缓存

Lru算法&#xff1a; Lru 指的是“Least Recently Used-近期最少使用算法”。 1、那么LruCache到底是什么呢&#xff1f; LruCache 是对限定数量的缓存对象持有强引用的缓存&#xff0c;每一次缓存对象被访问&#xff0c;都会被移动到队列的头部。当有对象要被添加到已经达到数…

LruCache 源码解析

1. 概述 对于 Android 开发者&#xff0c;LruCache 肯定不陌生&#xff0c;几乎所有的图片缓存框架都会用到它来实现内存缓存等&#xff0c;可见 LruCache 在 Android 开发中的重要性。LRU 是 Least Recently Used 的缩写&#xff0c;近期最少使用的意思。当我们进行缓存的时候…

LruCache

LruCache这个类是通过Glide得知的&#xff0c;不过它是自己又基于LRU算法自己写了个LruCache工具类&#xff0c;不过基本原理类似&#xff0c;都是基于LRU算法实现的 1.来源 一般来说&#xff0c;缓存策略主要包含缓存的添加、获取和删除这三类操作。如何添加和获取缓存这个比…

Android基础-LruCache原理解析

一、Android中的缓存策略 一般来说&#xff0c;缓存策略主要包含缓存的添加、获取和删除这三类操作。如何添加和获取缓存这个比较好理解&#xff0c;那么为什么还要删除缓存呢&#xff1f;这是因为不管是内存缓存还是硬盘缓存&#xff0c;它们的缓存大小都是有限的。当缓存满了…

LRUCache详解

1.概念 LRU是Least Recently Used的缩写&#xff0c;意思是最近最少使用&#xff0c;它是一种Cache替换算法。 Cache的容量有限&#xff0c;因此当Cache的容量用完后&#xff0c;而又有新的内容需要添加进来时&#xff0c; 就需要挑选并舍弃原有的部分内容&#xff0c;从而腾出…

LRUCache 详解

LRU算法详解 一、什么是 LRU 算法 就是一种缓存淘汰策略。 计算机的缓存容量有限&#xff0c;如果缓存满了就要删除一些内容&#xff0c;给新内容腾位置。但问题是&#xff0c;删除哪些内容呢&#xff1f;我们肯定希望删掉哪些没什么用的缓存&#xff0c;而把有用的数据继续…

LRU Cache

前言 哈喽&#xff0c;各位小伙伴大家好&#xff0c;本章内容为大家介绍计算机当中为了提高数据相互传输时的效率而引进的一种重要设计结构叫做LRU Cache,下面将为大家详细介绍什么是LRU Cache,以及它是如何是实现的&#xff0c;如何提升效率的。 1.什么是LRU Cache? LRU是L…

uniapp日历原生插件

<template><!-- 打卡日历页面 --><view classall><view class"bar"><!-- 上一个月 --><view class"previous" click"handleCalendar(0)"><button class"barbtn">上一月</button><…