前言：数据结构第五弹笔记来袭！主要内容为二叉树、红黑树及堆排序。

二叉树基础

（1）二叉树的节点:根节点、父子节点、兄弟节点、叶子节点
（2）高度：从下往上、深度：从上往下、层。如3,3,4
（3）满二叉树、完全二叉树（最后一层叶子节点靠左排列、其它层节点个数达到最大）。完全二叉树适用于顺序存储法
（4）链式存储法：每个节点包含数据、左、右子节点的指针，顺序存储：以数组方式存，可能有空闲位置
（5）二叉树遍历：前序遍历（自左右）、中序遍历（左自右）、后序遍历（左右自）。均可用递归实现。
（6）二叉查找树，左节点小于父节点，右节点大于父节点。
（7）二叉查找树插入：按左小右大的规律插入。
（8）二叉查找树删除：三种情况。要删除的节点没有子节点、要删除的节点只有一个子节点、要删除的节点有两个子节点。
（9）中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度为O(n)。
（10）支持重复数据的二叉查找树。第一种方法，相同数据存储在同一节点上，通过链表和支持动态扩容的数据结构。第二种方法，不存在同一节点，但是遇到相同就放到右子树中，当做大于等于处理。
（11）二叉查找树时间复杂度分析。极端情况退化成链表，O(n)。其他情况其实是与树的高度成正比，增删查为O(logn)。

红黑树基础

（1）定义：根节点是黑色的；
每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据（为了代码实现方便）；
任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；
（2）红黑树是近似平衡的。“平衡”的意思可以等价为性能不退化。“近似平衡”就等价为性能不会退化的太严重。
二叉查找树很多操作的性能都跟树的高度成正比。一棵极其平衡的二叉树（满二叉树或完全二叉树）的高度大约是 log2n，所以如果要证明红黑树是近似平衡的，我们只需要分析，红黑树的高度是否比较稳定地趋近 log2n 就好了。
（3）AVL树了解。AVL 树是一种高度平衡的二叉树，查找的效率非常高，但是，每次插入、删除都要做调整，就比较复杂、耗时。对于有频繁的插入、删除操作的数据集合，使用 AVL 树的代价就有点高了。
（4）红黑树是一种平衡二叉查找树。它是为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的。红黑树的高度近似 log2n，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是 O(logn)。
（5）平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于 1。

红黑树平衡

（1）红黑树的平衡过程跟魔方复原非常神似，大致过程就是：遇到什么样的节点排布，我们就对应怎么去调整。只要按照这些固定的调整规则来操作，就能将一个非平衡的红黑树调整成平衡的。
（2）左旋、右旋的定义。无论是左旋还是右旋，被旋转的树，在旋转前是二叉查找树，并且旋转之后仍然是一颗二叉查找树。
对x进行左旋，意味着，将“x的右孩子”设为“x的父亲节点”；即，将 x变成了一个左节点(x成了为z的左孩子)！。 因此，左旋中的“左”，意味着“被旋转的节点将变成一个左节点”。
对x进行右旋，意味着，将“x的左孩子”设为“x的父亲节点”；即，将 x变成了一个右节点(x成了为y的右孩子)！ 因此，右旋中的“右”，意味着“被旋转的节点将变成一个右节点”。
（3）正在处理的节点叫做关注节点。
（4）插入操作的平衡调整比较简单，但是删除操作就比较复杂。针对删除操作，我们有两次调整，第一次是针对要删除的节点做初步调整，让调整后的红黑树继续满足第四条定义，“每个节点到可达叶子节点的路径都包含相同个数的黑色节点”。但是这个时候，第三条定义就不满足了，有可能会存在两个红色节点相邻的情况。第二次调整就是解决这个问题，让红黑树不存在相邻的红色节点。

递归树

（1）归并排序：总的时间复杂度 O(n∗h)。满二叉树的高度大约是 log2n。所以，归并排序递归实现的时间复杂度就是 O(nlogn)。
快速排序：每次分区并不是均匀地一分为二，所以递归树并不是满二叉树。快排的平均时间复杂度就是 O(nlogn)。
（2）斐波那契数列：算法的时间复杂度就介于 O(2n) 和 O(22n) 之间。
（3）全排列的时间复杂度：时间复杂度大于 O(n!)，小于 O(n∗n!)。

堆排序基础

