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的代码差别: