---

二叉搜索树

（1） 二叉搜索树的概念：

二叉搜索树是一颗特殊的二叉树，（在其不为空的情况下，意为可以是空树）
特性：其根节点的值比左子树中每一个节点的值都大，比其右子树中每一个节点的值都小。并且对于其左右子树而言亦满足此规则，即所有节点的值比其左子树的值都大，比其右子树的值都小。

在二叉搜索树中所有的节点均是特殊的，不存在值相同的情况。

（2）二叉搜索树的意义：

查找有两种： 静态查找与动态查找
在静态查找中，有两种：
顺序查找，时间复杂度为O(N), 二分查找，时间复杂度为O(logN)(以2为底)
二分查找的效率较快，但必须在数据有序或逆序的情况下才可以使用。
如果我们隐约将数据与所在位置构建一种映射关系，则不会局限于这堆数据是否有序，且查询搜索效率会大大加快，二叉搜索树即是对这样一种思想的实现（在二叉搜索树中的存放位置与数据大小有关）。

（3）二叉搜索树的实现：

二叉搜索树主要实现三种操作：查找，插入，删除。
我们阐述这几种操作的思想，并辅以编码实现。

实现的方法与属性

public class BinarySearchTree {//实现节点的内部类static class TreeNode {int val;TreeNode left;TreeNode right;public TreeNode(int val) {this.val = val;}}      TreeNode root;   //创建二叉树根节点//关于二叉搜索树的查询方法：public TreeNode search(TreeNode root, int val){}// 关于二叉搜索树的插入方法：public void insert(int val){}//关于二叉搜索树的删除方法：public void remove(int val){};
}

实现二叉搜索树的查询：

时间复杂度：最优情况下：是完全二叉树，时间复杂度为O(logN)(以2为底)
最差情况下：是单分支树：时间复杂度为：O(N).