（1）快速排序，平均情况下，它的时间复杂度也为 O(nlogn)。尽管这两种排序算法的时间复杂度都是 O(nlogn)，甚至堆排序比快速排序的时间复杂度还要稳定，但是，在实际的软件开发中，快速排序的性能要比堆排序好。
（2）堆是一种特殊的树。堆是一个完全二叉树；堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。
（3）大顶堆和小顶堆。对于每个节点的值都大于等于子树中每个节点值的堆，我们叫作“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫作“小顶堆”。
（4）堆的操作。堆中插入一个元素和删除堆顶元素。
插入：把新插入的元素放到堆的最后，之后可能出现不符合堆的特性情况，需要进行堆化。堆化实际上有两种，从下往上和从上往下。
删除：堆顶元素存储的就是堆中数据的最大值或者最小值。当我们删除堆顶元素之后，就需要把第二大的元素放到堆顶，那第二大元素肯定会出现在左右子节点中。然后我们再迭代地删除第二大节点，以此类推，直到叶子节点被删除。
（5）堆化的过程是顺着节点所在路径比较交换的，所以堆化的时间复杂度跟树的高度成正比，也就是 O(logn)。插入数据和删除堆顶元素的主要逻辑就是堆化，所以，往堆中插入一个元素和删除堆顶元素的时间复杂度都是 O(logn)。
（6）堆排序方法的时间复杂度非常稳定，是 O(nlogn)，并且它还是原地排序算法。大致分解成两个大的步骤，建堆和排序。
（7）建堆的两种方法。
第一种建堆思路的处理过程是从前往后处理数组数据，并且每个数据插入堆中时，都是从下往上堆化。
第二种实现思路，是从后往前处理数组，并且每个数据都是从上往下堆化，因为叶子节点往下堆化只能自己跟自己比较，所以我们直接从第一个非叶子节点开始，依次堆化就行了，建堆的时间复杂度就是 O(n)。
（8）排序：建堆结束之后，数组中的数据已经是按照大顶堆的特性来组织的。数组中的第一个元素就是堆顶，也就是最大的元素。我们把它跟最后一个元素交换，那最大元素就放到了下标为 n 的位置。这个过程有点类似上面讲的“删除堆顶元素”的操作，当堆顶元素移除之后，我们把下标为 n 的元素放到堆顶，然后再通过堆化的方法，将剩下的 n−1 个元素重新构建成堆。堆化完成之后，我们再取堆顶的元素，放到下标是 n−1 的位置，一直重复这个过程，直到最后堆中只剩下标为 1 的一个元素，排序工作就完成了。
（9）建堆过程的时间复杂度是 O(n)，排序过程的时间复杂度是 O(nlogn)，所以，堆排序整体的时间复杂度是 O(nlogn)。
注意：堆排序不是稳定的排序算法，因为在排序的过程，存在将堆的最后一个节点跟堆顶节点互换的操作，所以就有可能改变值相同数据的原始相对顺序。
（10）快速排序和堆排序比较。堆排序数据访问的方式没有快速排序友好。对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序。

堆排序应用

（1）场景：热门榜 Top 10 的搜索关键词、求 Top K 和求中位数。
（2）优先级队列：数据的出队顺序不是先进先出，而是按照优先级来，优先级最高的，最先出队。用堆实现。
优先级队列使用：合并有序小文件、高性能定时器（执行定时任务）
（3）利用堆求 Top K：问题抽象成两类。一类是针对静态数据集合，也就是说数据集合事先确定，不会再变。另一类是针对动态数据集合，也就是说数据集合事先并不确定，有数据动态地加入到集合中。静态数据，时间复杂度就是 O(nlogK)。
（4）求中位数。动态数据集合，中位数在不停地变动。维护两个堆，一个大顶堆，一个小顶堆。大顶堆中存储前半部分数据，小顶堆中存储后半部分数据，且小顶堆中的数据都大于大顶堆中的数据。
如果有n个数据，n是偶数，我们从小到大排序，那前2/n个数据存储在大顶堆中，后2/n个数据存储在小顶堆中。这样，大顶堆中的堆顶元素就是我们要找的中位数。如果n是奇数，情况是类似的，大顶堆就存储2/n+1个数据，小顶堆中就存储2/n个数据。
（5）99%响应时间问题。类似求中位数。