覃超的《算法训练营》课程学习已接近尾声，通过这段时间的学习及训练，对数据结构和算法的认知进一步加深。从业务系统的CURD下沉到底层的数据结构和算法，回顾这些知识给我最大的感触是：这些数据结构和算法科学家/专家非常伟大。
今天用一些时间总结课程里关于“树”的知识。读者需要注意的是，对于下文中提到的几种“树”，这里只做简单的介绍、小结。详细的推理和证明建议有兴趣的读者可以查阅详细的资料，本文就不再花费大量篇幅去拷贝各位科学家的论文。提示：本文里有些超链接需要自备科学上网工具才可访问。
树（Tree）
- Root：根节点
- Parent Node：父节点
- Child Node：孩子节点
- Left Node：叶子节点
- Sub-tree：子树
二叉树（Binary Tree）
二叉树每个父节点最多拥有两个孩子节点，有如下三种遍历顺序：
1. 前序遍历（Pre-order）：根 -> 左 -> 右
// sample code
public void preorder(List<Integer> res, Node root) {
// terminator
if (root == null) return;
// business
res.add(root.val);
preorder(res, root.left);
preorder(res, root.right);
}
复制代码2. 中序遍历（In-order）：左 -> 根 -> 右
// sample code
public void preorder(List<Integer> res, Node root) {
// terminator
if (root == null) return;
// business
preorder(res, root.left);
res.add(root.val);
preorder(res, root.right);
}
复制代码3. 后序遍历（Post-order）：左 -> 右 -> 根
// sample code
public void preorder(List<Integer> res, Node root) {
// terminator
if (root == null) return;
// business
preorder(res, root.left);
preorder(res, root.right);
res.add(root.val);
}
复制代码二叉搜索树（Binary Search Tree）
二叉搜索树，也称二叉搜索树、有序二叉树（Ordered Binary Tree）、排序二叉树（Sorted Binary Tree），是指一颗空树或具有下列性质的二叉树：
- 左子树上
所有节点的值均小于它的根节点的值； - 右子树上
所有节点的值均大于它的根节点的值； - 以此类推：左、右子树也分别为二叉搜索树（这就是重复性）。
注意：二叉搜索树中序遍历的结果是升序排列。
下面我们来思考下面这幅图，找出红色节点所有的时间复杂度是多少？
在上图这个二叉搜索树中找出红色节点所有的时间复杂度是O(log2N)，这里的2为底数，N为节点数量。
如果出现下图的极端情况，退化成了一个线性的结构，那么找出最底部的节点，其时间复杂度是多少？
在上图的线性结构中找出最底部节点的时间复杂度是O(N)，N为节点数量。
从上面的现象可以得出这样的结论：需要保证二维维度，让左右子树节点平衡。
从维基百科Self-balancing binary search tree可以详细查看实现了上述结论的几种树。
- 2–3 tree
- AA tree
- AVL tree
- B-tree
- Red–black tree
- Scapegoat tree
- Splay tree
- Tango tree
- Treap
- Weight-balanced tree
AVL树
AVL树的每个节点都有其平衡因子，以平衡因子判断子树是否要通过旋转操作（有四种旋转操作）来进行平衡。
Balance Factor（平衡因子）：某父节点的左子树高度减去它的右子树高度（有时候右子树减去左子树）。平衡因子有三个值可取，分别是-1, 0, 1。如果某个节点的平衡因子不属于这三个值其中之一，就需要对其和其子树进行旋转操作。
下图是一个AVL树，绿色的数字代表其节点的平衡因子。
当增加一个数值为14的节点，该树的平衡因子变为下图。
当增加一个数值为3的节点，该树的平衡因子变为下图。
此时数值为10的节点的平衡因子已经不是-1, 0, 1的其中一个了，而是-2，就需要对其和其子树进行旋转操作。
如何进行旋转操作？首先介绍四种旋转，最后再对结合上图具体说明使用哪种旋转方法。
1. 左旋
当子树状态为右右子树（某父节点仅有单一的右子树，且该右子树也仅有单一的右子树），就对其进行左旋，如下图（图中左边为右右子树状态，右边为旋转后的状态）。
2. 右旋
当子树状态为左左子树（某父节点仅有单一的左子树，且该左子树也仅有单一的左子树），就对其进行右旋，如下图（图中左边为左左子树状态，右边为旋转后的状态）。
3. 左右旋
当子树状态为左右子树（某父节点仅有单一的左子树，且该左子树仅有单一的右子树），就对其进行左右旋，如下二张图。
首先对左右子树进行左旋，让其成为左左子树。
再对左左子树进行右旋。
4. 右左旋
当子树状态为右左子树（某父节点仅有单一的右子树，且该左子树仅有单一的左子树），就对其进行右左旋，如下二张图。
首先对右左子树进行右旋，让其成为右右子树。
再对右右子树进行左旋。
上面介绍的四种旋转操作的简图没将子树画出来。带有子树旋转链接1/链接2的示意图可参考下图。
旋转操作例题1
介绍完四种旋转操作后，回到前面提到的一个AVL树：「当增加一个数值为3的节点，该树的平衡因子变为下图。」
此时数值为10的节点的平衡因子已经不是-1, 0, 1的其中一个了，而是-2，就需要对其和其子树进行旋转操作。
因为对数值为10的节点属于左左子树的状态，所以需要对其进行右旋，如下图。
参考上面带子树旋转的示意图可知，旋转后要将数值为5的节点的子树（8）挂载到数值为10的节点下。旋转后的结果如下图。
旋转操作例题2
一个AVL树的平衡因子如下图。
当增加数值为15的节点，其平衡因子变为下图。
此时数值为9的节点和数值为7的节点的平衡因子已经不是-1, 0, 1的其中一个了，而是+2，就需要对其和其子树进行旋转操作。
我们对层数更高的数值为9的节点进行旋转操作，其属于左右子树的状态，所以需要对其进行左右旋，首先对其进行右旋，如下两张图。
右旋后的结果如下图。
再对其进行左旋，如下两张图。
左旋后的结果如下图。
AVL树小结
- 它是平衡二叉树;
- 每个节点存balance factor = {-1, 0, 1};
- 四种旋转操作。
得益于AVL树的数据结构，每个节点的左右子树高度差不超过1，极端境况的时间复杂度也非常接近O(log2N)，因此它的查询效率比较高。但也因此带来了一些不足之处：节点需要存储额外信息（平衡因子），且调整次数频繁，因此出现了红黑树。
红黑树
红黑树是一种近似平衡的二叉搜索树（BinarySearch Tree），它能够确保任何一个节点的左右子树的高度差小于两倍。具体来说，红黑树是满足如下条件的二叉搜索树：
- 每个节点要么是红色，要么是黑色
- 根节点是黑色
- 每个叶节点（NIL节点，空节点）是黑色的。
- 不能有相邻接的两个红色节点
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
关键性质：从根节点到叶子节点的最长的可能路径不多于最短的可能路径的两倍。
最后有个AVL树和红黑树的概述和比较，如下图。
- AVL树的查询效率比红黑树高，因为AVL树更严格的平衡。上面提到的AVL树的左右子树高度差不超过1，而红黑树从根节点到叶子节点的最长的可能路径不多于最短的可能路径的两倍。
- 红黑树的插入和删除效率比AVL高，因为红黑树是一个近似平衡树。AVL树如果增加/删除节点会因为
平衡因子的变化而进行更多的旋转操作。 - AVL树存的信息要比红黑树更多，所以AVL树额外的消耗空间要比红黑树多。AVL要存
平衡因子和树的高度，而红黑树只要存一个bit来存0或1表示是黑还是红。 - 红黑树一般使用在高级语言（Java, C++ ...）里面的map结构比较多，AVL树在数据库里的使用更多。因为根据上面的结论，如果写操作比较多或者读/写操作一半一半的时候，用红黑树即可，所以用在高级语言里的map比较多。而数据库往往是读操作多于写操作，所以一般是用AVL树。
近期评论