2-3树 —— 理解红黑树的捷径
如果从先易后难的顺序介绍各种树,那么红黑树必然放在 AVL 树后面。但在红黑树之前,还有一种名为 2-3 树的平衡二叉树。2-3 树理解起来比红黑树容易很多,并且在理解它的基础上增加一个变更,就成了红黑树(尽管不是通常使用的那种红黑树)。因此学习红黑树的时候,最好先学习 2-3 树。
如果从先易后难的顺序介绍各种树,那么红黑树必然放在 AVL 树后面。但在红黑树之前,还有一种名为 2-3 树的平衡二叉树。2-3 树理解起来比红黑树容易很多,并且在理解它的基础上增加一个变更,就成了红黑树(尽管不是通常使用的那种红黑树)。因此学习红黑树的时候,最好先学习 2-3 树。
之前在了解二叉树旋转的时候,为了方便查看中间状态,就写了个以树状形式打印二叉树的函数。
起初是使用二叉树中序遍历的结果展开的方式,简单但打印出来的树有一定的倾斜。
上一篇把树旋转了解清楚,是为这一篇平衡二叉树准备的。
平衡二叉树,就是在二叉树的基础上加上一个条件:对于任意节点,左子树和右子树的树高之差不超过 1。
我偶尔会思考“我的一生应该是什么样的”这个问题。当我偶然间思考出了一个足够明确的答案后,就自然而然地以最佳的状态去面对生活。
只是我没有及时地将这些内容记录下来,以至于因为一些事情而逐渐地忘记一部分内容,这种状态就消失了。如果能让那种时刻保持充分幸福感的状态一直持续下去,我也就心满意足了。所以我尝试现在将剩下的部分写出来,一是试图通过这种方式将遗忘的部分重新推导出来,二是为了以后重新进入状态的时候能快速补足内容。
事情要从某天晚上买夜宵说起。买了香肠拿着吃,想着多年来一直没搞懂的树旋转是不是应该看看,就点进某百科。
树旋转是在二叉树中的一种子树调整操作, 每一次旋转并不影响对该二叉树进行中序遍历的结果。
我们现在使用的 TLS 证书的标准是 X.509,版本号为 V3。版本号可从证书的 Version 字段看到。
根据 RFC 3280 定义的证书结构,证书由三个部分组成:
证书主体包括版本、序列号、公钥等内容。签名值是对证书主体使用签名算法计算并经过证书签名机构私钥加密后的值。