雨羊的博客

红黑树

参考：面试问你红黑树，可以这样回答红黑树详解，对插入旋转独到理解红黑树变色和旋转，图文案例讲解红黑树简介及左旋、右旋、变色 1. 红黑树简介 1.1 为什么要使用红黑树红黑树是一种自平衡的二叉查找树。对于二叉查找树，容易出现严重单边长的情况，会

树

参考：AVL 树 1. 什么是 AVL 树 AVL 树，自平衡二叉查找树，名字来源于作者首字母大写。在 AVL 树中，任一节点对应的两颗子树最大高度差为1，因此，AVL 树也称为高度平衡树。查找、删除、插入平均、最坏复杂度都是O(log n)，增加和删除元素的操作可能触发一次或多次树旋转。 2.

树

参考文档：最长回文子串解题思路2：Manacher算法 1. 介绍 Manacher(又称"马拉车")算法通过对字符串预处理的方式求出最长回文子串，算法时间复杂度为 O(n) 第一步: 添加分隔符

字符串

参考文献：【浅学Java数据结构】优先级队列以及堆的创建、插入、删除【数据结构】【堆】堆的建立、插入和删除 1. 堆的概念如果有一个关键码的集合 K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2i+1 且

堆

参考文档：漫画：什么是B-树？漫画：什么是B+树？ 1. B- 树 B- 树念 B 树，不念 B 减树 1.1 数据库索引为什么不使用二叉查找树？其实从算法逻辑上来讲，二叉查找树查找速度和比较次数都是最小的。但是，我们不得不考虑一个现实问题：磁盘 IO。数据库索引是存储在磁盘上的，当数据量比

树

参考文档：什么是跳跃表？ 1. 什么是跳跃表跳跃表(Skip List)是一种基于有序链表的扩展，简称跳表。其实就是使用关键节点作为索引的一种结构。怎样能更快查找到一个有序链表的某一节点呢？可以利用类似索引的思想，提取出链表中的部分关键节点比如：给定一个长度是 7 的有序链表，节点值依次

链表

参考文献：快速排序算法

排序

参考文献：什么是差分数组？背景如果给你一个包含5000万个元素的数组，然后会有频繁区间修改操作，那什么是频繁的区间修改操作呢？比如让第1个数到第1000万个数每个数都加上1，而且这种操作时频繁的。此时你应该怎么做？很容易想到的是，从第1个数开始遍历，一直遍历到第1000万个数，然后每个数都加上

数组

基数排序时间复杂度 O(kn)，k 为要排序的数字的最大长度例如对 342、58、576、356 进行排序不足的位数看做是 0 342 058 576 356 第一步按照个位将数字依次放到不同的位置 0: 1: 2: 342 3: 4: 5: 6: 576, 356 7: 8:

排序

参考链接：字符串全排列算法学习思路：一位一位来固定，求后面的全排列，设当前为k位，则让[k,n]位的字符都与第k位进行交换，并且需要保证第k位不重复(代码中用set来实现)，然后对于每种情况，递归第k+1位即可。具体过程如下图：递归的出口，就是只剩一个字符的时候。代码如下： import

递归