首页 > 其他分享 >秋招备战——数据结构

秋招备战——数据结构

时间:2023-02-04 12:00:28浏览次数:34  
标签:结点 哈夫曼 模式 备战 算法 二叉树 秋招 数据结构 节点


二叉树

满二叉树,深度为i,总共有pow(2,i) - 1个节点的二叉树称为满二叉树

哈夫曼树:带权路径最短的二叉树称为哈夫曼树或最优二叉树。

终端结点数为n0,度为2的结点数为n2,那么 n0 = n2 + 1

B树

  • 根节点至少有两个子节点
  • 每个节点有M-1个关键字,并且以升序排列
  • 位于M-1和M关键字的子节点的值位于M-1和M关键字对应的Value之间
  • 其他节点至少有M/2个子节点

B+树

B+树是对B树的一种变形树,它与B树的差异在于:

  • 有k个子结点的结点必然有k个关键码
  • 非叶结点仅具有索引作用,跟记录有关的信息均放在叶子结点中。
  • 树的所有叶结点构成一个有序链表,可以按照关键码排序的次序遍历全部记录。

B和B+树的区别在于,B+树的非叶子结点只包含导航信息,不包含实际的值,所有的叶子结点和相连的节点使用链表相连,便于区间查找和遍历。

B+ 树的优点在于:

  • 由于B+树在内部节点上不包含数据信息,因此在内存页中能够存放更多的key。 数据存放的更加紧密,具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。
  • B+树的叶子结点都是相链的,因此对整棵树的遍历只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连,所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻,所以缓存命中性没有B+树好。

但是B树也有优点,其优点在于,由于B树的每一个节点都包含key和value,因此经常访问的元素可能离根节点更近,因此访问也更迅速。下面是B树和B+树的区别图:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2VcLHveD-1662292694681)(en-resource://database/1121:1)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iPpxUSsP-1662292694683)(en-resource://database/1123:1)]

了解了数据结构再看索引,一切都不费解了,只是顺着逻辑推而已。另加两种存储引擎的区别:

  1. MyISAM是非事务安全的,而InnoDB是事务安全的
  2. MyISAM锁的粒度是表级的,而InnoDB支持行级锁
  3. MyISAM支持全文类型索引,而InnoDB不支持全文索引
  4. MyISAM相对简单,效率上要优于InnoDB,小型应用可以考虑使用MyISAM
  5. MyISAM表保存成文件形式,跨平台使用更加方便
  6. MyISAM管理非事务表,提供高速存储和检索以及全文搜索能力,如果在应用中执行大量select操作可选择
  7. InnoDB用于事务处理,具有ACID事务支持等特性,如果在应用中执行大量insert和update操作,可选择。

红黑树

解决二叉查找树的线性查找缺点,红黑树主要包括以下五条性质。

  • 节点不是红色就是黑色
  • 根节点是黑色
  • 叶子节点为黑色
  • 每个红色节点的两个子结点都是黑色。(从每个叶子节点到跟的所有路径上不能有俩个连续的红色节点)
  • 从任意节点到其叶子节点的所有路径都含有相同的黑色节点。

红黑树的插入、删除很可能会破坏红黑树的五条性质,因此需要一些操作来维护红黑树的五条性质不被破坏。主要有三种操作:变色,左旋、右旋。

设计模式

创建型模式共五种: 抽象工厂模式、单例模式、建造者模式、原型模式。

结构型模式共七种: 适配器模式、装饰器模式、代理模式、外观模式、桥接模式、组合模式、享元模式。

行为型模式共十一种: 策略模式、模板方法模式、观察者模式、迭代子模式、责任链模式、命令模式、备忘录模式、状态模式、访问者模式、中介模式、解释器模式。

完全二叉树

编号与满二叉树一致,说明最多是最后一行没有满。

线索二叉树,按照遍历的顺序来找前驱和后驱,前驱看左子树是否为空,后驱看右子树是否为空。

哈夫曼树,先根据最小的两个节点值构造一个根节点,再讲这个根节点放入剩下的节点中,找出最小的两个节点继续构造二叉树,重复以上工作,直至所有节点全部构造完成,规定左子树的边为0,右子树的边为1,得到最终的哈夫曼树。从而得到每个节点的哈夫曼编码。

最小生成树,主要有两种算法,prim算法和kruskal算法,prim算法是每次找出最短的权重边,最后使它联通;kruskal是先找出最短边,然后找比较小的邻接边。

最短路径:迪杰斯特拉(Dijkstra)算法,按路径长度递增的次序产生最短路径的算法。

弗洛伊德算法(Floyd),每次增加一个节点来找最短路径。

拓扑排序:找入度为0的点,找到之后,删除它的所有出度的边,再找一个入度为0的点。

几种排序算法的比较

不稳定排序:快排、堆排序(大根堆、小根堆)、希尔排序(找到两组比较)
稳定:简单排序(插入、冒泡)、归并(相邻两组比较)、基数排序。


标签:结点,哈夫曼,模式,备战,算法,二叉树,秋招,数据结构,节点
From: https://blog.51cto.com/u_15483653/6037102

相关文章

  • 数据结构-小孩出圈问题(约瑟夫环问题)
    假设有m个小孩,数到n的小孩出列,直到全部出去为止。使用环形链表解决约瑟夫环问题。packagecom.linkedlist;publicclassJosephuLinkeslist{publicstaticvoid......
  • 数据结构-基础
    1.什么是数据结构?数据结构是计算机存储、组织数据的方式。数据结构是指数据之间存在一种换种多种特定关系的数据元素的集合。结构包括物理结构和逻辑结构。数据逻辑结构......
  • Redis数据结构
    1.SDSstructsdshdr{//记录buf数组中已使用字节的数量//等于SDS所保存字符串的长度intlen;//记录buf数组中未使用字节的数量intfree;/......
  • 数据结构-单向链表练习
    publicclassSingLinkedList2{publicstaticvoidmain(String[]args){HeroNode2h1=newHeroNode2(1,"宋江","及时雨");HeroNode2h2=......
  • 数据结构-Hash常见操作实践
    数据结构-Hash常见操作实践目录介绍01.什么是哈希算法02.哈希算法的应用03.安全加密的场景04.唯一标识的场景05.数据校验的场景06.散列函数的场景07.Git版本的控......
  • Good Bye 2022: 2023 is NEAR D. Koxia and Game(数据结构,图论,数学)
    题目链接:https://codeforces.com/problemset/problem/1770/D 大致题意:有三个数组,每个数组的长度为n,数组里面的每个数在(1-n)。现在,对于每一位上面的数,Mahiru可以去掉其中......
  • 数据结构-数据模拟队列
    模拟单向队列classArrayQueue{privateintmaxSize;privateintfront;privateintrear;privateint[]arr;publicArrayQueue(intmaxSize......
  • 数据结构-详解优先队列的二叉堆(最大堆)原理、实现和应用-C和Python
    一、堆的基础1.1优先队列和堆优先队列(PriorityQueue):特殊的“队列”,取出元素顺序是按元素优先权(关键字)大小,而非元素进入队列的先后顺序。若采用数组或链表直接实现优......
  • [数据结构] 哈夫曼树
    哈夫曼树哈夫曼树简介给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(HuffmanTree)。哈夫曼......
  • 数据结构——最大堆
    一、堆堆(英语:heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质:堆中某个节点的值总是不大于或不小于其父节点......