当

  public TreeNode search(int val) {//在类中的方法，可以直接引用类中的字段属性//root.val = 10;//遍历整个二叉树TreeNode cur = root;while (cur != null) {if (cur.val == val) {return root;} else if (cur.val > val) {//如果根节点值比要查找的值大，则往左子树上寻找cur = cur.left;} else {cur = cur.right;}}return null;}

我们也可以采用递归来实现：
因为递归同遍历一样，也最终执行出一条路径，找到其对应的位置。
不过递归的空间复杂度较高，不推荐。

实现二叉搜索树的插入：

功能：插入方法用于向二叉搜索树中插入元素，或不断地插入元素来创建二叉搜索树。
思想：（1）：在二叉搜索树中插入一个值，最终此值要插入的位置一定是叶子节点。
（2）：我们需要一个cur节点来指向在遍历路径中的每一个节点，当cur遇到空节点时，则将需要插入的结点赋给cur，此时我们需要一个parent节点，指向cur的前一个节点。
（3）：当需要插入时，还需要判断要插入的节点是在parent的左子树上，还是右子树上，将插入的值与parent的值比较即可得出。

  public void insert(int val){TreeNode node  = new TreeNode(val);if(root==null){root = node;return ;}TreeNode cur = root;//设置一个父亲节点TreeNode parent = null;//如果根节点的值比要插入的值大，则将此值插入到左子树上去。while (cur!=null) {if (cur.val > val) {parent = cur;cur = cur.left;} else if(cur.val>val)    {//如果根节点值比要插入的值小，则将此值插入到右子树上去.parent = cur;cur = cur.right;}else {//如果要插入的值在二叉搜索树中已经存在，直接返回return;}}//当cur为空时：需要判断新的节点是插在父母节点的左子树上，还是右子树上if(val>parent.val) {parent.right = node;}else {parent.left = node;}}

实现二叉搜索树的删除：

实现思想：

 public void remove(int val){//要删除一个节点，//此节点有三种情况，左子树为空，右子树为空，左右子树均不为空，还有一个特殊情况，左右节点均为空，只有一个根节点if(root==null){return ;}//需要先找到此节点的位置TreeNode cur  = root;TreeNode parent = null;while (cur !=null) {//如果当前cur指向的值即要删除的值if (cur.val == val) {//调用删除函数delete(cur,parent);} else if(cur.val>val) {//如果根节点的值小，则访问右子树parent = cur;cur =cur.right;}else{parent = cur;cur = cur.left;}}}private void delete(TreeNode cur,TreeNode parent) {//当要删除的节点为左树为空时，三种情况：if(cur.left ==null){//先判断此节点是否为根节点，如果是根节点if(cur == root){root = root.right;}else if(cur==parent.left)  {//如果当前节点不是根节点,有两种情况，当前节点是父亲节点的左子树parent.left = cur.right;}else if(cur ==parent.right){//如果当前节点是父亲节点右子树parent.right = cur.right;}}else if(cur.right == null){//先判断此节点是否为根节点，如果是根节点if(cur == root){root = root.left;}else if(cur==parent.left)  {//如果当前节点不是根节点,有两种情况，当前节点是父亲节点的左子树parent.left = cur.left;}else if(cur ==parent.right){//如果当前节点是父亲节点右子树parent.right = cur.left;}}else {//当左右子树均不为空时//采用替换删除法：//找到当前节点左子树的最左节点或者当前节点右子树的最右节点TreeNode cur2 = cur.left;//当左子树只有一个节点呢？TreeNode parent2 = cur;while (cur2.right!=null){parent2 = cur2;cur2 = cur2.right;}//用最左节点的值覆盖掉cur节点的值cur.val = cur2.val;//如果左子树中除去左子树根节点外，其右边没有数据了，//那么parent2.left = cur2啊。if(parent2.right == cur2){parent2.right = cur2.left;}else {parent2.left = cur2.left;}}}

Map与Set

关于Map与Set的概念

Map与Set是用来搜索的容器或数据结构，我们在之前讲过，查询有静态查询与动态查询，动态查询是指在查询过程中，可能会进行一些插入与删除的操作，而Map与Set即是适合动态查找的容器。

模型的概念

在存储容器中，存储的数据模型有两种：纯Key模型与Key—Value模型
纯Key模型： 例如我们在字典中查询一个单词，看这个单词是否在字典中，字典中只是单纯地存储了这个单词并无别的数据。

Key—Value模型：例如，我们要统计一篇文章中每个单词出现的次数，则我们要存储的数据除去单词本身外，还要存储这个单词出现的次数，形式化为：<单词 , 单词出现的次数>。
在Map中存储的即是Key—Value值，而在Set中只存储Key.

Map与Set在java框架中的位置：

Map并没有继承Collection类，

Map中常用的方法：

Set中常用的方法：

HashMap源码的学习（重点掌握！！！）：

关于类属性的学习：

关于类构造方法的学习：

注： 我们在上面的四个构造方法中，并没有发现给table数组分配内存的操作，所以给table数组并不在构造方法中，实际上是在put方法中，我们再分析一下put方法。
关于put方法的学习：

下面这张图片接上面的（树化的函数）：

关于自主学习get方法：

哈希表（散列表）

什么是哈希表（散列表）？

哈希表是一种数据结构，其实现思想是基于通过数据的关键码与所存地址两者之间构建映射关系，能够一次直接从表中得到想要搜索的元素。

数据的关键码与所存地址之间的关系由哈希函数实现，规则为：设定适合的哈希函数之后，输入的关键码通过哈希函数的计算得出所存的地址。由此构造出来的结构称为哈希表。

哈希表相对于二叉搜索树以及其他查询方式，不需要与多个关键码比较，这极大提升了查询的效率

哈希冲突及如何减少冲突率：

当两个不同的关键码通过哈希函数计算得出的哈希地址相同时，此时的情况称为哈希冲突。
哈希冲突如何尽量避免？
首先需要声明的是：哈希表底层数组的容量往往小于需要存储的全部关键码的容量，所以冲突是不可避免的，只能尽量减少冲突率

**

（1）设置合理的哈希函数

**：哈希冲突过大可能是因为哈希函数有问题：哈希函数的设定原则为:

1. 哈希函数的定义域必须包括全部的关键码。
2. 哈希函数计算出的地址能够均匀地分布在地址空间之中。
3. 哈希函数应该比较简单。

哈希函数的几种设计方法：（这里只介绍两种，我们在用哈希函数时，一般不需要自己设计，而是采用java提供给我们的哈希函数）

1. 直接定制法–(常用)
   取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀 缺点：需要事先知道关
   键字的分布情况 使用场景：适合查找比较小且连续的情况 面试题：字符串中第一个只出现一次字符
2. 除留余数法–(常用)
   设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：
   Hash(key) = key% p(p<=m),将关键码转换成哈希地址

（2） 调节负载因子

负载因子概念：所谓负载因子是指: a = 哈希底层数组中的元素个数 / 数组容量大小，
负载因子与冲突率的关系如下：

所以想要降低冲突率就要降低负载因子，降低负载因子即需要扩展数组容量大小。所以当负载因子超过某一阈值时即应该扩展数组容量。

哈希冲突的解决：

哈希冲突的解决有两种方式：闭散列与开散列。
先学开散列—它比较重要

哈希冲突解决——开散列（哈希桶）（重点掌握）

开散列法又叫作链地址法，首先对关键码集合通过哈希函数计算出其对应的哈希地址，对于具有相同的哈希地址的关键码集合用一个单链表链接起来，称其为桶，单链表的起始地址存放在哈希表中（一般哈希表由数组实现）。
我们用图来形象化表示：

哈希桶可以看作将大集合（整个关键码集合）的搜索方法转化为小集合（链表）的搜索方法，当冲突严重时，即链表长度过长时，可以将小集合搜索问题继续进行转化来更好地解决冲突问题。
例如：1. 在每一个桶后跟一个哈希表。
2 .将每一个桶后转化为搜索树。

哈希桶的模拟实现：

我们哈希桶的实现只实现两种操作，插入与获取关于key的value值

哈希桶实现的方法与属性与内部类：

public class HashBuck {static class Node{//设置key值public int key;//设置val值public int val;public Node next;  //指向下一个节点的指针//赋值的构造方法public Node(int key,int val){this.key = key;this.val = val;}}private Node[] array  = new Node[10];  //默认设置的数组大小为10private int usedsize = 0;             //数组中使用的空间个数private  static  final   double  LoadFACTOR = 0.75; //默认的负载因子//插入数据——key与相应的valpublic void put(int key,int val);//获取数据——获取key相应的val值public int getVal(int key);
}

实现插入操作方法：

 public void put(int key,int val){//在插入数据时，我们先判断此数据在数组中应放在什么位置。int index = key%array.length;//然后遍历此位置的链表，如果链表中没有此节点，则插入，有则更新value值.Node cur = array[index];while (cur !=null){if(cur.key == key){//说明此key值存在。cur.val = val;return;}cur = cur.next;}//当cur为空时，说明插入的key值在链表中并不存在,则进行头插cur = new Node(key,val);cur.next = array[index];array[index] = cur;usedsize++;//之后再判断当前数组负载因子是否已经过大if(isoverload(array,LoadFACTOR)){//如果负载因子超过设定的值，则重新开辟一个数组，并进行后续步骤resize();}}private void resize() {Node []newarray = new Node[2*array.length];//应该遍历所有的链表的节点，重新分配到新的位置上去for (int i = 0; i < array.length; i++) {Node cur = array[i];while (cur!=null){int index  =   cur.key % newarray.length;//在重新获取当前的节点应在的下标后// 将此节点插入到应在的下标处Node curN = cur.next;cur.next = newarray[index];newarray[index] =cur;//cur需要回到原来节点的next节点处cur = curN;}}array = newarray;}//判断当前负载因子是否过大。private boolean isoverload(Node[] array, double loadfactor) {return usedsize%array.length>= loadfactor;}

实现获取对应key的Value的值

实现思想：先找到当前key值所在的下标，然后遍历此链表即这个桶，当找到值时，返回，未找到则指向下一个节点，直到cur为空

 public int getVal(int key){//判断key值是否存在int index = key% array.length;Node cur = array[index];while (cur!=null){if(cur.key==key){return cur.val;}cur = cur.next;}return -1;}

哈希冲突解决—闭散列法（了解即可）

如图：我们要放置44至数组中，但是当前数组下标4已经有数据，如采用闭散列法：
线性探测：
即在逐个遍历数组后面的位置，找到空位，则将44插入空位上。

注：采用闭散列解决哈希冲突时，不能随便删除数据，如下图：如果要删除4，则44则无法再找到
，一般采用伪删除法（比如：采用一个标记置为false，来表示已删除）。

二次探测：在前面所学的线性检测的缺点为产生冲突的数据都聚集在一起，（这导致了
要查找某一关键码时，需要比较多次，导致搜索效率降低）
举例：
如图：当所有产生冲突的数据都聚集在一起时，如果要查询5，则不能够直接从5下标找到，而必须从下标5比较到下标8。
二次检测：即在插入冲突的数据时，不再进行依次找位置插入，而找到下一个空位置的方法为：

（这个了解即可，通常用不到）以此去将相冲突的元素来进行间隔开来。
在进行二次检测后举例：

oj练习：

1.只出现一次的数字

2.复制带随机指针的链表

3.宝石与石头

4.坏键盘打字

5.前k个高频单词