好长一段时间没有看《数据结构与算法之美》系列了，现在重归树这一章节，这里的内容会比较多，也不会太容易理解，尤其后面涉及到 红黑树的地方。事实上，如果你完全掌握了红黑树，对你理解Linux的很多知识也会有帮助，比如我们常说的epoll这个系统调用，内部的 实现就强依赖于红黑树。
首先提出关于树的几个比较相似的概念：这里一定要随时给自己刻画一个概念，一棵树是有很多子树的。
- 1） 高度（Height）：节点的高度—>节点到叶子节点的最长路径（边数），树的高度就是根节点的高度
- 2） 深度（Depth）：节点的深度—>根节点到该节点所经历的边数
- 3） 层（Level）：节点的层数—>节点的深度 + 1，即根节点为第1层。
二叉树，即每个节点最多只有两个子节点。二叉树的主要两个概念是满二叉树和完全二叉树。
- （1） 满二叉树：指除了叶子节点以外，每个节点都有左右两个子节点。叶子节点都在最后一层
- （2） 完全二叉树：叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层以外，其他层的节点个数都要达到最大。这个概念可能不那么容易理解，后面会有一个完全二叉树的数学概念， 非常容易想明白。
一个问题，如何表示（存储）一棵二叉树？，一般来说有两种方法：
- 1） 基于指针或者引用的二叉链式存储法，也就是和链表类似，每一个节点除了数据以外，还保存了左右两个子节点的引用，这也是最常用的方式，绝大部分二叉树代码都是这样实现的。
- 2） 基于数组的顺序存储法。注意上面的链式并不要求节点在地址空间上连续，但是基于数组存储则需要，因为我们要使用到数组的 随机访问特性：将根节点存储在下标i = 1的位置，左子节点存储在2 * i = 2的位置，右子节点存储在2 * i + 1 = 3的位置，以此 类推。这样将每个节点存储起来，节点之间不需要引用，但是依赖于我们约定的这种规则。 对于上述的基于数组的顺序存储方式，当一棵树满足完全二叉树的条件时，我们仅仅会浪费一个存储空间，即第0个位置。如果不满足 完全二叉树的条件，只是一棵普通的二叉树的话，则会浪费许多的存储空间，数组存储就不再适用了。所以结论便是：如果一棵树是完全 二叉树的话，那么非常适合使用数组来存储，后续会看到，堆其实就是一种完全二叉树。
二叉树的遍历：前序中序和后续，主要是看当前节点是否在左子节点之前遍历，根—>左—>右，这样就是前序遍历。这三种遍历方式 我们都常用递归的方式，代码本质上都很简单，需要注意的是，二叉树的遍历时间复杂度都是O(n)，参考如下：
- （1） 前序遍历：
public static void beforeSearch(TreeNode root) {
if (root == null) return;
System.out.print(root.data + "-");
beforeSearch(root.left);
beforeSearch(root.right);
}
- （2） 中序遍历：
public static void middleSearch(TreeNode root) {
if (root == null) return;
middleSearch(root.left);
System.out.print(root.data + "-");
middleSearch(root.right);
}
- （3） 后序遍历：
public static void afterSearch(TreeNode root) {
if (root == null) return;
afterSearch(root.left);
afterSearch(root.right);
System.out.print(root.data + "-");
}
- （4） 层次遍历：层次遍历要稍微复杂一点，需要借用一个队列来操作，先将根节点入队列，然后在循环中不断出队，针对不为空的子节 点，依次入队。
public static void levelSearch(TreeNode root) {
Deque<TreeNode> nodeQueue = new ArrayDeque<>();
nodeQueue.add(root);
while (!nodeQueue.isEmpty()) {
TreeNode node = nodeQueue.remove();
System.out.println(node.data);
if (node.left != null) {
nodeQueue.add(node.left);
}
if (node.right != null) {
nodeQueue.add(node.right);
}
}
}
二叉查找树
二叉查找树是被设计出来用来同时支持**高效地添加、删除、查找元素的一个数据结构，其实前面提到过，散列表也支持这些操作， 并且时间复杂度只有O(1)，已经足够高效了，那使用二叉查找树的场景是什么呢？事实上，在学习HashMap的时候，我们了解到在哈希 碰撞激烈后，链表会升级成红黑树，这就是因为当你哈希碰撞激烈后，查找的时间复杂度会退化为去遍历一个链表，就不高效了。
二叉查找树，也叫二叉搜索树，它和我们普通二叉树的区别在于：它约束了对于树中的每一个节点，其左子树的每个节点的值都要小于当前节点值， 右子树的每个节点的值都要大于当前节点值，换句话说，它的中序遍历后生成的结果是自然升序的。下面我们依次看一下二叉查找树的查找、添加和 删除节点的操作。
1、查找
二叉查找树的查找过程本质上就是一个二分，先和根节点作比较，根据大小关系判断去左子树或者右子树里面查找，比较简单。使用 递归或者非递归的方式都比较容易实现。这里不再写代码了。
2、插入
二叉树的新插入的数据一般都在叶子节点上，本质上，也是从根节点开始，比较待插入节点数据和根节点数据的大小关系，依次在 左子树或者右子树中进行插入操作，规则如下：
- （1）如果树为空，则直接将节点设置为根节点，返回即可。
- （2）如果待插入的数据大于根节点数据，并且根节点的右子节点为空，则将新数据写入根节点的右子节点位置；如果右子节点不为空， 就再递归遍历右子树，直到找到插入位置。
- （3）如果待插入的数据小于根节点数据，和上面一样的原理，判断根节点的左子节点是否为空，进行相关操作。
按照上述规则，代码如下，应该还比较容易理解：
public static void insert(TreeNode root, int data) {
if (root == null) {
root = new TreeNode(data);
return;
}
TreeNode node = root;
while (node != null) {
if (node.data < data) {
if (node.right == null) {
node.right = new TreeNode(data);
return;
}
node = node.right;
} else {
if (node.left == null) {
node.left = new TreeNode(data);
return;
}
node = node.left;
}
}
}
3、删除
从一个二叉查找树中删除一个节点，就会比较复杂了，因为你删除的可能是一个叶子节点（最简单的情况，直接删除即可），也可能是一个非叶子节点，这样还需要看这个节点的左右子节点是否为空。针对要删除 的节点的子节点数目，主要分为以下几种情况讨论：
- 1） 待删除的节点没有子节点，即是一个叶子节点，那么只需要直接将父节点中指向待删除节点的指针置为null即可；
- 2） 待删除的节点只有一个子节点（只有左子节点或者只有右子节点），只需要更新父节点中指向待删除节点的指针，让它指向待删除节点的子节点即可，也还比较简单。
- 3） 待删除的节点有两个子节点（既有左子节点又有右子节点），这种情况会比较复杂。首先，需要找到待删除节点的右子树中最小节点，记为min，将min节点替换到待删除节点上，相当于一次copy操作， 然后再删除原右子树中这个min节点（这个min节点肯定没有左子节点，因为如果有，那它就肯定不是最小节点），所以这一次删除至少可以使用规则2来进行。
上述规则明了后，其实要写出在一棵二叉查找树中删除特定元素的代码并不难，当然涉及到寻找某个节点的父节点等通用操作，代码如下，简单描述一下整个流程：
首先需要找到待删除数据data对应的节点needDeleted，以及其父节点，因为后面会用到这个parent节点，注意这里找的时候，初始值也比较重要，needDeleted初始值就是根节点，从根节点 开始往下找，直到找到了值为data的节点；parent节点的初始值为null，因为当你要删除的节点就是根节点的时候，它的父节点其实是null的；注意while循环的退出条件， 这个while循环很巧妙，它的退出条件是needDeleted.data == data或者needDeleted为空，表示从树中没有找到值为data的节点，或者就找到了。parent节点在这个过程中不断赋值就好。
如果在上一步中没有找到值为data的节点，直接返回即可，如果找到了，就需要根据不同情况进行判断了，判断它的子节点的数目。
先看最复杂的情况，needDeleted节点的左右子节点均不为空，这时候我们需要找到needDeleted节点的右子树中的最小节点（事实上，这里也可以找其左子树中的最大节点），找到这个 min节点以后，将其值赋值到needDeleted上，然后删除min节点即可。注意此时删除min节点，min节点的左子节点必然为空，这一步删除就比较简单，这里需要注意的是，由于要删除min节点， 所以你在这个过程中还需要找到min节点的父节点parentMin节点。
剩下的两种简单情况，我写的代码比较繁杂，事实上是可以简化的，主要就是判断左子节点为空还是右子节点为空，进行相应的赋值即可。
attention：parent节点可能为空，因此下面的代码是可能会抛出NPE的，这种情况发生的条件是：待删除节点是跟节点，其左子节点和右子节点至少有一个为空的时候，parent此时也为 null，可能抛异常，因此还需要特殊处理
public static void delete(TreeNode root, int data) {
if (root == null) {
return;
}
TreeNode needDeleted = root;
TreeNode parent = null;
while (needDeleted != null && needDeleted.data != data) {
parent = needDeleted;
if (needDeleted.data < data) {
needDeleted = needDeleted.right;
} else {
needDeleted = needDeleted.left;
}
}
if (needDeleted == null) return;//没找到待删除的元素，直接返回即可，这是上面while循环break的一个条件
//左右子节点都不为空，则需要找到右子树中最小节点，将最小节点元素copy到待删除节点上，然后移除右子树中的最小节点
if (needDeleted.left != null && needDeleted.right != null) {
//找到min节点，以及其父节点
TreeNode min = needDeleted.right;
TreeNode parentMin = needDeleted;
while (min.left != null) {
parentMin = min;
min = min.left;
}
//经过上述遍历，min节点即是右子树中的最小节点，将min节点的值赋值给待删除节点
//而，parentMin是min节点的父节点
needDeleted.data = min.data;
//移除min节点，注意此时min节点的左子节点必然为空，就看min节点是parentMin的左子节点还是右子节点了；
// 这里为什么可能是右子节点：needDeleted.right本身就是右子树中的最小节点
if (parentMin.left == min) {
parentMin.left = min.right;
} else if (parentMin.right == min) {
parentMin.right = min.right;
}
return;
}
if (needDeleted.left == null && needDeleted.right == null) {
if (parent.left == needDeleted) {
parent.left = null;
} else {
parent.right = null;
}
return;
}
if (needDeleted.left != null) {
if (parent.left == needDeleted) {
parent.left = needDeleted.left;
} else if (parent.right == needDeleted){
parent.right = needDeleted.left;
}
return;
}
if (parent.left == needDeleted) {
parent.left = needDeleted.right;
} else if (parent.right == needDeleted){
parent.right = needDeleted.right;
}
return;
}
4、求一棵二叉树的高度
用递归的思路，求二叉树的高度会比较简单，代码如下，这里有一个疑问：只有一个节点的树的高度是1还是0，为了和空树区分开，认为应该是1
public static int computeHeight(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(computeHeight(root.right), computeHeight(root.left)) + 1;
}
上述递归的思路实际上是深度优先算法，DFS。还有一种广度优先的算法，BFS，利用到了上面写的层次遍历的思路，但是具体过程需要深度理解，广度优先算法往往都需要利用到一些外部的 数据结构（队列or栈）来辅助我们，存储一些中间过程的数据。这里的核心思想就是这个队列，必须要理解，下面这个代码就是 广度优先算法遍历或者操作一棵树的公共思路，都是需要一个队列来辅助。 代码如下：
public static int getHeight(TreeNode root) {
int result = 0;
Deque<TreeNode> nodeQueue = new ArrayDeque<>();
nodeQueue.add(root);
//while循环控制层数
while (!nodeQueue.isEmpty()) {
result++;
int size = nodeQueue.size(); //这一步非常重要，size记录的就是当前层的节点数目
for (int i = 0; i < size; i++) { //for循环中，去遍历每一层的所有节点。
TreeNode node = nodeQueue.remove();
if (node.left != null) {
nodeQueue.add(node.left);
}
if (node.right != null) {
nodeQueue.add(node.right);
}
}
}
return result;
}
实际上，对于删除操作，还有一个比较取巧的方法，就是在删除时仅对该节点做一个标记，标记为已删除，但是并不真正的移动这些 节点的指针，这样做的好处就是删除操作变得很简单，但是会浪费存储空间。
4、时间复杂度
很显然，在最坏情况下的一棵二叉查找树，根节点的左右子树极度不平衡，树已经退化为链表了，这时它的查找、插入和删除的时间复杂 度都是O(n)，很不高效；但是在一棵满二叉树或者完全二叉树下，查找，插入和删除的时间复杂度仅是O(log(n))，非常高效。
所以我们现在的目标就转化了，构建一棵不管怎么插入和删除数据，都尽量保持任意节点的左右子树比较平衡的二叉查找树——— 平衡二叉查找树，平衡二叉查找树的高度接近O(log(n))，对于n个节点的树，因此其查找，插入和删除的性能都比较稳定。
支持重复数据的二叉查找树
前面我们描述的二叉查找树都是默认认为元素并不会重复，查找到了就直接返回，并不考虑会有重复元素的情况，而实际上这种情况也 是会出现的，一般也有两种方法来解决这个问题：
- 1） 借鉴哈希表使用链表法解决哈希冲突的思想，二叉查找树的每一个节点不仅仅存储一个元素，而是存储了一个链表，这个链表将 值相同的所有元素都串起来，每个节点存储的都是值相同的元素。
- 2） 第二种方法更加优雅：每个节点仍然存储一个元素，在插入一个重复的元素时，我们总是将这个元素插入到相等值节点的右子树中， 也就是把新插入的元素当作是大于这个节点的值来处理。这样，查找和删除也会变化，当查找到某个值时，并不能直接停止返回，而是需要 继续在右子树中查找，直到遇到叶子节点，这样就查找出了所有等于值value的节点；当删除某个元素的时候，也需要先查找到等于值的 所有节点，然后依次删除。
问题：相比于散列表，二叉查找树的优势在哪里？
- （1） 散列表中的数据是无序存储的，如果要有序，需要其他数据结构辅助；而二叉查找树中序遍历就是有序的；
- （2） 散列表扩容耗时较多，遇到散列冲突时性能不稳定；但是在工程中我们常用的平衡二叉查找树性能稳定，时间复杂度稳定在 O(log(n))；
- （3） 散列表的设计更加复杂，需要考虑散列函数的设计，冲突解决办法，扩容缩容策略等，平衡二叉查找树只需要考虑维护平衡 性这一个问题，其解决方案很成熟。
平衡二叉查找树
定义：何为平衡？对于树中的任意一个节点，它的左子树和右子树的高度相差不能大于1，前面我们说到的，满二叉树和完全 二叉树都是平衡二叉树。那平衡 + 二叉查找就是在普通的二叉查找树上增强了概念。
最先被发明的平衡二叉查找树是AVL树，在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。 查找、插入和删除在平均和最坏情况下的时间复杂度都是O(log(n))。增加和删除元素的操作则 可能需要借由一次或多次树旋转，以实现树的重新平衡。
节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。 带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。
事实上，上面是平衡二叉查找树的严格定义，我们用的最多的平衡二叉查找树是传说中的红黑树，但是红黑树并不严格 符合上面的定义，它从根节点到叶子节点的最长路径可能是最短路径的一倍多。这里王争提出不用死抠平衡的定义，而是回到发明 平衡二叉查找树的初衷来，即解决普通二叉查找树在频繁的插入、删除等动态更新的情况下，出现时间复杂度退化的问题。
平衡二叉查找树其实有很多，比如，Splay Tree（伸展树）、Treap（树堆）等，但是我们提到平衡二叉查找树，听到的 基本都是红黑树。它的出镜率甚至要高于“平衡二叉查找树”这几个字，有时候，我们甚至默认平衡二叉查找树就是红黑树。
一棵红黑树的定义，或者说其约束如下：
- 1） 所有节点，要么是黑色，要么是红色；
- 2） 根节点是黑色的；
- 3） 每个叶子节点都是黑色的空节点（null），即叶子节点不存储数据，且为黑色（这个要求主要是为了简化红黑树的实现）；
- 4） 任何相邻的节点不能同时是红色的，也就是说，红色节点是被黑色节点隔开的；
- 5） 每个节点，从该节点到达其可达叶子节点的所有路径，其包含的相同数目的黑色节点。
这里王争简单从红黑树的定义分析了红黑树的时间复杂度为什么近似是O(log(n))，可以再理解一下。我们前面提到Treap、 Splay Tree，绝大部分情况下，它们操作的效率都很高，但是也无法避免极端情况下时间复杂度的退化。尽管这种情况出现的概率 不大，但是对于单次操作时间非常敏感的场景来说，它们并不适用。
AVL树是一种高度平衡的二叉树，所以查找的效率非常高，但是，有利就有弊，AVL树为了维持这种高度的平衡，就要付出更多 的代价。每次插入、删除都要做调整，就比较复杂、耗时。所以，对于有频繁的插入、删除操作的数据集合，使用AVL树的代价就有 点高了。
红黑树只是做到了近似平衡，并不是严格的平衡，所以在维护平衡的成本上，要比AVL树要低。所以，红黑树的插入、删除、查 找各种操作性能都比较稳定。对于工程应用来说，要面对各种异常情况，为了支撑这种工业级的应用，我们更倾向于这种性能稳定的 平衡二叉查找树。
红黑树
重在理解，即使记不住左旋右旋，也无所谓，重在思想。这一章节暂时不看，可以配合着《算法》一书中的2-3-4树和红黑树 章节一起看，那本书讲的也比较细。