深入解析AVL树与红黑树：平衡二叉查找树的旋转与性能优化

什么是 AVL 树？

AVL树是一种平衡二叉搜索树，在添加和删除节点后通过树旋转来重新平衡。右旋转是将某个节点居中，下沉到当前右子节点的位置，让当前左子节点作为新树的根节点，也称为顺时针旋转。同理，左旋转以某个节点为中心，将其下沉到当前左子节点的位置，使当前右子节点成为新树的根节点，也称为逆时针旋转。

什么是红黑树？

红黑树于1972年发明，称为对称二叉B树。 1978年被正式命名为红黑树，主要特点是为每个节点添加一个属性来表示节点颜色，可以是红色或黑色。红黑树与AVL树类似，在插入和删除过程中通过旋转来保持自身的平衡，从而获得更高的搜索性能。与AVL树相比，红黑树不追求所有递归子树的高度差不超过1，并保证从根节点到叶尾的最长路径不超过最短路径的2倍，因此最差时间复杂度为O(logn)。红黑树通过重新着色和左右旋转，更高效地完成插入和删除后的自平衡调整。

红黑树本质上是一棵二叉搜索树，它引入了5个额外的约束：①节点只能是红色或黑色。 ② 根节点必须是黑色的。 ③ 所有NIL节点都是黑色的。 ④ 一条路径上不能出现两个相邻的红色节点。 ⑤ 在任何递归子树中，从根节点到叶子节点的所有路径都包含相同数量的黑色节点。

这五个约束保证了红黑树的增、删、查最坏情况时间复杂度为O(logn)。如果树的左子节点或右子节点不存在，则两者都被视为黑色。红黑树的任意旋转可以在3次内完成。

AVL树和红黑树有什么区别？

红黑树的平衡性不如AVL树。它只是保持了粗略的平衡，并没有严格保证左右子树的高度差不超过1。这导致当节点数相同时，红黑树的高度可能更高，意味着相同情况下平均搜索次数会高于AVL树。

插入时，红黑树和AVL树最多可以在两次旋转内恢复平衡。删除时，由于红黑树只追求近似平衡，因此红黑树最多旋转3次就可以恢复平衡，而AVL树最多需要O(logn)次。当插入和删除时，AVL树会向上回溯以确定是否需要旋转。这种回溯最差的时间成本是O(logn)，而红黑树每次回溯的步长为2，回溯成本较低。因此，红黑树更适合频繁的插入和删除。

B树和B+树有什么区别？

B树中的每个节点都存储键和数据，而B+树中只有叶节点存储数据，非叶节点只存储键。 InnoDB对B+树进行了优化，在每个叶子节点上添加一个指向相邻叶子节点的链表指针，形成顺序指针的B+树，以提高区间访问的性能。

B+树的优点是：①由于B+树不包含非叶子节点上的数据信息，因此可以在内存页中存储更多的键，数据存储得更紧密，具有更好的空间利用率。访问叶节点关联的数据也有更好的缓存命中率。 ② B+树的叶子节点都是相连的，因此遍历整棵树只需要对叶子节点进行一次线性遍历。 B树每一级都需要递归遍历，相邻元素在内存中可能不相邻，所以缓存命中率不如B+树。但B树也有优点。由于每个节点都包含key和value，经常访问的元素可能离根节点更近，访问速度更快。

排序有哪些类别？

排序可以分为内部排序和外部排序。在内存中执行的排序称为内部排序。当数据量较大，无法复制到内存时，需要使用外部内存，称为外部排序。

内部排序包括比较排序和非比较排序。比较排序包括插入/选择/交换/合并排序。非比较排序包括计数/基数/桶排序。

插入排序包括直接插入/希尔排序，选择排序包括直接选择/堆排序，交换排序包括冒泡/快速排序。

堆和栈。请告诉我您对堆栈溢出的理解。请回答栈和堆的区别，以及为什么栈更快。请告诉我小根堆的特点。堆是一棵完全二叉树（如果总共有h层，那么1~h-1层都是满的，h层可能会缺少几个右叶）。请解释一下内存中栈、堆和静态区域的用法。并解释一下堆和栈的区别。通常我们定义一个基本数据类型的变量、对象的引用、函数调用的现场保存都使用内存中的栈空间；通过new关键字和构造函数创建的对象放置在堆空间中；程序中直接写的100、“hello”等字面量以及常量都放在静态区域中。堆栈空间操作速度最快，但堆栈很小。通常堆空间中会放置大量的对象。理论上，没有被其他进程使用的整个内存空间甚至硬盘上的虚拟内存都可以用作堆空间。堆栈是一种线性集合，其中添加和删除元素应在同一段中完成。堆栈按照后进先出的原则进行处理。堆是堆栈的一个元素。如何在大顶堆中插入、删除和插入： 在大顶堆后面插入新元素可能会破坏堆的结构。这时，需要找到新插入节点的父节点，并从下到上调整堆，使其成为大顶堆。

