树

极客时间王争的《数据结构与算法之美》树相关课程笔记

根节点，父节点，子节点，兄弟节点，叶子节点/叶节点

每个节点最多两个子节点：左子节点，右子节点
满二叉树
完全二叉树

满二叉树就是一种完全二叉树

二叉树的存储分两种：链式存储 和 数组存储

完全二叉树的优势在于用数组存储不浪费空间。
数组的第0个空着，从第1位开始存根节点，然后每一层从左到右依次存储，每个节点的左子节点在数组中的下标位置是自己下标2，右子节点自然就是2+1

如上图，一棵完全二叉树，仅仅“浪费”了一个下标为 0 的存储位置。如果是非完全二叉树，其实会浪费比较多的数组存储空间。如下图

前序，中序，后续遍历
怎么记住呢，这个前中后就是父节点在前，在中还是在后
从根节点出发：

• 前序遍历： 对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
• 中序遍历： 对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
• 后序遍历： 对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。

需要注意，上面描述中不是左节点，右节点，而是左子树和右子树，这就体现出一个递归的概念了。结合下面的例子理解：

为快速搜索，插入，删除而生
每个节点的左子节点必须比自己小，右子节点必须比自己大

• 查找 从根节点往下一个一个找啦，比节点小就往左，否则往右，数有多少层，最多比较多少次，所以查找的效率完全取决于数的深度。
• 插入 太简单了不说了
• 删除
  • 先通过查找定位到节点
  • 如果节点没有子节点：直接删掉
  • 如果节点只有一个子节点：用子节点替代父节点即可
  • 如果有两个子节点，取右子树的最小值代替当前节点
  • 有个通用的取巧的办法，不要删除节点，而是标记删除，这样就是浪费一点空间，但是不增加查找和插入的复杂度，同时大大减小删除的复杂度。

前面说了查找效率和树的深度有关，最完美的情况就是完全二叉树（深度最小），那怎么知道一棵有n个节点的完全二叉树的深度？
下面n是节点个数，L是层数，为啥有大于和小于呢，因为最后一层的节点数量在1个到2^(L-1)个之间啦

n >= 1+2+4+8+...+2^(L-2)+1
n <= 1+2+4+8+...+2^(L-2)+2^(L-1)

反正最后算出来插入、删除、查找操作的时间复杂度也比较稳定，是 O(logn)。 至于怎么算出来的，什么等比数列公式啥的，恕我直言忘得差不多了。

• 对于二叉查找树，只要你是用中序遍历，就可以有序输出。散列表完全无序。
• 只要把二叉查找树进化为平衡二叉树，那么它各种操作的复杂度就是稳定的。但散列表不好说，当有很多冲突的时候，性能会下降。
• hash函数也是一种消耗
• hash表实现难度大，需要考虑冲突，扩容缩容等

想想上面的二叉查找数，如果按照从小到大，或者从大到小的顺序插入数据，那画面就很美丽了，直接退化为链表：

所以出现了平衡二叉查找树，目的是确保数的深度不会太大，严格的平衡二叉树定义是：
任何节点的左右子树高度相差不超过 1

但是一秒打脸，大名鼎鼎的红黑树 （R-B Tree） 并不严格符合平衡二叉树的定义，因为二叉树的维护（插入，删除）和查找效率是需要平衡的，如果严格按照平衡二叉树的定义来做（例如AVL树），虽然查询效率贼高，但是维护的代价很大。红黑树平衡了这两者，所以是另一种含义的“平衡”二叉树了。

红黑树的定义：

• 根节点是黑色
• 红色节点不能相邻
• 每个节点到它可达叶子节点的路径上，包含相同的黑色节点数量
• 叶子节点都是黑色，且为null（方便红黑树的实现，图片忽略了这个）
  
  先不论维护的复杂度，先看看如果完全满足红黑树的要求，查找的复杂度如何？
  先把所有的红色节点干掉，由于定律：每个节点到它可达叶子节点的路径上，包含相同的黑色节点数量，干掉红色节点之后会变成一个完全平衡的四叉树，高度肯定比同等节点数量的二叉树低，复杂度也肯定是小于等于log2n。
  那如果再把红色节点加回来，由于红色节点不能相邻，每层黑色节点中间最多夹一层红色节点，所以树的高度最多翻个倍，那复杂度也最多翻倍变成2*log2n。

未完待续