寻找链表环入口的算法证明

寻找链表环入口是一道经典算法题目Linked List Cycle II,其解法是比较技巧性的快慢指针,写起来比较简单。真正的难点在于如何去证明解法的正确性。网上许多证明难以理解(没,我没证据),并且思路没有普适性,本文将会提供一种比较简洁且可移植的证明思路。

先回顾下题目:

给定一个单向链表(singly-linked-list)的头结点head,返回该链表的环入口。如下图所示,函数应该返回指向节点值为2的指针。
Circular Linked List

本题的最优解法是使用快慢两个指针,都从head开始出发,慢指针每次走一步,快指针每次走两步。当他们相撞的时候把快指针重新指向head,慢指针保留在相撞位置。并且从此时开始快慢指针的前进速度都改成一步,直到它们再次相撞的位置就是环的入口。详细代码如下:

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(!head)
return nullptr;

//寻找碰撞点
ListNode *slow = head, *fast = head;
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
break;
}

if(fast==nullptr || fast->next==nullptr)
return nullptr;

//寻找环入口
fast = head;
while(slow != fast){
slow = slow->next;
fast = fast->next;
}
return slow;
}
};

证明

接下来我们将会对这种解法进行证明,如下图所示将一个环形链表分为三个部分,分别为a,b和c代表此部分链表的长度(length),其中a的末端是环入口。
Circular Linked List

  1. 定义slow, fast分别为链表的快慢指针,slow每次前进一步,fast每次前进两步。
  2. 可以证明当快慢指针相撞的时候,它们相撞的时间点必定是慢指针进入环后的第一圈。(提示:根据快慢指针的定义并使用矛盾证法:proof-by-contradiction)。假设它们在图示的碰撞点处碰撞,那么此时slow,fast两个指针走过的步数分别为:

slow : a+b
fast : 2(a+b)
  1. 假设有环形链表指针p1, p2,我们定义符号:=的意义为:若p1 := p2则p1和p2指向环形链表的同一个节点。
    根据环形链表指针加减法的定义,有如下的法则:

若p1 := p2,且k为一个整数,则:
p1+k := p2+k
  1. 因为快慢指针在碰撞点相撞,且他们都是从head开始出发,所以可以得到下面的等式:

head+(a+b) := head+2(a+b)

根据上图的环形链表,有下列等式:


head+(a) := head+(a+b+c)

值得提醒的是a,b,c为整数长度(length),而head为指针,上面的等式进行的是指针的加减法(pointer arithmetic)。
为了方便表示,我们省略head,并默认等式两边都加上了head,那么可以得到下面的简化表示:


a+b := 2(a+b)
a := a+b+c

我们在前面有提到过上述算法在找到碰撞点后把fast重新指向head然后再向前一次走一步,直到快慢指针碰撞,那么如果它们碰撞时的位置的确为环入口的话那么必定有这个等式成立:a+b+a := a。你会问为什么?解析是:假设上述算法是正确的,那么第一次碰撞时slow走的步数为a+b,此时fast重新指向了头结点。根据算法中的描述,当再次碰撞的时候fast和slow在原来的基础上又走了a步(别忘了此时它们的速度已经变成一样了),此时slow = head+a+b+a指向了环入口,fast = head+a也指向了环入口,所以我们有简化式子a+b+a := a。只要证明这个式子正确,就可以确定slow指针从head出发经过了a+b+a步最终到达环入口。返回该处的指针即是题目要求的答案。

  1. 现在集中精力来证明这个等式是成立的:

核心部分


//别忘了这只是为了方便我们观察的简化表示,
//完整表达式中:=的左右应该都是指针

我们有:
a+b := 2(a+b) (1)
a := a+b+c (2)

那么
a+b+a := a+b+(a+b+c) //利用(2)
:= 2(a+b)+c
:= a+b+c //利用(1)
:= a //利用(2)

证明完毕

