SpringCloud学习笔记
2023-12-14 21:07:09 0 举报AI智能生成
登录查看完整内容
SpringCloud学习笔记
作者其他创作
大纲/内容
数组
单向链表
双向链表
循环链表
链表
在普通链表上简历索引
跳表
一致性哈希
哈希
队列
栈
根节点是黑色
叶子节点（NIL）是黑色
从根节点到叶子节点黑色节点的个数相同
节点为黑色或者红色
红色节点的两个子节点为黑色
五个特性
并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。
优点
红黑树
二叉搜索树
1.定义任意非叶子结点最多只有M个儿子；且M>2；
4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
5.非叶子结点的关键字个数=指向儿子的指针个数-1；
8.所有叶子结点位于同一层；
定义
1.关键字集合分布在整颗树中；
2.任何一个关键字出现且只出现在一个结点中；
3.搜索有可能在非叶子结点结束；
4.其搜索性能等价于在关键字全集内做一次二分查找；
5.自动层次控制；
特性
b树
其定义基本与B-树同，除了：
1.非叶子结点的子树指针与关键字个数相同；
3.为所有叶子结点增加一个链指针；
4.所有关键字都在叶子结点出现；
1.\t所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
2.不可能在非叶子结点命中；
3.\t非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
4.更适合文件索引系统；
b+树
B树中同一键值不会出现多次，并且它有可能出现在叶结点，也有可能出现在非叶结点中。而B+树的键一定会出现在叶结点中，并且有可能在非叶结点中也有可能重复出现，以维持B+树的平衡
因为B树键位置不定，且在整个树结构中只出现一次，虽然可以节省存储空间，但使得在插入、删除操作复杂度明显增加。B+树相比来说是一种较好的折中。
B树的查询效率与键在树中的位置有关，最大时间复杂度与B+树相同(在叶结点的时候)，最小时间复杂度为1(在根结点的时候)。而B+树的时候复杂度对某建成的树是固定的
b树和b+树区别
是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；
B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3
B*树
B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；
B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分<br>数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的<br>关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点<br>与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增<br>加新结点的指针； 所以，B*树分配新结点的概率比B+树要低，空间使用率<br>更高；<br>
b*和b+的区别
相比于”二叉查找树”，它的特点是：AVL树中任何节点的两个子树的高度最大差别为1。
左子树的左子树导致的失衡
左左
左子树的右子树导致的失衡
左右
右子树的左子树导致的失衡
右左
右子树的右子树导致的失衡
右右
失去平衡的可以概括为4种姿态
AVL树
是一种带权路径长度最短的二叉树
如何译码
哈夫曼树
字典树（Trie）可以保存一些 字符串 -> 值 的对应关系。基本上，它跟 Java 的 HashMap 功能相同，都是 key-value 映射，只不过 Trie 的 key 只能是字符串。
典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计
使用场景
（1）\t根节点不包含字符，除根节点意外每个节点只包含一个字符。
（2）从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
（3）每个节点的所有子节点包含的字符串不相同。
（4）如果字符的种数为n，则每个结点的出度为n，这也是空间换时间的体现，浪费了很多的空间。
（5）插入查找的复杂度为O(n)，n为字符串长度。
基本性质
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
Tire树
树
数据结构
稳定排序
空间复杂度O(1)
平均时间复杂度O(n2)
直接插入
不稳定排序
平均时间复杂度O(n1.3)
shell排序
插入排序
直接选择排序
平均时间复杂度O(nlgn)
堆排序
选择排序
冒泡排序
快速排序
交换排序
空间复杂度O(n)
归并排序
从(array.length-2)/2开始到0构造堆
两指针之三色排序
排序（https://blog.csdn.net/zxzxzx0119/article/details/79826380）
查找数组中间元素
怎么优化
KMP算法
使用linkhashmap实现LRU
栈实现队列
新建节点
非新建节点
反转链表
基本算法
bitset或者布隆过滤器
1亿个手机号码，判断重复
分区间（分桶统计，然后计数找到中间的）
100亿个数中寻找中位数
大数据算法
两个下标分别指向数组的头部，比如，i 指向数组 a 的头部，j 指向数组 b 的头部，那么比较 a[i] 和 b[j] ，如果 a[i] 较大，移动 j，如果 b[j] 较大，那么 移动 i，如果相等，那么 i 和 j 往后挪动，采用这种方式，只需要一次遍历即可
两个有序数组如何找到相同的元素
https://blog.csdn.net/zhangxiao93/article/details/55101605
旋转数组找最小值
https://www.cnblogs.com/grandyang/p/4325840.html
旋转数组找目标值(target)
查找旋转数组
是否有环
找出环
递归
前序遍历
中序遍历
栈、双向链表
后序遍历
非递归（队列)
层次遍历
树的四种遍历
最少硬币数
多少种组合
多少种排列组合
硬币找零
leetcode与剑指offer
分段20层、20层的去检测
100层楼丢玻璃球，一旦超过某层就会破，你只有两个球
面试算法题
正则表达式匹配ip地址
逆波兰式
其他算法
算法、数据结构
职业：暂无
0 条评论
回复 删除
下一页
