在上一篇中我们实现了二叉树的顺序结构——堆的实现,这次实现链式结构,若对堆不了解,可以观看。

如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同，若不相同则两个二叉树一定不同，若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同。对于这道题,我们可以进行深度优先查找,当值相同时就继续向下查找,如左子树,如果值相同就继续向下搜索左子树节点的值,不同就返回false,不用查找。对于这道题,如果两个二叉树都为空，则两个二叉树相同.如果两个二叉树中有且只有一个为空，则两个二叉树

这道题可以通过双指针来解决，我们分别用left和right来指向左右的起始位置，计算出当前的数值，同时移动left和right值较小的那一个，正如木桶原理，能接水的多少是由短的那一块木板决定的，所以我们通过移动较小值来不断更新，直到取到最大值。

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查 找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年 发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均

list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的

给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？方案1:将其中一个文件1的整数映射到一个位图中，读取另外一个文件2中的整数，判断在不在位图，在就是交集。消耗500M内存方案2:将文件1的整数映射到位图1中，将文件2的整数映射到位图2中，然后将两个位图中的数按位与。与之后为1的位就是交集。消耗内存1G

1970年，R.Bayer和E.mccreight提出了一种适合外查找的树，它是一种平衡的多叉树，称为B树 (后面有一个B的改进版本B+树，然后有些地方的B树写的的是B-树，注意不要误读成"B减树")。一 棵m阶(m>2)的B树，是一棵平衡的M路平衡搜索树，可以是空树或者满足以下性质：