到此我们对于上述算法的确能够找到环入口的证明完毕,其实上面一大段都只是为了保持文章的完整性做的详细说明,真正的证明其实非常简短,就是核心部分,只要你对符号:=的定义了解,那么很容易就能够通过纯数学变换重新写出这份证明。我们的思路具有普适性,同样使用定义的符号:=可以证明寻找相交链表交点的算法正确性Intersection of Two Linked Lists,有机会(通常隐含的意思是我懒得写)我会对此进行扩展说明。

BST(非平衡),AVL,红黑树,B+树的区别与应用

本文出自kelvin.ink
转载请注明出处

问题要点

这个问题要探究的要点是:


1. 这四种树的定义的了解
2. 这些树的主要区别,特性
3. 每种树的具体应用场景是什么,为何它适合于这种场景,为什么不用其他树代替

事实上Knuth Donald在《计算机编程艺术》中已经对这些树都作了非常深刻的说明,建议想要深入探究的读者可以自行找到这本书进行阅读。Google books有这本书的影印版。可以搜索6.2.2Binary Tree Search找到相应的章节。本文在此基础上结合其他资源对这个问题进行简要说明,并尽量保证self contained。

简明定义

我们先回顾一下这几种树的定义,为继续下一步的讨论建立共识。

二叉搜索树(BST)

简明BST递归定义(Knuth Donald):


对于任意一个节点均满足:
1. 所有位于左子树的节点值均比该节点值小
2. 所有位于右子树的节点值均大于等于该节点值
3. 所有左子树和右子树也必须是BST

AVL

简明AVL定义(Knuth Donald):

对于任意一个节点均满足:


1. 左子树和右子树的高度差小于等于1

红黑树

简明RBTREE定义(Knuth Donald):


1. 每个节点要么是红色,要么是黑色
2. 根节点是黑色
3. 所有叶节点(NIL)都是黑色
4. 如果一个节点是红色,那么它的两个孩子都是黑色
5. 从任意一个节点出发,到达其后代NIL节点的路径中都包含相同个数的黑节点

B+树

定义Branch Factor: b 为一个节点可以拥有的最大子节点的个数,那么:


1. 对于根节点,如果整棵树的节点个数大于1,那么根节点的子节点数量大于等于2
2. 对于内部节点,其子节点个数m必须满足 b/2 <= m <= b
3. 对于叶节点,其子节点个数m必须满足 b/2 <= m <= b
4. 每个节点内部的key值是已经排序的
5. 叶节点之间以linked list方式相连并且是有序的
6. 从根节点到叶节点的路径长度均相同

推荐阅读


BST: https://en.wikipedia.org/wiki/Binary_search_tree
AVL: https://en.wikipedia.org/wiki/AVL_tree
RBTREE: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
B+TREE: https://en.wikipedia.org/wiki/B%2B_tree

树的特性

基于上面对各种树的定义,我们可以推出它们的一些相关特性,本节我们将会罗列并解析这几种树的一些相关特性。

复杂度

我们先比较一下它的在进行各种操作时的复杂度:
Complexity

上面表格每个单元格显示的是平均复杂度/最差复杂度。我们可以看到除了BST外,其他树在查找,插入和删除操作时的复杂度均为O(logn),因为它们都是平衡树,而BST不是。相同的渐近复杂度并不意味着它们毫无区别,毕竟它们可能会相差数倍的关系。接下来我们会描述这些树的一些具体特性,并突出它们的主要区别。

1
//Todo

树的应用

BST

通常情况下非平衡的BST都仅仅当作一种概念,很少有实际场景会使用这种结构,因为查找在最差的情况下会出现O(n)的时间复杂度。虽然如此,我们依然可以了解一下它能够实现点什么,即使我们实际应用不会这么做。

BST可以实现:

  • 排序
  • 优先队列

BST排序的实现是把输入的元素一个个插入到BST,然后进行一次中序遍历,平均复杂度为O(nlogn)。优先队列(min)的实现是从根节点出发一直向左找到最小节点,平均复杂度为O(logn),最差状况为O(n),显然它在时间复杂度上是比不上min-heap的。

AVL

