从二叉树到红黑树
二叉树
- 树的每个节点最多只能有两个节点。
- 2-3 树的节点可以拥有 2 或 3 个子节点。
二叉搜索树(Binary Search Tree)
怎么称呼的都有：二分查找树、二叉搜索树、二叉排序树、有序的二叉树……
但是它的功能不仅在搜索哦，还需要进行增删改。
二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为
如果大量删除，二叉排序树就有可能变为一个单叶的树，此时查询效率就成了 O(n) 。
二叉查找树越是「矮胖」，也就是每层尽可能地被「塞满」（每个父节点均有两个子节点）时，查找效率越高。每层都被塞满时，查找效率最高，最高为 O(log n) 。当二叉查找树退化为单链表时，查找效率最低，最低为 O (n) 。
为了解决二叉查找树退化为单链表时查找效率低下的问题，引入了平衡二叉树。
平衡二叉树（AVL 树）
- 也称为平衡二叉搜索树。
- 相同结点数，深度最小的便是平衡二叉树。
- 当我们谈平衡二叉树时，默认它已经是一棵二叉搜索树。平衡二叉树是对二叉搜索树的改进。
- 定义：AVL 树是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。
- Windows 对进程地址空间的管理用到了 AVL 树。
在树有序的情况下，树的查询速度取决于树的深度。一棵二叉搜索树在最坏的情况下，查找的效率就是 O(n)。AVL 树通过维护自己的「矮胖」（平衡），使数据尽可能地二分，达到优化查找效率的目的。
但是这样查找是快了，当涉及到插入时，就需要极大的代价去维护树的平衡。因此有了 2-3 查找树。
2-3 树
- 2-3 树的节点可以拥有 2 或 3 个子节点。
- 2-3 树是最简单的 B-树。
- 直接把定义甩出来很抽象，把 2-3 树放在 2-3 查找树里看，直观一些。
2-3 查找树
- 2-3 查找树是对平衡二叉树的优化（自然，也是对二叉搜索树的改进）。
- 同理，当我们谈 2-3 查找树时，也就是默认这已经是 AVL 树了。
- 事实上，2-3 树属于 B-树，B-树已经默认是平衡二叉树了。
2-3 查找树怎么花比较小的代价去维护树的平衡呢？
红黑树
红黑二叉树是对 2-3 树的优化。
《算法》中提到：红黑树背后的思想是用标准的二叉搜索树（完全由 2- 结点构成）和一些额外的信息（替换 3- 结点）来表示 2-3 树.
红黑树将树中的链接分为两种类型：红链接（将两个 2- 结点连接起来构成一个 3- 结点）；黑链接（2-3 树中的普通链接）
- MySQL 的 InnoDB 存储索引用到了红黑树。
- JDK1.8 中，当桶中节点数目大于 8，将链表转换为红黑树存储。
其它「树」
B-树
上面提到 2-3 树是最简单的 B-树。
B-树属于多叉树，又名平衡多路查找树。也就是在 2-3 树上面进行扩展。
2-3 树的节点可以拥有 2 或 3 个子节点，而 B-树的节点可以拥有多个子节点。
B+树
B+树是对 B-树的升级。
- B/B+树 用在磁盘文件组织，数据索引和数据库索引。
完全二叉树
定义：若设二叉树的深度为 h，除第 h 层外，其它各层 （1 ～ h-1） 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
简单讲，完全二叉树——只有最下面的两层结点度小于 2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。
最优二叉树（哈弗曼树)
主要内容是哈弗曼算法，如何构造哈弗曼树，哈夫曼序列。
满二叉树
满二叉树——除了叶结点外每一个结点都有左右子叶且叶结点都处在最底层的二叉树。
除最后一层无任何子节点外，每一层上的所有结点都有两个子结点（最后一层上的无子结点的结点为叶子结点）。
也可以这样理解：除叶子结点外的所有结点均有两个子结点。节点数达到最大值。所有叶子结点必须在同一层上。
树的一些概念
- 叶子结点就是没有孩子的结点，其度为 0，度为二的结点是指有两个子树的结点。