不知不觉，马上就来到了五月。大学的课程也只剩下一两门。在大学时光结束之前，记录一下生活。可以将这东西理解为日记(流水账)，但俺懒到一个月才写一次。

AVL 树和红黑树都假设所有的数据放在主存当中。而当数据量达到亿级，主存中根本存储不下，我们只能以块的形式从磁盘读取数据，与主存的访问时间相比，磁盘的 I/O 操作相当耗时，而提出 B-树的主要目的就是减少磁盘的 I/O 操作。

虽然，Carl的《代码随想录》和labuladong的《算法小抄》对“动态规划”类问题有着详尽且优质的解答，但仍然想在这里简单啰嗦一下动态规划。在这里，并不想以《算法导论》中较为晦涩且难懂的「矩阵连乘」、「最优二叉搜索树」等为样例进行讲解。

引入

由于二叉搜索树很不平衡，很容易退化为一条类似链表的结构，从而造成时间复杂度从$O(lgN)$降低为$O(N)$。

为解决这一问题，引入了“平衡”二叉搜索树，红黑树就是其中的一种。红黑树在树的基础上，为每个节点增加了一个颜色位，可以是RED，也可以是BLACK。通过对每条路径的颜色进行约束，保证红黑树处于近似平衡的状态，从而保证了查找最坏情况为$O(lgN)$。

在二叉树的基础上，我们可以扩展出任意多个叉的树。即，多叉树。然而，此时又面临着另外一个问题：

• 当孩子结点无限制时，我们并不知道预先要分配多少个属性，且当仅有少数元素拥有多个子节点时，将会造成大量的空间浪费。

此时，提出了一种新的表示形式:

$left-child \quad right-sibling \quad representation$。