无论是在计算机课上，还是在网上，对数据结构有一定了解的童鞋，应该都对树的遍历不陌生。常见的遍历方式有如下两种：
基于栈的遍历：需要额外的空间复杂度。实现略复杂。
基于递归的遍历：实现简单。空间复杂度上，与栈类似，只是这里的栈维护是由系统自动完成的。
在看左程云的《程序员代码面试指南》时，里面介绍了一种只需 O(1) 的额外空间复杂度的遍历方法：Morris 树遍历。感觉非常神奇。这里给大家介绍一下。
Morris 树遍历的神奇之处在于，它充分利用了树里面大量的空闲节点（比如叶子节点的左右子树节点就为空，可以利用起来）来建立起必要的连接，推动遍历的进行。核心思想非常简单：找出当前节点左子树的最右节点，此时最右节点的右子树为空，将最右节点的右子树指向当前节点。然后左移，递归完成所有相关连接。没有左子树时，则向右移动，依次完成上述操作。我们来结合图来说明。如图：
图 1. Morris 树遍历 如上图所示，当访问根节点 4 时，它的左子树的最右节点就是 3，将 3 的右子树指向当前节点 4，如线条 ⑥ 所示。向左启动，建立起 1 到 2 的连接 ④。再向左移动到 1，1 没有左子树，则向右移动，此时就利用上了刚刚建立起的连接 ④。依次类推，即可完成遍历。在遍历过程中，也需要把建立的临时连接给取消掉。
/** * Morris 树遍历 * * @author D瓜哥 · https://www.diguage.com */ public void morris(TreeNode head) { TreeNode curr = head; TreeNode mostRight = null; while (curr != null) { // 当前节点左子树的最右节点，当然是从左子树开始了 mostRight = curr.left; if (mostRight != null) { // 左子树不为空，则找出左子树的最右节点 while (mostRight.right != null // 由于需要建立最右节点到当前节点的连接， // 所以，需要判断是否已建立连接来打破死循环 && mostRight.right != curr) { mostRight = mostRight.right; } if (mostRight.right == null) { // 最右节点的右子树为空，则第一次访问，那么建立起连接 mostRight.right = curr; curr = curr.left; continue; } else { // 最右节点的右子树不为空，则第二次访问，打破连接，恢复原貌 mostRight.right = null; } } // 左子树为空，则向右移动 curr = curr.right; } } 根据代码，结合图示，很容易得到 Morris 遍历的结果： 4、2、1、22、3、42、6、5、62、7。分析这个结果可以发现：有左子树的节点都会被访问两次。
前根遍历 那么该树的前根遍历是什么呢？这个也很容易得出：4、2、1、3、6、5、7。如何从 Morris 遍历中，得到前根遍历的结果呢？对比两边的结果，可以很容易发现：将访问两次的元素，只在第一次访问时输出；只访问一次的原始直接输出即可。代码如下：
/** * Morris 树前根遍历 * * @author D瓜哥 · https://www.diguage.com */ public void morrisPre(TreeNode head) { TreeNode curr = head; TreeNode mostRight = null; while (curr != null) { // 当前节点左子树的最右节点，当然是从左子树开始了 mostRight = curr.left; if (mostRight != null) { // 左子树不为空，则找出左子树的最右节点 while (mostRight.right != null // 由于需要建立最右节点到当前节点的连接， // 所以，需要判断是否已建立连接来打破死循环 && mostRight.right != curr) { mostRight = mostRight.right; } if (mostRight.right == null) { // 最右节点的右子树为空，则第一次访问，那么建立起连接 mostRight.right = curr; // 第一次访问时，即输出 System.out.print(curr.val + " "); curr = curr.left; continue; } else { // 最右节点的右子树不为空，则第二次访问，打破连接，恢复原貌 mostRight.right = null; } } else { // 前面内容已经分析过：有左子树的节点就会被访问两次 // 那么没有左子树的节点，就自会访问一次，访问到时直接输出即可。 System.out.print(curr.val + " "); } // 左子树为空，则向右移动 curr = curr.right; } }
传输控制协议（英语：Transmission Control Protocol，缩写：TCP）是一种面向连接的、可靠的、基于字节流的传输层通信协议，由 IETF 的 RFC 793 定义。在简化的计算机网络 OSI 模型中，它完成第四层传输层所指定的功能。
毫不夸张地说，TCP 协议是目前整个互联网的基础。它解决了一系列的网络问题。带来的结果，就是协议本身非常复杂。考虑到文章篇幅问题，本文着重说明 TCP 建立连接时的三次握手过程和关闭连接时的四次挥手过程。
三次握手 图 1. TCP 三次握手 第一次握手(SYN=1, seq=x):
客户端发送一个 TCP 的 SYN 标志位置 1 的包，指明客户端打算连接的服务器的端口，以及初始序号 x，保存在包头的序列号(Sequence Number)字段里。
发送完毕后，客户端进入 SYN_SEND 状态。
第二次握手(SYN=1、seq=y；ACK=1、ACKnum=x+1):
服务器发回确认包(ACK)应答。即 SYN 标志位和 ACK 标志位均为 1。服务器端选择自己 ISN 序列号，放到包头的序列号(Sequence Number)字段里，同时将确认序号(Acknowledgement Number)设置为客户的 ISN 加 1，即 x+1。
发送完毕后，服务器端进入 SYN_RCVD 状态。
第三次握手(ACK=1，ACKnum=y+1)
客户端再次发送确认包(ACK)，SYN 标志位为 0，ACK 标志位为 1，并且把服务器发来 ISN 的序号字段+1，放在确定字段中发送给对方，即数据段放写 y+1。
发送完毕后，客户端进入 ESTABLISHED 状态，当服务器端接收到这个包时，也进入 ESTABLISHED 状态，TCP 握手结束。
SYN Flood 攻击 在三次握手过程中，服务器发送 SYN-ACK 之后，收到客户端的 ACK 之前的 TCP 连接称为半连接(half-open connect)。此时服务器处于 SYN_RCVD 状态。当收到 ACK 后，服务器才能转入 ESTABLISHED 状态.
题目描述 题目是 LeetCode 的第 538 题： 把二叉搜索树转换为累加树。
给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。
思路分析 一棵二叉搜索树，如果是中根遍历，那么，其序列正好是一个升序序列。但，题目要求的是大于等于自身的节点值之和。正常的中根遍历是“左中右”，反过来“右中左”，就是降序序列，累计求和就符合题目要求了。
解题代码 中序遍历，可以用栈，也可以使用 Morris 遍历。在 题解：找到二叉搜索树中两个错误的节点 中就是用了 Morris 遍历。网上也很少有反向的 Morris 中根遍历。正好练习一下。
/** * 基于 Morris 的倒序中根遍历 * * @author D瓜哥 · https://www.diguage.com */ public TreeNode convertBST(TreeNode root) { int sum = 0; // 反向 Morris TreeNode cur = root; TreeNode mostLeft = null; while (cur != null) { // 向右转 mostLeft = cur.right; if (mostLeft != null) { // 寻找最左边的节点 while (mostLeft.left != null && mostLeft.left != cur) { mostLeft = mostLeft.left; } if (mostLeft.left == null) { // 第一次访问，将最左节点的左子树指向当前节点 mostLeft.left = cur; cur = cur.right; continue; } else { // 第二次访问，掐断中间建立的连接 mostLeft.left = null; } } // 计算累加和 sum += cur.val; cur.val = sum; cur = cur.left; } return root; } 得益于 Morris 的优秀本质，这个解法的时间复杂度是： O(n)，空间复杂度是： O(1)。
关于 Morris 树遍历的更多介绍，请看： 神奇的 Morris 树遍历。
本文内容对于 Redis 7+ 来说已经过时，最新实现请看下面两篇文章：
Redis 核心数据结构（3）
Redis 核心数据结构（4）
在上一篇文章： Redis 核心数据结构（1） 中，介绍了链表、ziplist、quicklist 数据结构。这篇文章，来介绍一下 skiplist、dict。
skiplist 跳跃表是一种有序数据结构，支持平均 O(logN)、最坏 O(N) 复杂度的节点查找；大部分情况效率可以和平衡树相媲美，实现却比平衡树简单。
跳跃表就是 Redis 中有序集合键的底层实现之一。
server.h typedef struct zskiplistNode { sds ele; double score; struct zskiplistNode *backward; struct zskiplistLevel { struct zskiplistNode *forward; unsigned long span; } level[]; } zskiplistNode; typedef struct zskiplist { struct zskiplistNode *header, *tail; unsigned long length; int level; } zskiplist; typedef struct zset { dict *dict; zskiplist *zsl; } zset; skiplist，顾名思义，首先它是一个list。实际上，它是在有序链表的基础上发展起来的。
当我们想查找数据的时候，可以先沿着跨度大的链进行查找。当碰到比待查数据大的节点时，再回到跨度小的链表中进行查找。
skiplist正是受这种多层链表的想法的启发而设计出来的。按照上面生成链表的方式，上面每一层链表的节点个数，是下面一层的节点个数的一半，这样查找过程就非常类似于一个二分查找，使得查找的时间复杂度可以降低到 O(logN)。但是，存在的一个问题是：如果插入新节点后就会打乱上下相邻两层节点是 2:1 的对应关系。如果要维持，则需要调整后面所有的节点。
skiplist为了避免这一问题，它不要求上下相邻两层链表之间的节点个数有严格的对应关系，而是为每个节点随机出一个层数(level)。
插入操作只需要修改插入节点前后的指针，而不需要对很多节点都进行调整。这就降低了插入操作的复杂度。实际上，这是 skiplist 的一个很重要的特性，这让它在插入性能上明显优于平衡树的方案。
skiplist，翻译成中文，可以翻译成“跳表”或“跳跃表”，指的就是除了最下面第1层链表之外，它会产生若干层稀疏的链表，这些链表里面的指针故意跳过了一些节点（而且越高层的链表跳过的节点越多）。这就使得我们在查找数据的时候能够先在高层的链表中进行查找，然后逐层降低，最终降到第1层链表来精确地确定数据位置。在这个过程中，我们跳过了一些节点，从而也就加快了查找速度。
在中间插入一个有比较高 Level 的节点，如何维护前面节点到这个节点的这些链接？
在平衡树种，如何做范围查找？先确定边界，然后其他节点怎么查找？
skiplist 中 key 允许重复。
在比较时，不仅比较分数（即key），还要比较数据自身。
第一层链表是双向链表，并且反向指针只有一个。
在 skiplist 中可以很方便计算每个元素的排名。
Redis 中的有序集合（sorted set），是在 skiplist, dict 和 ziplist 基础上构建起来的:
当数据较少时，sorted set是由一个 ziplist 来实现的。其中集合元素按照分值从小到大排序。
当数据多的时候，sorted set 是由一个叫 zset 的数据结构来实现的，这个 zset 包含一个 dict + 一个 skiplist。dict 用来查询数据到分数(score)的对应关系，而 skiplist 用来根据分数查询数据（可能是范围查找）。
本文内容对于 Redis 7+ 来说已经过时，最新实现请看下面两篇文章：
Redis 核心数据结构（3）
Redis 核心数据结构（4）
Redis 目前是使用最广泛的缓存中间件。其突出特点就是支持多种常见的数据结构。对比 JDK 集合类的实现，Redis 的实现表现出很多独到之处，很多地方设计得别具匠心。下面就来简要介绍一下。
linkedlist Redis 底层也有很多地方使用到 linkedlist，并且也是双向链表。
adlist.h typedef struct listNode { struct listNode *prev; struct listNode *next; void *value; } listNode; typedef struct listIter { listNode *next; int direction; } listIter; typedef struct list { listNode *head; listNode *tail; void *(*dup)(void *ptr); void (*free)(void *ptr); int (*match)(void *ptr, void *key); unsigned long len; } list; Redis 的 linkedlist 实现特点是：
双向：节点带有前后指针；
无环：首尾没有相连，所以没有构成环状；
链表保存了首尾指针；
多态：可以保存不同类型的值，这里成为泛型也许更符合 Java 中的语义。
Redis 在 2014 年实现了 quicklist，并使用 quicklist 代替了 linkedlist。所以，现在 linkedlist 几乎已经是废弃状态。
ziplist Redis 官方在 ziplist.c 文件的注释中对 ziplist 进行了定义：
The ziplist is a specially encoded dually linked list that is designed to be very memory efficient. It stores both strings and integer values, where integers are encoded as actual integers instead of a series of characters. It allows push and pop operations on either side of the list in O(1) time. However, because every operation requires a reallocation of the memory used by the ziplist, the actual complexity is related to the amount of memory used by the ziplist.
题目描述 一棵二叉树原本是二叉搜索树，但是其中有两个节点调换了位置，使得这棵二叉树不再是二叉搜索树，请按升序输出这两个错误节点的值。(每个节点的值各不相同)
思路分析 一棵二叉搜索树，如果是中序遍历，那么，其序列正好是一个升序序列。如果序列中间出现了降序，那么就是树中错误的节点。这里有两种情况需要考虑：
如果两个节点正好相邻，那么降序的两个节点就是题目要求的节点。
如果两个节点不相邻，就会出现两次降序。很容易想到，“大”的元素跑前面，“小”的元素跑后面。在进行比较的时候，第一个降序时，前面大的元素是错误节点；第二次降序时，则是后面小的元素是错误节点。
有了上面的分析，就可以写代码了。
解题代码 中序遍历，可以用栈，也可以使用 Morris 遍历。前面正好学习了一下 Morris（详情请看： 神奇的 Morris 树遍历），借此机会练练手：
/** * 基于 Morris 的中根遍历 * * @author D瓜哥 · https://www.diguage.com */ public TreeNode[] getErrs(TreeNode head) { TreeNode[] result = new TreeNode[2]; TreeNode curr = head; TreeNode mostRight = null; TreeNode prior = null; while (curr != null) { mostRight = curr.left; if (mostRight != null) { while (mostRight.right != null && mostRight.right != curr) { mostRight = mostRight.right; } if (mostRight.right == null) { mostRight.right = curr; curr = curr.left; continue; } else { mostRight.right = null; } } if (prior != null) { if (prior.val > curr.val) { if (result[0] == null) { result[0] = curr; result[1] = prior; } else { result[0] = curr; } } } prior = curr; curr = curr.right; } return result; } 得益于 Morris 的优秀本质，这个解法的时间复杂度是： O(n)，空间复杂度是： O(1)。
前几天在看一个资料时，看到关于负载均衡算法的介绍。最近也在研究 Spring Cloud 和 Apache Dubbo 等微服务框架。正好负载均衡是微服务框架中一个很重要的知识点。就动手做个整理和总结。方便后续学习。
听朋友建议，这篇文章还可以在算法对比，客户端负载均衡与服务端负载均衡区分等两方面做些补充。这些内容后续再补充加入进来。
常见的负载均衡算法 轮询(Round Robin)法 轮询选择指的是从已有的后端节点列表中按顺序依次选择一个节点出来提供服务。
优点：试图做到请求转移的绝对均衡。实现简单，使用广泛。
加权轮询(Weighted Round Robin)法 实际使用中各个节点往往都带有不同的权重，所以一般都需要实现带权重的轮询选择。 权重高的被选中的次数多，权重低的被选中的次数少。
优点：是 轮询(Round Robin)法 改良版。适用于服务器配置不一致时，可以将配置好的服务器多干活，配置差的服务器少干活以使机器的负载达到相同的水平。
静态轮询(Static Round Robin)法 HAProxy 中实现的一个负载均衡算法。
没有后台服务器的限制，服务器启动时，修改权重也不会生效。增删服务器时，服务器准备就绪后，会立即加入到服务队列中。
随机(Random)法 通过随机函数，根据后端服务器列表的大小值来随机选择其中一台进行访问。由概率统计理论可以得知，随着调用量的增大，其实际效果越来越接近于平均分配流量到每一台后端服务器，也就是轮询的效果。
加权随机(Weighted Random)法 与加权轮询法类似，加权随机法也是根据后端服务器不同的配置和负载情况来配置不同的权重。不同的是，它是按照权重来随机选择服务器的，而不是顺序。
原地址哈希(IP Hashing)法 源地址哈希的思想是获取客户端访问的IP地址值，通过哈希函数计算得到一个数值，用该数值对服务器列表的大小进行取模运算，得到的结果便是要访问的服务器的序号。
优点：保证了相同客户端 IP 地址将会被哈希到同一台后端服务器，直到后端服务器列表变更。根据此特性可以在服务消费者与服务提供者之间建立有状态的 Session 会话。
URI 哈希(URI Hashing)法 HAProxy 中实现的一个负载均衡算法。支持部分 URI（问号之前）和完整 URI 两种模式。
这个算法可以把同一个 URI 的访问发送到同一台服务器上，以最大程度提高缓存命中率。
该算法支持两个可选参数 len 和 depth，后跟一个正整数。仅在需要基于URI的开头来平衡服务器时，这些选项可能会很有用。 len 参数指示算法仅应考虑URI开头的许多字符来计算哈希。请注意，将 len 设置为 1 几乎没有意义，因为大多数URI都以前导 / 开头。
depth 参数指示用于计算哈希的最大目录深度。请求中的每个斜杠都计为一个级别。如果同时指定了两个参数，则在达到任意一个参数时都将停止评估。
