专栏首页图雀社区前端学习数据结构与算法系列(四):哈希、堆和二叉查找树

前端学习数据结构与算法系列(四):哈希、堆和二叉查找树

本文由图雀社区认证作者 神奇的程序员 写作而成,图雀社区将连载其前端学习数据结构与算法系列,点击阅读原文查看作者的掘金链接,感谢作者的优质输出,让我们的技术世界变得更加美好?

哈希的概念

哈希是由键 (key) 和值 (value) 组成的数据。

存储数据

例如,将图中所示数据,存储到哈希表中:

  1. 准备数组:声明长度为5的数组:
  1. 尝试把Joe存进去:
  1. 使用哈希函数 (Hash) 计算 Joe 的值,即字符串 "Joe" 的哈希值。得到的结果是 4928:
  1. 将得到的哈希值处以数组的长度 5,求得其余数。这样的操作叫 "mod运算"。此处mod的运算结果为 3:
  1. 将 Joe 进行 mod 运算的值作为数组下标,放进数组里:
  1. 重复上述步骤,即可往哈希表中添加数据、

存储冲突

当元素进行 mod 运算后,可能会与其他元素的 mod 值一样,此时数组中已经有其他元素占了这个下标位置,这种存储位置重复了的情况便叫做 冲突,我们来看个例子:

使用链表解决冲突问题

遇到存储冲突问题时,可使用 链表[1] 在已有数据的后面继续存储新的数据,也称之为链地址法

例如,Nell 的 mod 结果为1,此时下标为1的地址中已经有了Sue元素,此时使用链表在Sue后面添加Nell即可。

查询数据

将要查询的key使用哈希函数计算出哈希值,进行mod运算,得出的结果即当前要查询key在数组[2]中的的下标,通过下标访问即可获取存储的元素,取出对应的值。

例如要查询Dan的值

  1. 对Dan进行mod运算得出值为4,则得之Dan在数组的下标是4
  1. 取出Dan对应的value值为M

数组中的链表数据查询

将需要查找的key进行mod运算,得到结果后,发现对应下标下的key不一致,然后对不一致的key的链表进行线性查找,得出查找的key,取出value值。

例如,需要查询Ally键对应的value值:

  1. 求出Ally的哈希值,对哈希值进行mod运算,得出值为3:
  1. 对下标为3元素的连败哦进行线性查找,找到Ally元素:

哈希表的优点

在哈希表中,可以利用哈希函数快速访问到数组中的目标元素。如果发生哈希冲突,就是用链表进行存储。这样一来,不管数据量多少,我们都能够灵活应对。

哈希表的缺点

如果数组空间太小,使用哈希表的时候很容易发生冲突,线性查找的使用频率也会更高,反过来,如果数组的空间太大,就会造成内存的浪费。因此,使用哈希表时,数组空间大小的指定非常重要。

更多解决冲突的方法

开放地址法

这种方法是指当冲突发生时,立刻计算出一个候补地址(数组上的位置)并将数据存去。如果仍然有冲突,便继续计算下一个候补地址,直到有空地址为止。可以通 过多次使用哈希函数或 “线性探测法” 等方法计算候补地址。

堆的概念

堆是一种图的数据结构,被用于实现“优先队列”。

优先队列是一种数据结构,可以自由添加数据,但取出数据时要从最小值开始按顺序取出。在堆的树形结构中,各个顶点被称为“结点(node)”,数据就存储在这些节点中。

堆的特点

如下图所示,每个节点由两个子节点,用线条连接即为堆:

  1. 结点内的数字就是存储的数据
  2. 堆中的每个结点最多有两个子节点
  3. 树的形状取决于数据的个数
  4. 节点的排列顺序为从上到下,同一行里则为从左到右
  5. 堆的父节点必须小于子结点

堆的数据存储

在堆中存储数据时必须遵守这样一条规则:子结点必定大于父节点

  1. 顶端的结点为根节点存储的数据为堆中的最小值
  2. 新数据增加时会被放在堆的最底部靠左的位置
  3. 堆的底部没有多余空间时,会另起一行把数据加在这一行的最左端

例如,将数字5添加到堆中:

  1. 结点6有个空位置,将数字5加在结点6中
  1. 数字5结点的父结点大于本身,故调换位置
  1. 交换完毕后数字5结点的父节点小于本身,所以不再交换,往堆中插入数据5的操作结束

堆的数据获取

从堆中获取数据时,需要从最上面的数据开始取,取完数据后,堆需要进行重新排序,将最后的数据移到取出的结点位置。

如图所示,取出堆中的数字1:

  1. 1被取出后,结构需要重新调整
  1. 将最后的数字6结点移到最顶部
  1. 如果子结点的数字小于父节点,就将父节点与其左右两个子节点中较小的一个进行交换
  1. 数字6结点的子结点3和5,3为较小者。故与3进行位置调换
  1. 交换后,数字6结点的两个子节点4和8,4为较小者。故与4进行位置交换
  1. 交换后,数字6结点无子节点。故交换完毕,从堆中取出数据的操作完成

二叉查找树的概念

二叉查找树是一种数据结构,采用了图的树形结构,数据存储于二叉查找树的各个结点中。

二叉查找树又叫 二叉搜索树二叉排序树

如图所示,即为一个二叉查找树的示例:

二叉查找树的特点

  1. 同堆一样,每个节点最多有两个子结点
  2. 每个结点的值均大于其左子树上任意一个结点的值
  3. 每个结点的值均小于其右子树上任意一个结点的值
  4. 查询二叉树中最小值要从顶端开始找他的左子树
  5. 查询二叉树中最大值要从顶端开始找他的右子树