删除：将堆的最后一个元素填充到被删除元素的位置，然后调整堆结构，构造一个新的大顶堆。请告诉我动态链表和静态链表的区别。静态链表是使用类似于数组的方法实现的，是顺序的。存储结构在物理地址上是连续的，地址空间大小需要提前分配。因此，静态链表的初始长度一般是固定的。插入和删除操作时，不需要移动元素，只需要修改指针。动态链表利用内存申请函数（malloc/new）来动态申请内存，因此链表的长度没有限制。由于动态链表是动态申请内存的，所以每个节点的物理地址不是连续的，必须通过指针顺序访问。数组，请回答Array&List，数组和链表的区别，如何防止数组越界。由于默认情况下不会将数组的元素个数作为实际参数内容传入调用函数，因此会带来数组访问越界的相关问题。防止数组越界。越界：1）检查传入参数的合法性。 2）可以采用传递数组元素个数的方法，即使用两个实参，一个是数组名，一个是数组长度。在处理过程中，您可以确定数组的大小并确保不会访问超出数组大小的元素。 3）处理数组越界时，打印出遍历数组的索引是非常有帮助的，这样我们就可以追踪代码找出索引达到非法值的原因 4）Try{} catch(){ } 可以添加到Java中。请回答数组和链表的区别，以及优缺点，有没有办法结合两者的优点进行排序？ 1.请手写快速排序的代码并说明其最佳情况。

快速排序的最佳情况是每次Partition都被均匀划分。当排序元素个数为n时，递归树的深度为logn+1。第一次做Partition时，需要将所有元素扫描一次。得到的枢轴元素将所有元素一分为二，并继续划分，直到排序结束。在这种情况下，快速排序的最佳时间复杂度为 nlogn 。 2. 求第k大数的方法及其各自的复杂度是什么？另外，如果有相同的元素，可以用什么不同的方法来找到第k大的元素？首先使用快速排序算法对数组进行从大到小的排序，然后取出第k个元素。最快的时间复杂度是O(nlogn)。使用堆排序构建最大的堆，然后调整堆，直到得到第k个元素。时间复杂度为O(n+klogn)，首先用哈希表统计数组中元素出现的次数，然后利用计数排序的思想。从大到小的线性扫描过程中，如果前面有k-1个数，那么就是第k大的数。利用快速排序的思想，从数组中随机选择一个数i，然后将数组分为两部分Dl和Dr，Dl的元素全部小于i，Dr的元素全部大于我。然后计算 Dr 元素的数量。如果Dr元素的个数等于k-1，则第k大的数为k。如果Dr元素个数小于k，则继续寻找Dl中k-Dr最大的元素；如果 Dr 的元素个数大于 k 的话，则继续寻找 Dr 中第 k 大的元素。

当存在相同元素时，首先使用哈希表统计数组中元素出现的次数，然后使用计数排序的思想。从大到小的线性扫描过程中，如果前面有k-1个数，就是第k大的数。数，平均时间复杂度为O(n)。 3.请介绍一下各种排序算法和时间复杂度。插入排序：对于已排序的数组，初始有序数组元素个数为1，然后将第二个元素插入到有序数组中。 。对于每次插入操作，都会从后向前遍历当前的有序数组。如果当前元素大于要插入的元素，则向后移动一位；如果当前元素小于或等于待插入元素，则将待插入元素插入到当前元素的下一位中。希尔排序：首先将整个待排序记录分成若干子序列，然后分别进行直接插入排序。当整个序列中的记录基本有序时，对所有记录进行直接插入排序。子序列的组成不是简单地逐段划分，而是按一定增量的记录组成子序列。希尔排序的时间复杂度与增量序列的选择有关，其最后的值必须为1。 归并排序：该算法采用分而治之的方法；对于包含m个元素的待排序序列，将其视为子序列长度为1的m个元素，然后将它们成对合并，得到n/2个长度为2或1的有序子序列；然后再次成对合并，直到得到长度为 m 的有序序列。冒泡排序：对于一个包含n个元素的排序数组，重复遍历数组，首先比较第一个和第二个元素，如果顺序相反则交换元素位置；然后比较第二个和第三个元素，重复上述过程。

每次遍历都会将当前前ni个元素中最大的元素移动到ni位置。遍历n次即可完成排序。快速排序：通过一次排序将待排序的数据分成两个独立的部分。一部分中的所有数据都小于另一部分中的所有数据。然后用这个方法将两部分数据分别快速排序。整个排序过程可以递归地进行，从而使整个数据成为一个有序的序列。选择排序：每次循环时，选择当前无序数组中最小的元素，然后与无序数组的第一个元素交换位置，使得有序数组元素加1，无序数组元素减1。初始 无序数组为空。堆排序：堆排序是一种选择排序，利用堆等数据结构来完成选择。算法思想是对已排序的数据构造一个最大堆（升序）/最小堆（降序），然后将堆顶元素与待排序数组的最后一个元素交换位置。此时最后一个元素就是最大/最小值。然后将剩余的 n-1 个元素重建为最大堆/最小堆。各排序的时间复杂度、空间复杂度和稳定性如下：

