# 二叉树 ## 树 比如下面这幅图，A 节点就是 B 节点的父节点，B 节点是 A 节点的子节点。B、C、D 这三 个节点的父节点是同一个节点，所以它们之间互称为兄弟节点。我们把没有父节点的节点叫 作根节点，也就是图中的节点 E。我们把没有子节点的节点叫作叶子节点或者叶节点，比如 图中的 G、H、I、J、K、L 都是叶子节点。 ![tree.png](/images/tree.png) ![tree_gainian.png](/images/tree_gainian.png) ## 二叉树 二叉树，顾名思义，每个节点最多有两个“叉”，也就是两个子节点，分别是**左子节点**和**右 子节点**。 二叉树中，叶子节点全都在最底层，除了叶子节点之外，每个节点都有左 右两个子节点，这种二叉树就叫作**满二叉树**。 二叉树中，叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除 了最后一层，其他层的节点个数都要达到最大，这种二叉树叫作**完全二叉树**。 ## 二叉树的遍历 遍历方式 ![bianli_tree.png](/images/bianli_tree.png) ``` //前序遍历 void preOrder(Node* root) { if (root == null) return; print root // 此处为伪代码，表示打印 root 节点 preOrder(root->left); preOrder(root->right); } //中序遍历 void inOrder(Node* root) { if (root == null) return; inOrder(root->left); print root // 此处为伪代码，表示打印 root 节点 inOrder(root->right); } //后序遍历 void postOrder(Node* root) { if (root == null) return; postOrder(root->left); postOrder(root->right); print root // 此处为伪代码，表示打印 root 节点 } ``` ## 二叉查找树（Binary Search Tree） 二叉查找树要求，在树中的任意一个节点，其左子树 中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。 ### 查找操作 首先，我们看如何在二叉查找树中查找一个节点。我们先取根节点，如果它等于我们要查找 的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要 查找的数据比根节点的值大，那就在右子树中递归查找。 ``` public class BinarySearchTree { private Node tree; public Node find(int data) { Node p = tree; while (p != null) { if (data < p.data) p = p.left; else if (data > p.data) p = p.right; else return p; } return null; } public static class Node { private int data; private Node left; private Node right; public Node(int data) { this.data = data; } } } ``` ### 插入操作 如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点 的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节 点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再 递归遍历左子树，查找插入位置。 ``` public void insert(int data) { if (tree == null) { tree = new Node(data); return; } Node p = tree; while (p != null) { if (data > p.data) { if (p.right == null) { p.right = new Node(data); return; } p = p.right; } else { // data < p.data if (p.left == null) { p.left = new Node(data); return; } p = p.left; } } } ``` ### 删除操作 ``` public void delete(int data) { Node p = tree; // p 指向要删除的节点，初始化指向根节点 Node pp = null; // pp 记录的是 p 的父节点 while (p != null && p.data != data) { pp = p; if (data > p.data) p = p.right; else p = p.left; } if (p == null) return; // 没有找到 // 要删除的节点有两个子节点 if (p.left != null && p.right != null) { // 查找右子树中最小节点 Node minP = p.right; Node minPP = p; // minPP 表示 minP 的父节点 while (minP.left != null) { minPP = minP; minP = minP.left; } p.data = minP.data; // 将 minP 的数据替换到 p 中 p = minP; // 下面就变成了删除 minP 了 pp = minPP; } // 删除节点是叶子节点或者仅有一个子节点 Node child; // p 的子节点 if (p.left != null) child = p.left; else if (p.right != null) child = p.right; else child = null; if (pp == null) tree = child; // 删除的是根节点 else if (pp.left == p) pp.left = child; else pp.right = child; } ``` ### 其他操作 支持快速地查找最大节点和最小节 点、前驱节点和后继节点。 {{< admonition >}} 重要的特性，就是中序遍历二叉查找树， 可以输出有序的数据序列，时间复杂度是 O(n)，非常高效 {{}} ## 支持重复数据的二叉查找树 针对的都是不存在键值相同的情况。那如果存储的两个对 象键值相同，这种情况该怎么处理呢？ 第一种方法比较容易。二叉查找树中每一个节点不仅会存储一个数据，因此我们通过链表和 支持动态扩容的数组等数据结构，把值相同的数据都存储在同一个节点上。 第二种方法比较不好理解，不过更加优雅。 每个节点仍然只存储一个数据。在查找插入位置的过程中，如果碰到一个节点的值，与要插 入数据的值相同，我们就将这个要插入的数据放到这个节点的右子树，也就是说，把这个新 插入的数据当作大于这个节点的值来处理。 当要查找数据的时候，遇到值相同的节点，我们并不停止查找操作，而是继续在右子树中查 找，直到遇到叶子节点，才停止。这样就可以把键值等于要查找值的所有节点都找出来 对于删除操作，我们也需要先查找到每个要删除的节点，然后再按前面讲的删除操作的方 法，依次删除。 ## 什么是“平衡二叉查找树”？ 平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于 1。 平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比 较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说 低一些，相应的插入、删除、查找等操作的效率高一些。 ## 如何定义一棵“红黑树”？ 红黑树的英文是“Red-Black Tree”，简称 R-B Tree。它是一种不严格的平衡二叉查找 树 一棵红黑 树还需要满足这样几个要求： * 根节点是黑色的； * 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据； * 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的； * 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点； ## 为什么说红黑树是“近似平衡”的？ 平衡”的意思可以等价为性能不退化。“近似平衡”就等价为性能不会 退化的太严重。 二叉查找树很多操作的性能都跟树的高度成正比。一棵极其平衡的二叉 树（满二叉树或完全二叉树）的高度大约是 log2n，所以如果要证明红黑树是近似平衡的， 我们只需要分析，红黑树的高度是否比较稳定地趋近 log2n 就好了。 首先，我们来看，如果我们将红色节点从红黑树中去掉，那单纯包含黑色节点的红黑树的高 度是多少呢？ 红色节点删除之后，有些节点就没有父节点了，它们会直接拿这些节点的祖父节点（父节点 的父节点）作为父节点。所以，之前的二叉树就变成了四叉树。 前面红黑树的定义里有这么一条：从任意节点到可达的叶子节点的每个路径包含相同数目的 黑色节点。我们从四叉树中取出某些节点，放到叶节点位置，四叉树就变成了完全二叉树。 所以，仅包含黑色节点的四叉树的高度，比包含相同节点个数的完全二叉树的高度还要小。 **我们现在知道只包含黑色节点的“黑树”的高度，那我们现在把红色节点加回去，高度会变 成多少呢？** 在红黑树中，红色节点不能相邻，也就是说，有一个 红色节点就要至少有一个黑色节点，将它跟其他红色节点隔开。红黑树中包含最多黑色节点 的路径不会超过 log2n，所以加入红色节点之后，最长路径不会超过 2log2n，也就是说， 红黑树的高度近似2log2n ## 实现红黑树的基本思想 ### 插入操作的平衡调整 红黑树规定，插入的节点必须是红色的。而且，二叉查找树中新插入的节点都是放在叶子节 点上。所以，关于插入操作的平衡调整，有这样两种特殊情况，但是也都非常好处理。 * 如果插入节点的父节点是黑色的，那我们什么都不用做，它仍然满足红黑树的定义。 * 如果插入的节点是根节点，那我们直接改变它的颜色，把它变成黑色就可以了 除此之外，其他情况都会违背红黑树的定义，于是我们就需要进行调整，调整的过程包含两 种基础的操作：**左右旋转和改变颜色** #### CASE 1：如果关注节点是 a，它的叔叔节点 d 是红色 1. 将关注节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑色； 2. 将关注节点 a 的祖父节点 c 的颜色设置成红色； 3. 关注节点变成 a 的祖父节点 c； 4. 跳到 CASE 2 或者 CASE 3。 #### CASE 2：如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的右子节点 1. 关注节点变成节点 a 的父节点 b； 2. 围绕新的关注节点b 左旋； 3. 跳到 CASE 3。 #### CASE 3：如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的左子节点 1. 围绕关注节点 a 的祖父节点 c 右旋； 2. 将关注节点 a 的父节点 b、兄弟节点 c 的颜色互换。 3. 调整结束。 ### 删除操作的平衡调整 #### 1. 针对删除节点初步调整 #### 2. 针对关注节点进行二次调整 ## 递归树与时间复杂度分析 递归的思想就是，将大问题分解为小问题来求解，然后再将小问题分解为小 小问题。这样一层一层地分解，直到问题的数据规模被分解得足够小，不用继续递归分解为 止。 如果我们把这个一层一层的分解过程画成图，它其实就是一棵树。我们给这棵树起一个名 字，叫作**递归树**。 ### 实战一：分析快速排序的时间复杂度 ![kuaipai_diguishu.png](/images/kuaipai_diguishu.png) 快速排序的过程中，每次分区都要遍历待分区区间的所有数据，所以，每一层分区操作所遍 历的数据的个数之和就是n。我们现在只要求出递归树的高度 h,这个快排过程遍历的数据个数 就是 h * n，也就是说，时间复杂度就是 O(h * n) 我们知道，快速排序结束的条件就是待排序的小区间，大小为1,也就是说叶子节点里的数据规模是 1。 从根节点n到叶子节点 1，递归树中最短的一个路径每次都乘以1/10，最长的一个路径每次都乘以9/10. 通过计算，我们可以得到，从根节点到叶子节点的最短路径是 log10n,最长的路径是 log10/9 n ![zuiduianlujing.png](/images/zuiduianlujing.png) 当分区比例是1 : 9时， 快速排序的时间复杂度仍然是 O(n log n) ### 实战二：分析斐波那契的时间复杂度 ![feibonaqi.png](/images/feibonaqi.png) f(n)分解为 f(n-1)和f(n-2)，每次数据规模都是 -1 或者-2.叶子节点的数据规模是 1 或者 2， 所以，从跟节点到叶子节点，每条的路径都是长短不一的 每次分解之后的合并操作只需要一次加法计算，我们把这次加法运算的时间消耗记作 1，从上往下，第一层的总时间消耗为 1， 第二层的总时间消耗为 2，第三层的总时间消耗就是 {{< raw >}} \[ 2^2 \] {{< /raw >}} 依次类推，第 k层的时间消耗就是 2^k-1,那整个算法的总的时间就是每层时间消耗之和 所以，该算法的时间复杂度就介于O(2^n)和O(2^(n/2))之间