AVL是历史上出现的第一种平衡二叉树,它现在的很多应用都已经被红黑树代替。主要原因是它的平衡限制比较红黑树严格,在插入或者删除节点的时候很容易违反平衡限制条件,造成频繁的树结构调整和重新平衡。AVL限制对每个节点左子树和右子树的高度相差不超过一,所以它是高度平衡的二叉树,因而在进行查找的时候效率很高。而红黑树的平衡限制比AVL要弱,甚至左右子树的高度差等于2倍,所以红黑树的查找效率比AVL要低。但是,红黑树不需要频繁重平衡(得益于其宽松的限制条件),所以在插入删除较频繁的环境中红黑树胜出。

红黑树

红黑树虽然定义复杂,但是它的限制条件是相对AVL宽松的。所以在进行插入删除操作的时候出现违反限制条件的状况较少,因而重平衡操作出现的机会比AVL少。基于上述原因,许多需要进行频繁删插操作的场景都使用来红黑树:

  • Linux epoll
  • C++ STL(sert, map)
  • Completely Fair Sheduler

B+树

B+树主要应用于文件系统中,最大的原因是它高度平衡,branch factor较大,这样可以减少磁盘IO。

B+树主流应用:

  • 数据库索引(SQL Server, PostgreSQL, SQLite)
  • 文件系统(NTFS XFS, NSS, JFS)

树的区别

比较AVL与红黑树的优缺点

在前面已经比较过了这两者的优缺点,为了突出它们的区别,特意把上面一段文字复制到本问题下:

AVL是历史上出现的第一种平衡二叉树,它现在的很多应用都已经被红黑树代替。主要原因是它的平衡限制比较红黑树严格,在插入或者删除节点的时候很容易超出平衡限制条件,造成频繁的树结构调整和重新平衡。AVL限制对每个节点左子树和右子树的高度相差不超过一,所以它是高度平衡的二叉树,因而在进行查找的时候效率很高。而红黑树的平衡限制比AVL要弱,甚至左右子树的高度差等于2倍,所以红黑树的查找效率被AVL要低。但是,红黑树不需要频繁重平衡(得益于其宽松的限制条件),所以在插入删除较频繁的环境中红黑树胜出。REF

同时我们看看Knuth对于AVL的评价:
Knuth AVL Tree Comment

为何数据库索引使用B+树而不是红黑树(或其他)

要理解这个问题,我们先分析一下数据库的性质。数据库的数据被分割为多个Page以文件的形式储存在磁盘上的。因此我们每次进行数据库查询其实是在做Disk IO,而Disk IO是时间开销较大的操作(关键!)。而数据库在进行索引lookup的时候每次access一个page都是一次IO。因此我们需要选择一种能够尽量少做Disk IO的数据结构来构建索引。B+树之所以被选中主要是因为它的branch factor较大,树高较小。因而在进行索引搜索的时候需要进行的IO数量也较其他树的数量小,所以是最合适的做索引的数据结构。基于上述原因,在应用场景需要选树的时候我们都会做如下的思考:基于内存操作的我们考虑红黑树,AVL和BST,基于磁盘操作的我们优先考虑B或B+树。REF

我们在这边引用一段Knuth对于B+树的精彩评价来佐证我们的观点:
Knuth B+ Tree Comment

References:

Key References
Knuth Donald(1997) 6.2.2:Binary Tree Searching. The Art of Computer Programming
Ben Pfaff https://web.stanford.edu/~blp/papers/libavl.pdf

HTTP Introduction

What’s HTTP

HTTP is a protocol that is used for the communication in world wide web. For example, when you try to google something, you need to enter http://www.google.com in your web browser address bar. Then your browser start talking to the server of google on behalf of you by following the rules of http protocol.

HTTP client server

HTTP is an application protocol in the OSI seven layers model. So, it’s the protocol for application-to-application communication. For the case of accessing google website, it’s the protocol that enables the communication between client web browser and google server (apache, nginx). Until now, there are three versions of HTTP protocols, they are HTTP1.0, HTTP1.1 and HTTP2.0. This article will mainly focus on version 1.0 and 1.1.

The official documents of HTTP1.1 can be found here. (Afraid? XXD)

Characteristics

  • Connectionless
  • Stateless

