RSA，KMP，AVL树，红黑树和LLRB-tree

发表于 分类于 阅读次数：

这三个算法是好几年前就好奇但一直没搞懂的神奇算法

0x01 RSA

RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。
但实际上，在1973年，在英国政府通讯总部工作的数学家克利福德·柯克斯（Clifford Cocks）在一个内部文件中提出了一个相同的算法，但他的发现被列入机密，一直到1997年才被发表。
RSA目前是应用最广泛的加密技术之一

RSA的生成步骤如下：

  1. 随意选择两个大质数p q，并计算$N=p*q$
  2. $r=(p-1)(q-1)$ 这是根据欧拉函数$r = φ(N) = φ(p)\cdotφ(q) = (p-1)\cdot(q-1)$获得的
  3. 选择一个小于r并与r互质的整数e（通常取65537），求得e关于r的模反元素d（$ed = 1(mod r)$，模反元素存在，当且仅当e与r互质）
  4. 销毁p和q
  5. (N , e)是公钥，(N, d)为私钥

假设明文内容m，密文内容c

  • 加密过程： $m^e = c ,(\mod n ,)$
  • 解密过程： $c^d = m ,(\mod n ,)$

0x02 KMP算法

KMP是字符串匹配的算法，由普通的O(MN)缩减到了O(M+N)。KMP 算法的意思是找到目标字符串（模式串）中已经匹配过的前缀，并略去其匹配过程。
先看知乎大神的解释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from https://www.zhihu.com/question/34623343/answer/59516921
我我是我是傻我不是傻逼我是傻逼我是大傻逼
找出句中的“我是傻逼”
普通的字符串匹配比较傻逼：
我我是我是傻我不是傻逼我是傻逼我是大傻逼
我
对上了
我我是我是傻我不是傻逼我是傻逼我是大傻逼
我是
对不上了，往后移一个，我们再来
我我是我是傻我不是傻逼我是傻逼我是大傻逼
__我
对上了
我我是我是傻我不是傻逼我是傻逼我是大傻逼
__我是
对上了
我我是我是傻我不是傻逼我是傻逼我是大傻逼
__我是傻
对不上了，往后移一下，我们再来
等等，你傻啊，你往后移一个明显不可能对的上嘛，为毛不一下移两个呢？
好好好，我移两个移两个
我我是我是傻我不是傻逼我是傻逼我是大傻逼
_____我对上了
我我是我是傻我不是傻逼我是傻逼我是大傻逼
_____我是对上了
我我是我是傻我不是傻逼我是傻逼我是大傻逼
_____我是傻对上了
我我是我是傻我不是傻逼我是傻逼我是大傻逼
_____我是傻逼对不上了。。。
这次还往后移一个吗？还是……移两个？
啊？你傻啊，你看不出来能一次往后移三个啊！！！

嗯？怎么看出来的呢？
这个嘛，当然是和我是傻逼这四个字有关系啦。匹配的越多，失配后后移的越多。
那后移多少呢？
那就是next数组啦。。。

0x03 AVL树与红黑树

对于普通的排序二叉树，如果运气不好（比如插入的数据本来就是有序的），那么树就会变成链表（只有左儿子或右儿子）。于是科学家们就发明了完全平衡的AVL树和允许一丢丢不平衡的红黑树。

  • AVL树：最早的平衡二叉树之一，应用比较少。Windows对进程地址空间的管理用到了AVL树。
  • 红黑树：广泛应用在C++的STL中，比如map和set都是红黑树实现的
  • B/B+树：磁盘文件组织，数据库的索引
  • Trie树：统计排序大量字符串（自动机）

1. AVL树（平衡二叉树）

AVL树的左子树和右子树的深度之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。

为了防止排序二叉树的不平衡，AVL树中添加了平衡因子，当树不平衡时对树进行旋转。（这篇文章写得很清楚）

其中，对右子树中插入右孩子导致不平衡需要左旋，对右子树中插入左孩子导致不平衡需要右旋+左旋。当删除左孩子的时候，其实相当与插入了右孩子。具体实现方法如图：

2. 红黑树

下图出自"程序员小灰"公众号

红黑树的规则如下：

  1. 每个节点不是红色就是黑色的；
  2. 根节点总是黑色的；
  3. 如果节点是红色的，则它的子节点必须是黑色的（反之不一定）；
  4. 从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）。

红黑树的规则太复杂了，然而我们从这篇文章中读懂红黑树的起源2-3-4树，问题就迎刃而解啦。

我们定义

  • 2节点：瘦节点
  • 3节点：胖节点
  • 4节点：胖胖节点

因此，往瘦节点插入元素后会变成胖节点（2个值的节点）；往胖节点再插入元素时，胖节点会变成胖胖节点，接着胖胖节点分解成3个瘦节点。

理解2-3-4树以后再来看红黑树。以2-3-4树的理论，红节点与父节点构成了胖（胖）节点，他们彼此是等价的。因此就不难理解，旋转操作只是为了下一步计算方便，而并没有改变这等价关系。如下图。


对于红黑树，插入操作分为4种情况

  1. 当前节点N是树中的根节点—>将节点直接染成黑色
  2. 当前节点的父亲P是黑色—>直接添加
  3. 算法导论 情况1叔叔是红色（相当与出现了5节点）—>父亲，叔叔，爷爷全部变色
  4. 算法导论 情况2,3叔叔是黑色（出现了胖胖节点，变成其标准形状）—>将N变为左孩子（左旋），并对整颗树进行右旋。形成胖胖节点的标准形状

这篇文章详细的介绍了红黑树的各种操作。

应该注意到，2-3-4树是不允许有5节点的。因此，翻开算法导论，情况1：叔节点是红色的就可以看作，发现了不可能存在的5节点，就立马变色。因为胖胖树最终是要拆成3个瘦树的，所以对连续红色节点的树进行旋转，形成胖胖的标准形状。

3. 左倾红黑树

这篇文章（插入部分有错误，详情见我给他的评论）里介绍了左倾红黑树。不同于算法导论中介绍的版本，左倾红黑树是由2-3树的变种，又因为作者给了很牛逼的递归表达，因此实现起来更简单。

  1. 插入红节点，如果如果右倾，左旋为左倾
  2. 如果出现连续的红节点，右旋转换成胖胖节点
  3. 出现了胖胖节点，立刻分解成3个瘦节点（变色）

下面是作者给出的RB-tree和LLRB-tree的代码差别：