合理运用心流通道，科学刷题，快乐刷题！

前言

怎么刷算法题？按照什么顺序刷题？如何科学地提高算法能力？

如果你刚开始刷题，还不熟悉基本编程语法和常用库函数，推荐先刷力扣官方的入门题单：

红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。

它是在1972年由鲁道夫·贝尔发明的，他称之为"对称二叉B树"，它现代的名字是在Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文中获得的。

它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的：它可以在 O(lg(n)) 时间内做查找，插入和删除，这里的 n 是树中元素的数目。

用途和好处

红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。

伸展树（英语：Splay Tree）是一种能够自我平衡的二叉查找树，它能在均摊 O(log n) 的时间内完成基于伸展（Splay）操作的插入、查找、修改和删除操作。

它是由丹尼尔·斯立特（Daniel Sleator）和罗伯特·塔扬在1985年发明的。

核心思想

考虑到局部性原理（刚被访问的内容下次可能仍会被访问，查找次数多的内容可能下一次会被访问），为了使整个查找时间更小，被查频率高的那些节点应当经常处于靠近树根的位置。

ps: 这个思想实际上非常的简单，也非常的实用。我们以前实现的 LFU 的思想是类似的。

2–3树是一种树型数据结构，内部节点（存在子节点的节点）要么有2个孩子和1个数据元素，要么有3个孩子和2个数据元素，叶子节点没有孩子，并且有1个或2个数据元素。

2–3树由约翰·霍普克洛夫特于1970年发明。

2–3树和AA树是等距同构的，意味着它们是同一种数据结构。

换句话说，对于每个2–3树，都至少有1个AA树和它的元素排列是相同的。

2–3树是平衡树，意味着右边，左边，中间的子树的元素数量都是相同或接近的。

定义

（1）2-3 树要么为空要么具有以下性质：

在1970年，Bayer＆McCreight发表的论文《ORGANIZATION AND MAINTENANCE OF LARGE ORDERED INDICES》（大型有序索引的组织和维护）中提出了一种新的数据结构来维护大型索引，这种数据结构在论文中称为B Tree。

B树的定义

h：代表树的高度，k 是个自然数，一个B树要么是空的，要么满足以下条件：

1. 所有叶子节点到根节点的路径长度相同，即具有相同的高度；（树是平衡的）

2. 每个非叶子和根节点（即内部节点）至少有 k+1 个孩子节点，根至少有 2 个孩子；（这是关键的部分，因为节点都是分裂而来的，而每次分裂得到的节点至少有 k 个元素，也就有 k+1 个孩子；但根节点在分裂后可能只有一个元素，因为不需要向上融合，中间元素作为新的根节点，因此最少有两个孩子。而叶子节点没有孩子。）

3. 每个节点最多有 2k+1 个孩子节点。（规定了节点的最大容量）

4. 每个节点内的键都是递增的

B+ 树是应文件系统所需而产生的一种B Tree的变形树。

描述

B Tree有许多变种，其中最常见的是B+Tree，例如MySQL就普遍使用B+Tree实现其索引结构。

与B Tree相比，B+Tree有以下不同点：

每个节点的指针上限为2d而不是2d+1。

内节点不存储data，只存储key；叶子节点不存储指针。

图3是一个简单的B+Tree示意。

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

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

实际例子

给出了一个简单实例，如下图所示：

MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。

提取句子主干，就可以得到索引的本质：索引是数据结构。

我们知道，数据库查询是数据库的最主要功能之一。

我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。

最基本的查询算法当然是顺序查找（linear search），这种复杂度为O(n)的算法在数据量很大时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查找算法，例如二分查找（binary search）、二叉树查找（binary tree search）等。

场景

对于很多场景，比如说图片展示，还有一些前后端请求，有时候通过 url 会比较麻烦。

通过 Base64 转换处理之后比较方便，当然也有把这个当做一种加密策略的。（实际上只是转码，不是严格意义的加密）

Base64是一种能将任意Binary资料用64种字元组合成字串的方法，而这个Binary资料和字串资料彼此之间是可以互相转换的，十分方便。

在实际应用上，Base64除了能将Binary资料可视化之外，也常用来表示字串加密过后的内容。

java 实现方式

早期作法

早期在Java上做Base64的编码与解码，会使用到JDK里sun.misc套件下的BASE64Encoder和BASE64Decoder这两个类别，用法如下：

神探夏洛克

二战加解密

卷福

SM4-中国人自己的加密算法

好的算法：告诉你算法，没有秘钥，也无法破解。

SM4是一种分组密码算法，其分组长度为128位（即16字节，4字），密钥长度也为128位（即16字节，4字）。

其加解密过程采用了32轮迭代机制（与DES、AES类似），每一轮需要一个轮密钥（与DES、AES类似）。

快速体验

maven 依赖

<dependency>
    <groupId>org.bouncycastle</groupId>
    <artifactId>bcprov-jdk15on</artifactId>
    <version>1.59</version>
</dependency>