【数据结构】二叉搜索树（Java + 链表实现）

Hi~！这里是奋斗的明志，很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~~
🌱🌱个人主页：奋斗的明志
🌱🌱所属专栏：数据结构、LeetCode专栏

📚本系列文章为个人学习笔记，在这里撰写成文一为巩固知识，二为展示我的学习过程及理解。文笔、排版拙劣，望见谅。

前言

Map接口是独立的
实现Iterable接口的集合都是可以使用 for - Each 语句进行打印的

搜索性能会非常高

一、二叉搜索树

1.概念

二叉搜索树又称为二叉排序树，它或者是一棵空树，或者是具以下性质的二叉树：

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

如果中序遍历这棵二叉搜索树，会发现遍历的结果是有序的

接下来就模拟实现一下二叉搜索树

首先，和之前二叉树的实现一样，都是一个节点包括值和指向左右节点的引用（利用孩子兄弟表示法）

public class BinarySearchTree {//首先这棵树是由若干个结点组成的static class TreeNode {public int val;public TreeNode left;public TreeNode right;//提供构造方法进行初始化public TreeNode(int val) {this.val = val;}}//根节点public TreeNode root;
}

2.search 搜索或查找

若根节点不为空：
如果 查找key == 根节点的值 返回true
如果 查找key > 根节点的值 在其右子树查找
如果 查找key < 根节点的值 在其左子树查找

/*** search 搜索的意思** @param val* @return*/public boolean search(int val) {TreeNode cur = root;while (cur != null) {if (val > cur.val) {cur = cur.right;} else if (val < cur.val) {cur = cur.right;} else {return true;}}return false;}

算法从根节点开始，根据当前节点的值与 val 的大小关系，决定是向左子树还是向右子树移动，直到找到匹配的节点或者搜索到空节点为止。因为每一步都是根据节点值的大小进行移动，而树的高度（树的深度）是 log(n) 级别的（其中 n 是树中节点的数量），所以在平均情况下，search 方法的时间复杂度是 O(log n)。

3.insert 插入

如果该树为空树，即 根节点 == null 直接实例化一个结点，进行插入

如果树不是空树，按照查找逻辑确定插入位置，插入新的节点

public void insert(int val) {//判断是否是空树if (root == null) {root = new TreeNode(val);return;}//定义一个前驱结点TreeNode parent = null;//定义一个临时节点TreeNode cur = root;while (cur != null) {if (val > cur.val) {parent = cur;cur = cur.right;} else if (val < cur.val) {parent = cur;cur = cur.left;} else {return;}}//插入的这个结点TreeNode node = new TreeNode(val);if (val > parent.val) {parent.right = node;}if (val < parent.val) {parent.left = node;}
}

这个方法用于向二叉搜索树中插入一个新的节点，如果节点已经存在则不插入。插入操作首先需要找到要插入位置的父节点，然后根据 val 的大小决定是插入为左子节点还是右子节点。与 search 方法类似，插入操作的时间复杂度也取决于树的高度。在平均情况下，插入一个节点的时间复杂度也是 O(log n)。

4.删除（难点）

设待删除结点为cur，待删除节点的双亲结点为parent

4.1 根结点的左子树为空

cur.left == null

• cur 是 root，则 root == cur.right

• cur 不是 root ，cur 是 parent.left，则 parent.left = cur.right

• cur 不是 root ，cur 是 parent.right，则 parent.right = cur.right

4.2 根结点的右子树为空

cur.right == null

• cur 是 root，则 root = cur.left

• cur 不是 root ，cur 是 parent.left，则 parent.left = cur.left

• cur 不是 root ，cur 是 parent.right，则 parent.right = cur.left

4.3 根结点的左右子树都不为空

cur.left != null && cur.right != null

需要使用替换法进行删除，即在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被 删除节点中，再来处理该结点的删除问题

• 删除结点的左树的最大值，替换当前删除的结点（一定没有左子树）
• 删除结点的右树的最小值，替换当前删除的结点（一定没有右子树）

【情况一】

【情况二】

4.4 完整代码

/*** 删除这个结点* 利用替换的思路** @param val*/public void remove(int val) {//首先需要查找该树有没有该值TreeNode cur = root;TreeNode parent = null;while (cur != null) {if (val > cur.val) {parent = cur;cur = cur.right;} else if (val < cur.val) {parent = cur;cur = cur.left;} else {//如果等于的话，说明该树有该值removeNode(parent, cur);return;}}}//进行覆盖的方法，删除结点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 t = cur.right;TreeNode tp = cur;while (t.left != null) {tp = t;t = t.left;}cur.val = t.val;if (tp.left == t) {tp.left = t.right;} else {tp.right = t.right;}}}

---

5.性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度 的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

最优情况下，二叉搜索树为完全二叉树，其平均比较次数为： log2N 最差情况下，二叉搜索树退化为单支树，其平均比较次数为：

问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，都可以 是二叉搜索树的性能最佳？

二、1.7 和 java 类集的关系

TreeMap 和 TreeSet 即 java 中利用搜索树实现的 Map 和 Set；实际上用的是红黑树，而红黑树是一棵近似平衡的 二叉搜索树，即在二叉搜索树的基础之上 + 颜色以及红黑树性质验证，关于红黑树的内容后序再进行介绍

三、搜索

1.概念及场景

Map和set是一种专门用来进行搜索的容器或者数据结构，其搜索的效率与其具体的实例化子类有关。以前常见的 搜索方式有：

1. 直接遍历，时间复杂度为O(N)，元素如果比较多效率会非常慢
2. 二分查找，时间复杂度为o(log N) ,但搜索前必须要求序列是有序的

上述排序比较适合静态类型的查找，即一般不会对区间进行插入和删除操作了，而现实中的查找比如：

1. 根据姓名查询考试成绩
2. 通讯录，即根据姓名查询联系方式
3. 不重复集合，即需要先搜索关键字是否已经在集合中

可能在查找时进行一些插入和删除的操作，即动态查找，那上述两种方式就不太适合了，本节介绍的Map和Set是 一种适合动态查找的集合容器。

2.模型

一般把搜索的数据称为关键字（Key），和关键字对应的称为值（Value），将其称之为Key-value的键值对，所以 模型会有两种：

纯 key 模型，比如：

• 有一个英文词典，快速查找一个单词是否在词典中 。
• 快速查找某个名字在不在通讯录中

Key-Value 模型，比如：

• 统计文件中每个单词出现的次数，统计结果是每个单词都有与其对应的次数： <单词，单词出现的次数> 。
• 梁山好汉的江湖绰号：每个好汉都有自己的江湖绰号

而Map中存储的就是key-value的键值对， Set中只存储了Key。

---