Retros.

——神即道,道法自然,如来

从2-3树到红黑树

在上一篇文章中,我们讨论了一种严格平衡的平衡查找树 AVL 树,本文来看一个在实际场景中运用更多的平衡查找树——红黑树。 本文所解析的红黑树并非一般意义上的更一般化的红黑树,解析的是源自《算法》第四版中由 2-3 树变化而来的左偏红黑树。感兴趣的读者可以在理解了本文所阐释的左偏红黑树后,再去理解更一般的红黑树,相信能够更容易理解。 2-3树 2-3 树的思想不仅仅有利于帮助我们理解左偏红黑树,也有利于我们去理解 B 树——一种其变种被广泛用于数据库索引领域的更宽的平衡树。 简单来说,2-3 树就是这样一种树:它的节点可能有两个孩子,也可能有三个孩子。对于两个孩子的节点,其左子节点小于根节点的值,右子节点大于根节点的值。这个与普通二叉搜索树一致,很容易理解。对于三个孩子的节点,其实也很容易理解。如果我们将三个孩子节点中包含的两个值分别称为 A 和 B,那么第一孩子的值全部 小于 A,第三孩子的值全部 大于 B,第二孩子的值介于 A 和 B 之间。大概就是如下图所示: 但 2-3 树的构建过程与前面的普通二叉搜索树,以及 AVL 树不同,它是由下至上构建的。具体来说,2-3 树的插入规则可以这么理解: 如果插入的节点是 2 节点,则生成一个新的键,使其变为 3 节点 如果插入的节点是 3 节点,则同样生成一个新的键,使其变为 4 节点,然后再进行调整: 如果这个 4 节点是 2 节点的孩子,那么提取中间的键到父节点,使父节点变成 3 节点 如果这个 4 节点 是 3 节点的孩子,依旧提取中间的键到父节点,使父节点变成 4 节点,递归此过程 如果 4 节点是根节点,则将其分解成两个 2 节点,以及一个 2 节点的根节点 如果想要了解 2-3 树是如何保证全局的有序性与平衡性的,可以参阅 《算法》第四版 P272-273,本文在此就不赘述。...

March 13, 2022 · 2 min

AVL树

题记:AVL树是笔者在上学时就一直没弄懂的数据结构,时隔多年重学数据结构,终于跨越了新手误区,成功理解了它的旋转,特作此文以记录一下。 注:本文默认读者已对二叉查找树、AVL树的基本功能有了一个感性认识,因此不赘述其查询过程,也不分析其查询复杂度,仅就其理解上的难点给出说明。 一、正确理解递归 树是一个典型的递归定义的数据结构,在树上执行的操作很多都是递归进行的,因此要理解树上的操作,我们首先需要正确理解递归。 笔者在第一次学习递归时,一度试图跟着递归调用一直走到递归终止,然后跟着递归弹栈,以理解全过程。这种策略在理解迭代型程序是可行的,但是理解递归程序切不可这么做。试图跟着递归程序理解其递归全过程,是新手学习递归过程中最容易进入的误区。 那么应该如何正确理解递归呢?我们可以考虑高中数学里一个常见的递归(递推)结构:数列。当我们描述一个数列时,有时我们可以给定一个数列的通项公式,但更多时候,通项公式并没有数列的递推公式容易得到。所以,也时常有数列是以递推公式+首项的方式进行描述的,这其实就是理解递归的正确方式。 在理解递归时,只需要考虑相邻结构,以及递归终止条件(即相当于数列首项)即可,数学结构保证了其有效性。 二、二叉查找树 二叉查找树是指一棵空树或者具有下列性质的二叉树: 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值; 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值; 任意节点的左、右子树也分别为二叉查找树; 上面是二叉查找树的正式的定义,其实一般情况下,只需要记住二叉查找树的左子树的值都小于根,右子树的值都大于根,就已足够。 二叉查找树的构建是通过一个值一个值插入来构建的,哪怕有一组用来构建二叉查找树的值,二叉查找树也只能通过逐个插入来构建。 举例:1、4、3、5、6、2、7 这个序列: 但同样的7个数字,如果不是按照上述插入方式插入的话,得到的二叉查找树的结构就会大相径庭。比如一个很容易发现的规律是:序列中第一个插入的元素一定会成为朴素二叉查找树的根节点。 三、AVL树 由于朴素二叉查找树在极端情况下(即插入序列为有序序列)构建的查找树退化成一个单链表,使得在二叉查找树上进行查询的时间复杂度退化成O(n)。因此,为了保证查询高效,我们必须在插入元素后,对树的结构进行调整,使树尽量「宽」,而非尽量「深」,使得树能够保证平均查询复杂度始终保持在O(logN)数量级。 为了衡量一棵树是否需要调整,我们需要有一个方式对树的状态进行度量。在AVL树中,我们选择的度量方式是比较子树的高度。 路径长度:从根节点到叶子节点经过的节点数量(包含根节点和叶子结点) 树的高度:一棵树的所有路径里最长路径的长度 在AVL树结构中,当一棵树的左子树与右子树的高度差的绝对值超过2时,就需要对树的结构进行调整了,这种调整在一般的文章讨论中成为「旋转」,其实本质就是对树中一些指针的指向进行调整的过程,它和链表插入也没什么本质的区别,都是指针调整而已。 那么 AVL 树是怎么做的呢? 首先 AVL 树将需要调整的情况分成了四类: 在左子树的左子树上做插入 在左子树的右子树上做插入 在右子树的左子树上做插入 在右子树的右子树上做插入 其中类型 1、4 镜像对称,类型 2、3 镜像对称。因此我们只需要研究类型 1 和类型 2 即可。 这里额外插一句,从上文对情况分类讨论时的用词「左子树的左子树」「右子树的左子树」等,我们可以很清晰地发现关于 AVL 结构调整的操作是在两层(即子树,以及子树的子树)上去操作的,这一定程度上有别于一些简单的递归操作时仅仅只在一层上去操作,此处需要格外注意去理解。 另外,关于如何找到要调整的根节点,这块看看具体的代码实现就清晰了,文字描述反而容易增加理解难度,因此此处不用文字赘述。 1、4两种情况的处理 关于这种调整是如何进行的,也话不多说,看图即可。 上图描述了如何处理 在左子树的左子树上做插入, 即第一类情况需要做出的调整。 用文字描述的话就是:让根节点成为其左子树的右子树,然后让左子树原来的右子树成为根节点新的左子树。经过调整后,原左子树变成了根节点。...

February 20, 2022 · 3 min

解决 Windows 11 PowerShell 禁止运行脚本问题

通过配置注册表,一劳永逸地解决 PowerShell

January 12, 2022 · 1 min