网站开发后台需要做什么,河北大名网站建设招聘,天津哪家公司做公司网站,大型大型网站建设目录
二叉搜索树
二叉搜索树的插入
二叉搜索树的查找 二叉搜索树的删除
哈希表
哈希冲突
闭散列
线性探测法
二次探测法
开散列
开散列代码实现#xff1a;
插入元素
删除元素
查找元素 二叉搜索树
先了解以下二叉搜索树是啥#xff0c;概念如下#xff1a…目录
二叉搜索树
二叉搜索树的插入
二叉搜索树的查找 二叉搜索树的删除
哈希表
哈希冲突
闭散列
线性探测法
二次探测法
开散列
开散列代码实现
插入元素
删除元素
查找元素 二叉搜索树
先了解以下二叉搜索树是啥概念如下 二叉搜索树又称二叉排序树它具有以下性质的二叉树或空树: 若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的每颗子树也分别为二叉搜索树 这就是一颗简单的二叉搜索树 二叉搜索树的插入
二叉搜索树的插入非常简单
从根节点开始比较如果大于根节点就遍历右子树小于根节点就遍历左子树对所有的子树都进行如上操作直到遍历到空节点将待插入元素插入此空节点
先创建一个二叉搜索树的类然后创建一个描述节点的内部类
public class BinarySearchTree {//描述节点的内部类public static class TreeNode {public int key;public TreeNode left;public TreeNode right;TreeNode(int key) {this.key key;}}//搜索树的根节点public TreeNode root;}
}
添加一个插入元素的方法注二叉搜索树的插入只会出现在null节点处也就是插入的新节点都会成为搜索书的叶子节点 。
public class BinarySearchTree {public static class TreeNode {public int key;public TreeNode left;public TreeNode right;TreeNode(int key) {this.key key;}}public TreeNode root;/*** 插入一个元素*/public boolean insert(int key) {TreeNode tmp new TreeNode(key);//树如果为空就直接令其成为根节点if (this.root null) {this.root tmp;//插入成功返回truereturn true;}TreeNode privat this.root;TreeNode p1 this.root;//寻找新元素的插入位置while (p1 ! null) {privat p1;if (p1.key key) {p1 p1.left;}else {p1 p1.right;}}//插入新元素if (privat.key key) {privat.left tmp;}else {privat.right tmp;}//插入成功返回truereturn true;}
}
二叉搜索树的查找
在二叉搜索树中查找一个元素分为两步
从根节点开始比较如果大于根节点就遍历右子树小于根节点就遍历左子树对所有的子树都进行如上操作 //查找key是否存在public TreeNode search(int key) {//判断树是否为空为空就直接返回nullif (this.root null){return null;}TreeNode tmp this.root;while (tmp ! null) {if (tmp.key key) {tmp tmp.left;}else if (tmp.key key) {tmp tmp.right;}else {//找到该元素后将其作为返回值返回return tmp;}}//当出循环之后代表没找到该元素返回nullreturn null;} 二叉搜索树的删除
二叉搜索树的删除相比于插入和查找还是比较复杂的因为要保证删除待删除结点之后树依旧是一颗二叉搜索树。
分两种情况
待删除节点只有一颗子树即左子树或者右子树为空
当待删除节点左树为空就令待删除节点的双亲指向其右子树当待删除节点右树为空就令待删除节点的双亲指向其左子树 左右子树都不为空此处我们利用“替罪羊”的删除方法
找到待删除节点的右左子树的最左右端的节点交换两个结点的值删除该节点 //删除key的值public boolean remove(int key) {if (this.root null) {return false;}TreeNode tmp this.root;TreeNode privat tmp;//寻找待删除节点while (tmp ! null) {if (tmp.key key) {privat tmp;tmp tmp.left;}else if (tmp.key key) {privat tmp;tmp tmp.right;}else {break;}}if (tmp null) {return false;}//判断待删除节点是否只有一颗子树if (tmp.left null || tmp.right null) {判断该子树为左右哪颗子树if (tmp.left null) {if (tmp this.root) {this.root tmp.right;}else {if (privat.left tmp) {privat.left tmp.right;}else {privat.right tmp.right;}}}else {if (tmp this.root) {this.root tmp.left;}else {if (privat.left tmp) {privat.left tmp.left;}else {privat.right tmp.left;}}}}else {//待删除节点有两棵子树时//寻找右子树的最左端的节点TreeNode a tmp.right;while(a.left ! null) {privat a;a a.left;}//将右子树的最左端的节点的值赋值给待删除节点tmp.key a.key;//删除右子树的最左端的节点if (privat.left a) {privat.left a.right;}else {privat.right a.right;}}return true;} 哈希表
在顺序结构和平衡树中顺序查找时间复杂度为O(N)平衡树中为树的高度即O()。
而哈希表是一种插入/删除/查找时间复杂度都是O(1)的数据结构它的查询之所以也可以如此之快的的原因就是它在查找时不需要经过任何比较直接一次从表中得到要搜索的元素。
实现这种数据结构的方法就是通过某种函数使元素的存储位置与它的关键码之间能够建立一一对应的映射关系在查找时通过该函数就可以很快找到该元素。而这种数据结构被称作哈希表或散列表这种函数被称为哈希(散列)函数。
设计一个哈希表最关键的一步就是设计哈希函数。
哈希函数的设计有以下要求
哈希函数的定义域必须包括需要存储的全部关键码其值域必须在0到m-1之间散列表允许有m个地址哈希函数计算出来的地址能均匀分布在整个空间中哈希函数应该比较简单
例如将数据集合{176459}存入哈希表 存入的时候将每个元素都带入哈希函数计算出下标然后插入查找时也是同理。
但是此时又出现了一个新问题如果此时要插入元素15 就会发现没地方可以放了而这也是哈希表中经常会发生的问题被称为哈希冲突或哈希碰撞。
冲突的发生是必然的而我们能做的应该是尽量的降低冲突率。
哈希冲突
降低哈希冲突有以下几个方法
采用更优的哈希函数哈希函数设计的越精妙产生哈希冲突的可能性就越低但是无法避免哈希冲突减小负载因子负载因子 填入表中的元素个数 / 表的大小 JDK中负载因子被设置成里0.75也就是增大哈希表的存储地址。
解决哈希冲突的两种常见的方法是闭散列和开散列
闭散列
闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置中的“下一个” 空位置中去。
常见的闭散列有两种
线性探测法
线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。
通过哈希函数获取待插入元素在哈希表中的位置如果该位置中没有元素则直接插入新元素如果该位置中有元素发生哈希冲突使用线性探测找到下一个空位置插入新元素
例如在前面的例子中插入元素14 因为下标为4的地方已经有值了所以就看下一个位置即下标为5的地方此处因为也有值所以继续向后寻找直到出现空位。
线性探测的缺陷产生冲突的数据会堆积在一起这与其找下一个空位置的方式关系因为找空位置的方式就是挨着往后逐个去找。
二次探测法
二次探测法的本质与线性探测法相同它们的区别是当发生哈希冲突时找下一个空位置的方法不同。
二次探测法找空位置的方法为 % m 其中i 1,2,3… H0是通过散列函数对元素的关键码 key 进行计算得到的位置其中m是表的大小。
例如在前面的例子中插入元素14 虽然插入位置和线性探测法相同但是原理不同
先计算得到插入位置H0 4因为4下标处已有值所以带入利用 % m 公式代入i1计算得到的新下标为5但5下标处也有值所以带入i 2计算得到新下标为8插入
但是闭散列还有一个问题如果此时删除元素4那么就找不到元素14了。
开散列
开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。
比如采用开散列的方式存储集合{17645914} 而开散列最重要的是控制负载因子因为当负载因子过大就无法使哈希表的速度达到O(1)。JAVA中的哈希表就是采用的开散列的方式在JDK中负载因子为0.75。
开散列代码实现
散列函数和上面的例子相同
class MyHash{//哈希表中存储元素的节点static class node{public int data;public node next;public node(int data) {this.data data;}}//哈希表,默认大小为10node[] arr new node[10];//数组中的元素个数int size 0;//最大负载因子,默认为0.75double maxLoadNum 0.75;
}
插入元素
加入插入元素的方法注开散列最重要的是控制负载因子因为当负载因子过大就无法使哈希表的速度达到O(1)所以插入元素之后必须进行负载因子的判断 public void insert(int data) {//先利用散列函数计算出插入位置int index data % this.arr.length;//创建节点node tmp new node(data);if (this.arr[index] null) {this.arr[index] tmp;}else {//头插法tmp.next this.arr[index];this.arr[index] tmp;}this.size;//计算负载因子是否过大如果过大就必须进行扩容然后将所有元素重新哈希if (((double)this.size / this.arr.length) this.maxLoadNum) {this.size 0;node[] arr1 new node[this.arr.length * 2];for (int i 0; i this.arr.length; i) {while (this.arr[i] ! null) {int index1 this.arr[i].data % arr1.length;node tmp1 this.arr[i];//在原表中删除该节点this.arr[i] this.arr[i].next;tmp1.next null;//将节点插入新表中if (arr1[index1] null) {arr1[index1] tmp1;}else {//头插法tmp1.next arr1[index1];arr1[index1] tmp1;}this.size;}}//用新表替换原表this.arr arr1;}}
利用该组样例进行简单测试之后插入和扩容均无误。 删除元素 public void remove (int data) {//先利用散列函数计算出插入位置int index data % this.arr.length;node p this.arr[index];if (p null) {return;}if (p.data data) {this.arr[index] p.next;}else {while (p.next ! null){if (p.next.data data) {p.next p.next.next;break;}p p.next;}}}
查找元素 //找到该元素返回该元素的值没找到返回-1public int check(int data) {//先利用散列函数计算出插入位置int index data % this.arr.length;node p this.arr[index];if (p null) {return -1;}while (p ! null){if (p.data data) {return p.data;}p p.next;}return -1;}
