

首页  思维导图  详情



SpringCloud学习笔记

2020-03-27 10:27:54   0  举报





AI智能生成

详细整理springcloud的知识点

java

学习笔记

大数据

模版推荐

作者其他创作

大纲/内容

数据结构

数组

链表

单向链表

双向链表

循环链表

跳表

在普通链表上简历索引

哈希

一致性哈希

队列

栈

树

红黑树

五个特性

根节点是黑色

叶子节点（NIL）是黑色

从根节点到叶子节点黑色节点的个数相同

节点为黑色或者红色

红色节点的两个子节点为黑色

优点

并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。

二叉搜索树

b树

定义

1.定义任意非叶子结点最多只有M个儿子；且M&gt;2；

2.根结点的儿子数为[2, M]；

3.除根结点以外的非叶子结点的儿子数为[M/2, M]；

4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）

5.非叶子结点的关键字个数=指向儿子的指针个数-1；

6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] &lt; K[i+1]；

7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于 K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键属于(K[i-1], K[i])的子树；

8.所有叶子结点位于同一层；

特性

1.关键字集合分布在整颗树中；

2.任何一个关键字出现且只出现在一个结点中；

3.搜索有可能在非叶子结点结束；

4.其搜索性能等价于在关键字全集内做一次二分查找；

5.自动层次控制；

b+树

定义

其定义基本与B-树同，除了：

1.非叶子结点的子树指针与关键字个数相同；

2.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；

3.为所有叶子结点增加一个链指针；

4.所有关键字都在叶子结点出现；

特性

1. 所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；

2.不可能在非叶子结点命中；

3. 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；

4.更适合文件索引系统；

b树和b+树区别

B树中同一键值不会出现多次，并且它有可能出现在叶结点，也有可能出现在非叶结点中。而B+树的键一定会出现在叶结点中，并且有可能在非叶结点中也有可能重复出现，以维持B+树的平衡

因为B树键位置不定，且在整个树结构中只出现一次，虽然可以节省存储空间，但使得在插入、删除操作复杂度明显增加。 B+树相比来说是一种较好的折中。

B树的查询效率与键在树中的位置有关，最大时间复杂度与 B+树相同(在叶结点的时候)，最小时间复杂度为1(在根结点的时候)。而B+树的时候复杂度对某建成的树是固定的

B*树

定义

是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；

特性

B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3

b*和b+的区别

B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；

&nbsp;B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分&lt;br&gt;数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的&lt;br&gt;关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点&lt;br&gt;与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增&lt;br&gt;加新结点的指针；&nbsp;&nbsp; 所以，B*树分配新结点的概率比B+树要低，空间使用率&lt;br&gt;更高；&lt;br&gt;

AVL树

定义

相比于”二叉查找树”，它的特点是： AVL树中任何节点的两个子树的高度最大差别为1。&nbsp;

失去平衡的可以概括为4种姿态

左左

左子树的左子树导致的失衡

左右

左子树的右子树导致的失衡

右左

右子树的左子树导致的失衡

右右

右子树的右子树导致的失衡

总结：发生问题的那个节点要成为根节点才能解决问题。不管我们是执行插入还是删除操作,只要不满足上面的条件, 就要通过旋转来保持平衡,而旋转是非常耗时的, 由此我们可以知道AVL树适合用于插入删除次数比较少，但查找多的情况。

哈夫曼树

是一种带权路径长度最短的二叉树

如何译码

Tire树

定义

字典树（Trie）可以保存一些&nbsp;字符串 -&gt; 值&nbsp;的对应关系。基本上，它跟 Java 的 HashMap 功能相同，都是 key-value 映射，只不过 Trie 的 key 只能是字符串。

使用场景

典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计

基本性质

（1）根节点不包含字符，除根节点意外每个节点只包含一个字符。

（2）从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。

（3）每个节点的所有子节点包含的字符串不相同。

（4）如果字符的种数为n，则每个结点的出度为n，这也是空间换时间的体现，浪费了很多的空间。

（5）插入查找的复杂度为O(n)，n为字符串长度。

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

基本算法

排序（https://blog.csdn.net/zxzxzx0119/article/details/79826380）

插入排序

直接插入

平均时间复杂度O(n2)

空间复杂度O(1)

稳定排序

shell排序

平均时间复杂度O(n1.3)

空间复杂度O(1)

不稳定排序

选择排序

直接选择排序

平均时间复杂度O(n2)

空间复杂度O(1)

不稳定排序

堆排序

平均时间复杂度O(nlgn)

空间复杂度O(1)

不稳定排序

交换排序

冒泡排序

平均时间复杂度O(n2)

空间复杂度O(1)

稳定排序

快速排序

平均时间复杂度O(nlgn)

空间复杂度O(1)

不稳定排序

归并排序

平均时间复杂度O(nlgn)

空间复杂度O(n)

稳定排序

堆排序

从(array.length-2)/2开始到0构造堆

调用Adjustheap,dad=start,end,son

从0至array.length-1,依次把最大的移至数组尾

两指针之三色排序

查找数组中间元素

KMP算法

怎么优化

使用linkhashmap实现LRU

栈实现队列

反转链表

新建节点

非新建节点

大数据算法

1亿个手机号码，判断重复

bitset或者布隆过滤器

100亿个数中寻找中位数

分区间（分桶统计，然后计数找到中间的）

leetcode与剑指offer

两个有序数组如何找到相同的元素

两个下标分别指向数组的头部，比如，i 指向数组 a 的头部，j 指向数组 b 的头部，那么比较 a[i] 和 b[j] ，如果 a[i] 较大，移动 j，如果 b[j] 较大，那么移动 i，如果相等，那么 i 和 j 往后挪动，采用这种方式，只需要一次遍历即可

查找旋转数组

旋转数组找最小值

https://blog.csdn.net/zhangxiao93/article/details/55101605

旋转数组找目标值(target)

https://www.cnblogs.com/grandyang/p/4325840.html

循环链表

是否有环

找出环

树的四种遍历

前序遍历

递归

栈

中序遍历

递归

栈

后序遍历

递归

栈、双向链表

层次遍历

递归（Digui(root,h）

非递归（队列)

硬币找零

最少硬币数

多少种组合

多少种排列组合

面试算法题

100层楼丢玻璃球，一旦超过某层就会破，你只有两个球

分段20层、20层的去检测

其他算法

正则表达式匹配ip地址

逆波兰式

 Collect

Get Started

后端学习路线

 Collect

Get Started

AI、机器学习、深度学习、大模型的关系图

 Collect

Get Started

PMBOK学习笔记

 Collect

Get Started

精准学习笔记





0 条评论

下一页