0402 - 数据结构
2021-05-12 23:04:17 0 举报
AI智能生成
系统架构、Java技术栈、面试宝典
作者其他创作
大纲/内容
数据结构
线性表
顺序表
数组
栈(后进先出)
栈,是限定尽在表尾进行插入或者删除操作的线性表,后进先出(LIFO)
队列(先进先出)
链队列
循环队列
双端队列
Java中的Deque接口
链表
单向链表
循环链表
双向链表
树
二叉树
完全二叉树
堆
满二叉树
哈夫曼树
哈夫曼微博
用于二级制表示字符串
二叉搜索树
二叉搜索树满足这样的条件,每个节点包含一个值,每个节点至多有两个子树。每个节点左子树节点的值都小于自身的值,每个节点右子树节点的值都大于自身的值。
二叉树的查询时间复杂度是 log(N),但是随着不断的插入、删除节点,二叉树的树高可能会不断变大,当一个二叉搜索树所有节点都只有左子树或者都只有右子树时,其查找性能就退化成线性的了
平衡二叉树
平衡二叉树可以解决上面这个问题,平衡二叉树保证每个节点左右子树的高度差的绝对值不超过 1,例如 AVL 树。AVL 树是严格的平衡二叉树,插入或删除数据时可能经常需要旋转来保持平衡,比较适合插入、删除比较少的场景。
红黑树
红黑树是一种更加实用的非严格的平衡二叉树。红黑树更关注局部平衡而非整体平衡,确保没有一条路径会比其他路径长出 2 倍,所以是接近平衡的,但减少了许多不必要的旋转操作,更加实用。前面提到过,Java 8 的 HashMap 中就应用了红黑树来解决散列冲突时的查找问题。TreeMap 也是通过红黑树来保证有序性的。
(1)每个节点不是红色就是黑色。(2)根节点是黑色。(3)每个叶子节点都是黑色的空节点,如图中的黑色三角。(4)红色节点的两个子节点都是黑色的。(5)任意节点到其叶节点的每条路径上,包含相同数量的黑色节点。
多叉树
B树
B 树是一种多叉树,也叫多路搜索树。B 树中每个节点可以存储多个元素,非常适合用在文件索引上,可以有效减少磁盘 IO 次数。B 树中所有结点的最大子节点数称为 B 树的阶,如下图所示是一棵 3 阶 B 树,也叫 2-3 树。
B 树的关键字分布在整颗树中,一个关键字只出现在一个节点中;搜索可能在非叶节点停止;B 树一般应用在文件系统。
B+树
节点中的关键字与子树数目相同,比如节点中有 3 个关键字,那么就有 3 棵子树;关键字对应的子树中的节点都大于或等于关键字,子树中包括关键字自身;所有关键字都出现在叶子节点中;所有叶子节点都有指向下一个叶子节点的指针。
与 B 树不同,B+ 树在搜索时不会在非叶子节点命中,一定会查询到叶子节点;另外一个,叶子节点相当于数据存储层,保存关键字对应的数据,而非叶子节点只保存关键字和指向叶节点的指针,不保存关键字对应的数据,所以同样数量关键字的非叶节点,B+ 树比 B 树要小很多。
B+ 树更适合索引系统,MySQL 数据库的索引就提供了 B+ 树实现。原因有三个:(1)由于叶节点之间有指针相连,B+ 树更适合范围检索;(2)由于非页节点只保存关键字和指针,同样大小非叶节点,B+ 树可以容纳更多的关键字,可以降低树高,查询时磁盘读写代价更低;(3)B+ 树的查询效率比较稳定。任何关键字的查找必须走一条从根结点到叶子结点的路,所有关键字查询的路径长度相同,效率相当。最后可以简单了解,还有一种 B* 树的变种,在 B+ 树的非叶节点上,也增加了指向同一层下一个非叶节点的指针。
字典数
图
有向图
无向图
带权图
哈希表
哈希函数
直接地址法
数字分析法
平方取中法
折叠法
除留余数法
随机数法
处理哈希冲突
开发定址法
再哈希法
链地址法
建立一个公共溢出区
数据结构演示地址:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
数据结构与算法
算法
常用算法思路
分治
动态规划
贪心
回溯
分支界定
复杂度
时间复杂度
空间复杂度
字符串匹配
BF算法
BM算法
Sunday算法
KMP算法
Tire算法
排序
插入
希尔
直播
交换
冒泡
快排
选择
简单选择
归并
基数
查找
二分查找
二叉排序树
Hash
BloomFilter
排序算法
分类
内排序
插入排序
直接插入排序
希尔排序
选择排序
简单选择排序
堆排序
交换排序
冒泡排序
快速排序
归并排序
基数排序
外排序
评估标准
时间/空间复杂度O
稳定性
查找算法
分块查找
哈希查找
贪心算法
爬山问题
分治算法
回溯算法
文件指纹算法
位图算法
布隆过滤器
0 条评论
回复 删除
下一页