二叉搜索树

二叉搜索树也叫二叉排序树，具有以下性质：

• 若它的左子树不为空，则左子树的所有结点的值都小于根结点的值。
• 若它的右子树不为空，则右子树的所有结点的值都大于根结点的值。
• 左右子树都是二叉搜索树。

例如：

二叉搜索树—查找

二叉搜索树和普通二叉树的结构都一样，只是结点的值不太一样。

//二叉搜索树结构
static class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int val) {this.val = val;}
}public TreeNode root = null;

如何在二叉搜索树中查找某一结点值？我们可以根据二叉搜索树的性质，如果要查找的值大于根结点的值就继续往右边查找，如果要查找的值小于根结点的值就继续往左边查找。

查找代码：

public TreeNode find(int val) {TreeNode cur = root;while (cur != null) {//大于往右边if (val > cur.val) {cur = cur.right;} else if (val < cur.val) {//小于往左边cur = cur.left;} elsereturn cur;}return null;
}

二叉搜索树—插入

插入代码：

public boolean insert(int val) {TreeNode node = new TreeNode(val);//空树if (root == null) {root = node;return true;}TreeNode cur = root;TreeNode parent = null;while (cur != null) {if (val == cur.val) {return false;} else if (val < cur.val) {parent = cur;cur = cur.left;} else {parent = cur;cur = cur.right;}}//cur为空了，小于放左边，大于放右边if (val < parent.val) {parent.left = node;} else {parent.right = node;}return true;
}

二叉搜索树—删除

假设待删除结点为 cur，待删除结点的双亲结点为 parent，那么有下面几种情况：

1. cur.left 为空
   

2. cur.right 为空
   

3. cur.left 不为空 并且 cur.right 不为空
   

删除代码：

public void remove(int val) {TreeNode cur = root;TreeNode parent = null;//循环遍历找到要删除的结点while (cur != null) {if (cur.val == val) {//找到后，判断当前节点的情况removeNode(parent, cur);return;} else if (cur.val < val) {parent = cur;cur = cur.right;} else {parent = cur;cur = cur.left;}}
}//根据结点情况删除结点
private void removeNode(TreeNode parent, TreeNode cur) {//待删除结点的左为空if (cur.left == null){if (cur == root){root = cur.right;}else if (parent.left == cur){parent.left = cur.right;}else {parent.right = cur.right;}//待删除结点的右为空}else if (cur.right == null){if (cur == root){root = cur.left;}else if (parent.left == cur){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;}//将最小结点值替换待删除结点cur.val = target.val;//判断最小结点是左孩子还是有孩子if (target == targetParent.left){targetParent.left = target.right;}else {targetParent.right = target.right;}}
}

Map和Set

map 和 set 是一种专门用来进行搜索的容器或者数据结构，属于动态查找，也就是在查找时可以进行插入和删除操作。

一般把搜索的数据称为关键字(Key)，和 Key 对应的称为值(Value)，将其称为 Key-value 的键值对。分为以下两种：

1. 纯 key 模型（Set）： 例如：某单词是否在一句话中。
2. Key-Value 模型（Map）： 例如：某单词出现的次数 <单词，出现次数>。

Map的使用

put(K key, V value)，设置 key 对应的 value

使用 put 方法时，插入的 key 一定不能是 null，否则会空指针异常，但是 value 可以。

插入的 key 一定是可以比较的，否则会报错。

如果 key 相同，则会替换原来的 value。

get(Object key) 返回 key 对应的 value
getOrDefault(Object key, V defaultValue) 返回 key 对应的 value，key 不存在，返回默认值

remove(Object key) 删除 key 对应的映射关系

Set<K> keySet() 返回所有 key 的不重复集合
Collection<V> values() 返回所有 value 的可重复集合

Set<Map.Entry<K, V>> entrySet() 返回所有的 key-value 映射关系

containsKey(Object key) 判断是否包含 key
containsValue(Object value) 判断是否包含 value

Set的使用

哈希表

通过某种函数使元素的存储位置与它的关键码之间建立映射关系的一种存储结构叫做哈希表(散列表)。

插入元素： 根据待插入元素的关键码，使用函数计算出该元素的存储位置并按此位置进行存放。
搜索元素： 对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。

例如：

哈希冲突

假设现在要插入 23，就会出现冲突：

不同关键字通过相同的哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

注意： 哈希表底层数组的容量往往小于实际要存储的数量，这就导致一个问题，冲突的发生是必然的，我们只能尽量的低冲突。

---

冲突避免

设计合理的哈希函数可以减小冲突的概率。哈希函数设计原则：

• 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有 m 个地址时，其值域必须在 0 到 m-1 之间。
• 哈希函数计算出来的地址能均匀分布在整个空间中。
• 哈希函数应该比较简单。

常见哈希函数：

1. 直接定制法
   取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
   优点：简单、均匀
   缺点：需要事先知道关键字的分布情况
   使用场景：适合查找比较小且连续的情况

2. 除留余数法
   设散列表中允许的地址数为 m，取一个不大于 m，但最接近或者等于 m 的质数 p 作为除数，按照哈希函数：Hash(key) = key% p(p<=m)，将关键码转换成哈希地址。

还有几个不常用的：平方取中法、折叠法、随机数法、数学分析法。

---

负载因子调节： α(负载因子) = 元素个数 / 表的长度
负载因子越大，产生冲突的可能性就越大，所以要想减小负载因子，就要增大表的长度(扩容)。

---

冲突解决

解决哈希冲突两种常见的方法是：闭散列和开散列。

冲突解决—闭散列

闭散列： 也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把 key 存放到冲突位置中的 “下一个” 空位置中去。

寻找下一个空位置：

1. 线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
   
   如果再插入 33，那几个数据就会在一块，那就需要其他方法解决这个问题。

2. 二次探测：
   线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：H$i$= ( H$0$+$i$²)% m，i 等于1，2，3……。

冲突解决—开散列

开散列法又叫链地址法(开链法)，同样先计算出散列地址，把相同地址的关键码放于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。类似下面这种：

开散列中每个桶中放的都是发生哈希冲突的元素，开散列就是把一个在大集合中的搜索问题转化为在小集合中做搜索了。我们还可以继续优化在小集合中搜索，例如：每个桶的背后是另一个哈希表或者每个桶的背后是一棵搜索树。

---

题目练习

只出现一次的数

题目链接：【leetcode】136. 只出现一次的数字
题目描述：

这题我们利用 set 的性质来做，使用异或（将数组里的元素全部异或，最后结果就是只出现一次的数字）或者 map（统计每个元素出现的次数，value 为1的就是只出现一次的数字）也可以。

代码：

class Solution {public int singleNumber(int[] nums) {Set<Integer> set = new HashSet<>();for(int x : nums){//利用add函数的返回值，返回false，//说明set中已经存在这个元素，那我们就移除if(!set.add(x)){set.remove(x);}}//最后 set 中就剩下只出现一次的数字for (Integer x : set) {return x;}return -1;}
}

复制带随机指针的链表

题目链接：【leetcode】138. 复制带随机指针的链表
题目描述：

题目的意思就是，我们需要根据题目给的链表，生成同等个数并且结点的 val 相等，所给链表的 next 和 random 域指向链表中的哪个结点，我们就需要在自己生成的链表中指向位置相对应的结点。

为了达到题目要求，我们可以使用 map 来存储他们对应位置的结点。

代码：

public Node copyRandomList(Node head) {Map<Node, Node> map = new HashMap<>();Node cur = head;//遍历链表while (cur != null) {//生成和题目的链表节点 相同值 的结点Node node = new Node(cur.val);//再把题目中链表的结点  和  生成的新结点存储到 map中map.put(cur, node);cur = cur.next;}//再次指向题目链表的头结点cur = head;while (cur != null) {//获取对应位置关系的结点map.get(cur).next = map.get(cur.next);map.get(cur).random = map.get(cur.random);cur = cur.next;}//新链表的头结点对应老链表头结点的valuereturn map.get(head);
}

宝石与石头

题目链接：【leetcode】771. 宝石与石头
题目描述：

我们可以把宝石都放到 set 中，然后遍历石头，如果 set 中有这个元素，那就是宝石，否则就不是。

代码：

class Solution {public int numJewelsInStones(String jewels, String stones) {Set<Character> set = new HashSet<>();//先把宝石加到 set中for (int i = 0; i < jewels.length(); i++) {set.add(jewels.charAt(i));               }int count = 0;//遍历石头，如果 set中包含，就是宝石for (int i = 0; i < stones.length(); i++) {if (set.contains(stones.charAt(i))) {count++;}}return count;}
}

旧键盘

题目链接：【牛客网】旧键盘
题目描述：

和上题类似，我们把坏键(_hs_s_a_es) 输出的字符串添加到 set 中，在遍历好键(7_This_is_a_test) 输出的字符串，如果没有哪个字符，那个键就是坏的，也就是我们要输出的。

代码：

public static void func(String str1,String str2) {Set<Character> set = new HashSet<>();//把坏键先转成大写，然后存储到 set中for (char c : str2.toUpperCase().toCharArray()) {set.add(c);}Set<Character> res = new HashSet<>();//遍历好键，把不存在的添加到 res中for (char c : str1.toUpperCase().toCharArray()) {//!res.contains(c) 避免重复输出 if (!set.contains(c) && !res.contains(c)) {res.add(c);System.out.print(c);}}
}