添加数据

  1. 首先从二叉查找树的顶端结点开始寻找数字的位置
  2. 将想要添加的结点的值与该结点的值进行比较
  3. 若要添加的结点值小于当前结点值则往左移否则右移
  4. 左移或右移后与其子结点继续比较,重复步骤3进行判断左移还是右移
  5. 当判断至当前结点的子结点不存在则数据插入完毕

示例1

将数字1插入一个二查找树中:

  1. 将插入的数据与树的顶端结点进行比较,1<15数据左移
  1. 左移后,与15的子结点9进行比较,1<9数据左移
  1. 左移后,与9的子结点3进行比较,1<3数据左移,由于3没有子结点了,所以将1作为新结点添加到左下方
  1. 至此,1的添加操作就完成了

示例2

将数字4插入一个二叉查找树中。

  1. 与示例1步骤一样,与二叉树顶端的结点进行比较,由于4<15,数据左移
  1. 将插入的结点与15的子结点9进行比价,4<9,数据左移
  1. 将插入的结点与9的子结点3进行比较,4>3,数据右移
  1. 将插入的结点与3的子结点8进行比较,4>8,数据左移,8没有子结点,所以将4作为新结点添加到左下方
  1. 至此,4的添加操作完成

删除数据

  1. 删除结点时,判断要删除的结点是否有子结点,若子结点不存在则直接删除
  2. 若要删除的结点只有一个子结点,则先删除目标结点,然后将子结点移到被删除结点的位置上即可
  3. 若删除的结点有多个子结点,则先删除目标结点,然后在被删除结点的左子树中寻找最大结点,最后将最大结点移到被删除结点的位置上,若要移动的结点还有子结点,则递归前面的操作。
  4. 存在多个子结点时,也可在被删除结点的右子树中寻找最小结点,将其移至被删除结点的位置。

示例1

删除数字28的结点

  1. 先判断28所在结点是否有子结点
  2. 28结点无子结点直接删除

示例2

删除结点8

  1. 结点8有一个子结点,则先删除目标结点8
  1. 移动目标结点的子结点4移到被删除结点的位置上

示例3

删除结点9

  1. 删除目标结点
  1. 在被删除结点的左子树中寻找最大结点
  1. 找到最大结点为4,将其移至被删除结点的位置

查询数据

  1. 首先,从二叉树的顶端结点开始往下查找。
  2. 与添加数据时一样,将要查找的结点和树中的结点进行比较,小于该结点则往左移,否则往右移

示例

查找树中的结点12

  1. 从二叉查找树的顶端结点开始往下查找,将要查询的结点12与顶端的结点15进行比较,12<15,数据左移
  1. 左移后,将要查询的结点12与结点15的子结点4进行比较,5<12,数据右移
  1. 右移后,找到结点12,查询结束

写在最后

* 文中使用的图片源自《我的第一本算法书》,如若侵权,请联系图雀社区公众号小编,作者立即删除相关图片。

本文分享自微信公众号 - 图雀社区(tuture-dev),作者:神奇的程序员

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-04-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 全栈“食”代:用 Django + Nuxt 实现美食分享网站(一)

    Django 作为 Python 社区最受欢迎的 Web 框架之一,凭借其高度抽象的组件和强大方便的脚手架,将快速且流畅的开发体验演绎到了极致。而 Nuxt 作...

    一只图雀
  • uni-app 结合云函数开发小程序博客(二):云函数实现登录注册

    不好意思大家,个人原因拖了一周时间才发表第二篇,没想到还有朋友在支持,非常感谢和抱歉。第一篇中已经引入了第三方样式,实现了主题和语言的切换;本篇主要开始页面的搭...

    一只图雀
  • Taro 小程序开发大型实战(四):使用 Hooks 版的 Redux 实现应用状态管理(上篇)

    •熟悉的 React,熟悉的 Hooks[1]:我们用 React 和 Hooks 实现了一个非常简单的添加帖子的原型•多页面跳转和 Taro UI 组件库[2...

    一只图雀
  • 30 张图带你彻底理解红黑树

    小吴正在写红黑树的相关系列文章,不过内容太多,动画做起来比较慢,大家可以先看一下这篇红黑树的介绍,内容很不错。

    五分钟学算法
  • 漫画:什么是AVL树?(修订版)

    对于AVL树的每一个结点,平衡因子是它的左子树高度和右子树高度的差值。只有当二叉树所有结点的平衡因子都是-1, 0, 1这三个值的时候,这颗二叉树才是一颗合格的...

    小灰
  • 红黑树(一):构建红黑树

    前两篇文章谈了B-Tree和B+Tree,它们属于多路平衡树,所有叶子结点都在同一层,除了这两种平衡树, 我们熟知的还有平衡二叉树和红黑树。这一篇文章就来看看如...

    每天学Java
  • 漫画:什么是红黑树?(下篇)

    上周,我们初步介绍了红黑树存在的意义,以及红黑树的插入操作,没看过的小伙伴可以点击下面链接:

    小灰
  • 漫画:什么是红黑树?

    2017年,小灰曾经发布过一篇关于红黑树的漫画,当时由于时间仓促,部分知识点一带而过,并没有讲解得很细致全面。

    小灰
  • Python数据结构__树

        有且只有一个特殊元素根,剩余元素都可以划分为m个不相交的集合T1、T2、T3...Tm,

    py3study
  • 17张图带你解析红黑树的原理!保证你能看懂!

    由于红黑树本质上就是一棵二叉查找树,所以在了解红黑树之前,咱们先来看下二叉查找树。

    程序员追风

扫码关注云+社区

领取腾讯云代金券