HTTP is connectionless, because for each http request/response pair, a new tcp connection is set up (HTTP1.0). After that, the tcp connection is closed. Since HTTP1.1, the tcp connection is allowed to be reused by multiple request/response pair.

HTTP is stateless, because there is no link between two requests. But we can use session and cookies to keep the state or context of user interactions.

Comparing HTTP1.0 with HTTP1.1

  1. HTTP1.1 allows http connection to be reused(persistent connection) by multiple request/response pairs. In http1.0, you have to open a new http connection for each request/response pair.
  2. HTTP1.1 Uses Etag to replace If-Modified-Since
  3. HTTP1.1 Supports chunk transfer

Request message format

Let’s take a look at a typical example of http request:

1
2
3
4
5
6
7
8
9
10
11
GET /path/to/resource HTTP/1.1
User-Agent: Mozilla/4.0 (compatible; MSIE5.01; Windows NT)
Host: www.kelvin.ink
Content-Type: text/xml; charset=utf-8
Content-Length: length
Accept-Language: en-us
Accept-Encoding: gzip, deflate
Connection: Keep-Alive

<?xml version="1.0" encoding="utf-8"?>
<string xmlns="http://hello.com/">string</string>

A http request is composed of three parts: request line, header and request body. Where


Request-Line = Method SP Request-URI SP HTTP-Version CRLF

Where SP represents space and CRLF represents carrige return line feed.

HTTP Request

The following figure shows the detail format of a HTTP datagram. Method can be one of GET, PUT, POST, DELETE .etc. And for the header field, you can specify some basic info such as host, Accept-Language, Content-Type for the request. Other fields are for advanced users, for example, if you want to crawl web content with spider, you can frequently change your User-Agent to pretend to be a normal human. You may also want to keep the connection alive by specifying the Connection field.

HTTP Request

After constructing the request message, we establish a TCP connection and send the message to the server, and then receive a HTTP response from it. We start to talk about the format of HTTP response in next section.

Methods? Explain Them!

It’s highty recommend to read through the RFC doc of HTTP request methods.

Response message format

The format of HTTP response is similar to that of HTTP request.

Let’s checkout a typical http response first:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
HTTP/1.1 200 OK
Date: Sun, 30 Jun 2019 14:55:19 GMT
Expires: -1
Cache-Control: private, max-age=0
Content-Type: text/html; charset=ISO-8859-1
P3P: CP="This is not a P3P policy! See g.co/p3phelp for more info."
Server: gws
X-XSS-Protection: 0
X-Frame-Options: SAMEORIGIN
Set-Cookie: 1P_JAR=2019-06-30-14; expires=Tue, 30-Jul-2019 14:55:19 GMT; path=/; domain=.google.com
Set-Cookie: NID=186=Igr9gPUb8HL-S-iDsDtkEqrqPdEsWE19BA4R-EZ3gUeCnbE1tdG1t0irtfiiEOL7ZenA3ukMB7l4qG9TBwcKXrra7GLPmMpuShtKWaCrH1nnGJbqysRB8mvtPcAp9LC4nAmuYU6xG78FAnkNCaAOKrIiSqi7rseO9_w4JPBjW8Y; expires=Mon, 30-Dec-2019 14:55:19 GMT; path=/; domain=.google.com; HttpOnly
Accept-Ranges: none
Vary: Accept-Encoding
Transfer-Encoding: chunked

<!doctype html><html itemscope="" itemtype="http://schema.org/WebPage" lang="zh-HK"><head><meta content="text/html; charset=UTF-8" http-equiv="Content-Type"><meta content="/images/br ..........

A http response include three major components: status line, header, reponse body. Where


Status-Line = HTTP-Version SP Status-Code SP Reason-Phrase CRLF

HTTP Response

Basically, fields in a HTTP response tells us about the status of the http connection, information about the server, and some useful info for further access. For example, Status-Code tells us the healthiness of the connection, Server field tells us the identity of response server, and Set-Cookie sets a cookie on client side for later access.

Conclusion

We have talked about HTTP1.0 and HTTP1.1. What they are and for what purpose. We have also compared the differences between the two. But we haven’t discussed HTTP2.0 yet, this may be included in other posts or be expanded in this post later. Thanks!