4、如何从海量数据中获取最大的k个数？ 6、我们来说说如何获取数据流中的中位数？数据是从数据流中读取的，数据的数量随着时间的推移而增加。如果使用数据容器来保存从流中读取的数据，则当从流中读取新数据时，数据将被插入到数据容器中。数组是最简单的容器。如果数组未排序，可以使用 Partition 函数查找数组中的中位数。将数字插入未排序数组并查找中位数的时间复杂度为 O(1) 和 O(n)。当向数组插入新数据时，我们还可以保持数组排序。这是因为 O(n) 个数字可能会被移动，因此需要 O(n) 时间才能完成插入操作。在排序数组中查找中位数是一个简单的操作，只需要 O(1) 时间即可完成。排序链表是另一种选择。我们需要 O(n) 时间才能在链表中找到合适的位置来插入新数据。如果定义两个指针指向链表的中间节点（如果链表的节点数为奇数，则两个指针指向同一个节点），那么中位数可以在 O( 1）时间。这时候时间效率和基于排序的数组是一样的。如果能够保证数据容器左边的数据小于右边的数据，那么即使左右两边的数据没有排序，也可以根据最大的得到中位数左边的数字和右边最小的数字。如何快速查找容器中的最大数量？使用最大堆来实现这个数据容器，因为最大的数据位于堆的顶部。同样，您可以快速从最小堆中找到最小的数字。因此，可以采用以下思路来解决这个问题：使用最大堆来实现左边的数据容器，使用最小堆来实现右边的数据容器。向堆中插入一条数据的时间效率是O(logn)。由于获取堆顶数据只需要O(1)的时间，所以获取中位数的时间效率为O(1)。 7、对1000万个整数进行排序，整数范围在[-1000,1000]之间。哪种排序方法最快？在上面的场景中，最好使用计数排序。计数排序的基本思想是在排序之前先对这些数字进行计数。如果组号中的其他数字都小于这个数字，那么它的时间复杂度为O(n+k)，其中n是整数的个数，k是所有数字的范围，在这种情况下n>>k，所以计数排序优于其他基于比较的排序。 8.堆排序的思想是与待排序的序列形成一个大的顶堆。此时整个序列的最大值就是堆顶的根节点。与末端节点进行交换，然后末端变为最大值，然后剩下n。将-1个元素重建成堆，从而得到这n个元素中第二大的值。重复上述操作即可得到有序序列。 9.topK给出了3种解决方案

（1）可以避免对所有数据进行排序，只对部分数据进行排序；

（2）冒泡排序每轮排序都会获得一个最大值，因此K轮排序可以获得TopK。

时间复杂度空间复杂度：

(1)时间复杂度：一轮排序为O(N)，则K次排序总时间复杂度为：O(KN)。

（2）空间复杂度：O(K)，用于存储得到的topK，或者O(1)遍历原数组的最后K个元素。

1）堆：分为大顶堆（堆顶的元素比所有其他元素都大）和小顶堆（堆顶的其他元素比所有其他元素都小）。

(2)我们使用一个小顶堆来实现。

(3)取出K个元素放到另一个数组中，为这K个元素构建一个堆。

(4)然后循环从K下标位置开始遍历数据。只要该元素大于堆顶，我们就将堆顶分配给该元素，然后重新调整为小顶堆。

(5)循环完成后，K个元素的堆数组就是我们需要的TopK。

（1）时间复杂度：每次构建K个元素的堆时，时间复杂度为：O(KlogK)，加上NK次循环，总时间复杂度为O((K+(NK))logK)，即O (NlogK)，其中K是要获取的TopK个数，N是数据总量。

（2）空间复杂度：O(K)，只需要新建一个K大小的数组来存放topK

（1）例如，如果有10亿条数据，我们要查找Top1000，我们首先将10亿条数据分为1000份，每份100万条数据。

（2）在每个副本中找到对应的Top1000，整合成一个数组，得到100万条数据，这样就过滤掉了999%%的数据。

（3）使用快速排序对这100万条数据进行“一轮”排序。经过一轮排序后，假设指针指向的数字为S。数组将被分为两部分。大于S的部分记为Si，小于S的部分记为Sj。

(4) 如果 Si 元素的数量大于 1000，则对 Si 数组进行另一轮排序，将 Si 再次分为 Si 和 Sj。如果 Si 的元素小于 1000，则需要在 Sj 中获取 1000-count(Si) 个元素，即对 Sj 进行排序

(5) 这样递归即可得到TopK。

时间复杂度和空间复杂度：

(1)时间复杂度：获取副本前TopK的时间复杂度：O((N/n)logK)。那么所有副本的数量就是：O(NlogK)，但是对于分而治之的方法我们将使用多核和多机资源。比如我们有S个线程同时处理。时间复杂度为：O((N/S)logK)。然后进行快速排序，一次时间复杂度为：O(N)。假设排序M次后得到结果，则时间复杂度为：O(MN)。因此，总时间复杂度约为O(MN+(N/S)logK)。

（2）空间复杂度：每次拷贝都需要一个数组，所以空间复杂度为O(N)。

下一期我会发布一些排名访谈话题，敬请期待！