校园二级网站建设,网站制作的订单,上海外贸建站商城,网站首页被降权的原因#x1f48e; 欢迎大家互三#xff1a;2的n次方_ #x1f48e;所属专栏#xff1a;数据结构与算法学习 #x1f341;1. 二叉搜索树
二叉搜索树也称为二叉查找树或二叉排序树#xff0c;是一种特殊的二叉树结构#xff0c;它的特点是#xff1a; 1. 若左树不为空 欢迎大家互三2的n次方_ 所属专栏数据结构与算法学习 1. 二叉搜索树
二叉搜索树也称为二叉查找树或二叉排序树是一种特殊的二叉树结构它的特点是 1. 若左树不为空则左树所有节点的值都小于根节点的值 2. 若右树不为空则右树所有节点的值都小于根节点的值 3. 不存在键值相等的节点 接下来就模拟实现一下二叉搜索树
首先和之前二叉树的实现一样都是一个节点包括值和指向左右节点的引用
public class BinarySearchTree {static class TreeNode {int val;TreeNode left;TreeNode right;public TreeNode(int val) {this.val val;}}
} 之后就是插入删除搜索等一些方法了
1.1 search()
根据二叉搜索树的性质只需要在遍历的时候进行判断目标值在左子树还是在右子树 public TreeNode search(int key) {//从根节点开始往下搜索TreeNode cur root;while (cur ! null) {if (cur.val key) {cur cur.left;} else if (cur.val key) {cur cur.right;} else {return cur;}}return null;}
1.2 insert(int key)
插入也是一样的过程这里定义了两个节点一个用来遍历另一个用来判断最后插入的位置需要注意的是由于二叉搜索树不能有重复节点在遍历的过程中如果发现当前节点和要插入的元素的值相同直接退出方法 public void insert(int key) {if (root null) {root new TreeNode(key);return;}TreeNode parent null;TreeNode cur root;//定义要插入的节点TreeNode node new TreeNode(key);while (cur ! null) {if (cur.val key) {parent cur;cur cur.left;} else if (cur.val key) {parent cur;cur cur.right;} else {return;//不能有重复的值直接返回}}//判断作为左树还是右树if (parent.val key) {parent.left node;} else {parent.right node;}} 1.3 remove(int key)
删除操作是有些麻烦的因为删除节点之后还需要保证是二叉搜索树首先找到要删除的节点找到之后调用删除节点的方法 public void remove(int key) {TreeNode parent null;TreeNode cur root;while (cur ! null) {if (cur.val key) {parent cur;cur cur.left;} else if (cur.val key) {parent cur;cur cur.right;} else {removeNode(parent, cur);}}}
可以分为三种情况
要删除的节点左树为空接着又可以分为三种情况 右树为空同理也可以分为三种情况 左右都不为空
这里采用替换删除的方法找到一个合适的数据替换cur.val这个数据替换之后还要保证二叉搜索树的特性所以就要找左子树的最大值或者右子树的最小值来进行替换
左子树的最大值也就是左树最右边的节点即右树为空
右子树的最小值也就是右树最左边的节点即左树为空
以右子树的最小值为例找到之后替换cur接着删除原来的节点 找到之后还需要判断是右子树或者是左子树因为二者的删除方式是不一样的 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 {//左右都不为空 // t:要交换的目标元素的 tp:要交换的目标元素的双亲节点方便后续删除TreeNode tp cur;TreeNode t cur.right;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;}}} 2. 哈希表
哈希表Hash table也叫散列表是一种根据关键码值Key value而直接进行访问的数据结构。它通过哈希函数也叫散列函数将关键码值映射到表中一个位置来访问记录以加快查找的速度。
哈希表的插入、删除和查找操作的时间复杂度在理想情况下是O(1)比我们之前学过的数据结构都要快
2.1 实现原理
哈希表通过哈希函数将元素的键名映射为数组下标转化后的值叫做哈希值或散列值然后在对应下标位置存储记录值。当我们按照键名查询元素时可以使用同样的哈希函数将键名转化为数组下标从对应的数组下标位置读取数据。
2.2 哈希函数的构造
哈希函数的设计规则 哈希函数的定义域必须包括需要存储的全部关键码 哈希函数计算出来的地址能均匀分布在整个空间中 哈希函数应该简单设计 关于哈希函数的构造介绍一下两种最常用的方法
直接定制法取关键字的某个线性函数为散列地址HashKey A*Key B 优点简单、均匀 缺点需要事先知道关键字的分布情况 使用场景适合查找比较小且连续的情况
除留余数法设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数按照哈希函数 Hash(key) key% p(pm),将关键码转换成哈希地址 2.3 哈希冲突
哈希冲突是指不同的键名通过哈希函数计算后得到相同的哈希值导致它们被映射到散列表中的同一个位置例如下面的4和14通过除留余数的哈希函数映射到了同一个位置 2.3.1 哈希冲突的避免
避免哈希冲突有以下需要注意的 1. 引起哈希冲突的一个原因可能是哈希函数设计的不合理需要设计合理的哈希函数 2. 调节负载因子 哈希表的负载因子用于衡量哈希表的填充程度 其实很好理解填的越满越容易挤
2.3.2 哈希冲突的解决方法
我们有以下几种解决办法
闭散列开放寻址法 线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止 很明显这种方式有一个弊端冲突元素都聚集到了一起这与其找下一个空位置有关系
二次探测当哈希函数计算出的位置已被占用时二次探测通过计算一个二次方递增的步长来探测下一个可能的哈希地址直到找到一个空槽或遍历完整个表。 其中i 1,2,3… H₀是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置m是表的大小。 (4 1^2)%10 , (4 2^2)%10 无论是线性探测还是二次探测都有一个问题空间利用率低就有了下面的一种方法
开散列哈希桶
开散列法又叫做链地址法首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。 HashSet就是采用的链表数组链表的方式存储的并且在特定的情况下会变为红黑树
3. 哈希桶的实现
3.1 创建哈希桶
我们这里根据key-value模型来实现一下哈希桶
public class HashBuck {static class Node {public int key;public int val;public Node next;public Node(int key, int val) {this.key key;this.val val;}}//数组中每一个元素都是一个头结点public Node[] arr new Node[10];public int usedSize;//负载因子private final double DEFAULT_LOAD_FACTOR 0.75;
} 这也和我们之前说的数组链表是一样的,接下来就是其中的一些方法
3.2 push()
首先通过哈希函数计算出要插入的数组下标接着再顺着链表进行判断如果插入元素已经存在需要更新val之后再返回不存在的话就用头插的方法插入 public void push(int key, int val) {//哈希函数int index key % arr.length;//根据哈希函数算出来数组的位置后进行判断Node cur arr[index];while (cur ! null) {//如果要插入元素已经存在更新val后直接返回if (cur.key key) {cur.val val;return;}cur cur.next;}//如果没有找到相同的元素调用头插法插入Node node new Node(key, val);node.next arr[index];arr[index] node;usedSize;//超过负载因子进行扩容if (doLoadFactor() DEFAULT_LOAD_FACTOR) {resize();}} 接下来讲一下扩容的方法 //扩容private void resize() {//重新定义一个扩容之后的数组Node[] newArr new Node[arr.length * 2];for (int i 0; i arr.length; i) {Node cur arr[i];while (cur ! null) {//提前记录cur.next避免之后头插时无法再遍历原来的节点Node curn cur.next;//重新记录扩容后的下标int index cur.key % newArr.length;cur.next newArr[index];newArr[index] cur;cur curn;}}arr newArr;}//计算存储的比例private double doLoadFactor() {return usedSize * 1.0 / arr.length;} 由于采用了数组链表的形式不能简单的进行扩容拷贝这样链表上的元素无法处理这里采用的是定义一个扩容之后的数组接着遍历原数组上链表的每一个元素并重新根据哈希函数进行计算并排列到新的数组中合适的位置
3.3 hashCode()方法
上面我们是先用int类型实现了哈希桶但是如果是其他非数值的类型怎么去根据哈希函数计算地址呢这时就用到了hashCode方法hashCode方法是Java中Object类的一个方法用于返回对象的哈希码可以利用哈希码来进行计算对于同一个对象在其生命周期内只要对象的内容没有发生变化多次调用hashCode方法应该返回相同的值理想情况下hashCode方法应该为每个不同的对象生成不同的哈希码但实际上由于哈希码的值域有限int类型不同的对象可能会生成相同的哈希码称为哈希冲突
class Person{public String name;public Person(String name) {this.name name;}Overridepublic boolean equals(Object o) {if (this o) return true;if (o null || getClass() ! o.getClass()) return false;Person person (Person) o;return Objects.equals(name, person.name);}Overridepublic int hashCode() {return Objects.hash(name);}
}public class Text {public static void main(String[] args) {Person person1 new Person(LiHua);Person person2 new Person(LiHua);//重写hashCode之前两个对象的hashCode值不一样System.out.println(person1.hashCode());System.out.println(person2.hashCode());//在重写equals前这是两个不同的对象重写后为trueSystem.out.println(person1.equals(person2));//两个不一样的对象拥有了相同的哈希值System.out.println(abc.hashCode());//96354System.out.println(acD.hashCode());//96354}
} 不重写的话即使两个对象属性值一样也不是同一个对象哈希值也就不相同 3.4 实现泛型哈希桶 根据hashCode方法就可以实现一个泛型类的哈希桶传入其他类型的值也可以
public class HashBuck2K, V {static class NodeK, V {public K key;public V val;public NodeK, V next;public Node(K key, V val) {this.key key;this.val val;}}public NodeK, V[] arr (NodeK, V[]) new Node[10];public int usedSize;private final double DEFAULT_LOAD_FACTOR 0.75;public void push(K key, V val) {int index key.hashCode() % arr.length;NodeK, V cur arr[index];while (cur ! null) {//如果要插入元素已经存在更新val后直接返回if (cur.key.equals(key)) {//由于是引用数据类型就需要用equals方法判断cur.val val;return;}cur cur.next;}//如果没有找到相同的元素调用头插法插入NodeK, V node new Node(key, val);node.next arr[index];arr[index] node;usedSize;if (doLoadFactor() DEFAULT_LOAD_FACTOR) {resize();}}private void resize() {NodeK, V[] newArr (NodeK, V[]) new Node[arr.length * 2];for (int i 0; i arr.length; i) {NodeK, V cur arr[i];while (cur ! null) {//提前记录cur.next避免之后头插时无法再遍历原来的节点NodeK, V curn cur.next;//重新记录扩容后的下标int index cur.key.hashCode() % newArr.length;cur.next newArr[index];newArr[index] cur;cur curn;}}arr newArr;}private double doLoadFactor() {return usedSize * 1.0 / arr.length;}public V getVal(K key) {int index key.hashCode() % arr.length;NodeK, V cur arr[index];while (cur ! null) {if (cur.key.equals(key)) {return cur.val;}cur cur.next;}return null;}
}需要注意的还有由于传入的值为引用数据类型就不能用比较两个对象的值了这时就需要调用equals方法进行判断
