一、集合框架源码分析

• 集合框架 （第 01 篇） 源码分析：Collection<E> 框架总览
• 集合框架 （第 02 篇） 源码分析：Map<K,V > 框架总览
• 集合框架 （第 03 篇） 源码分析：ArrayList<E>
• 集合框架 （第 04 篇） 源码分析：LinkedList
• 集合框架 （第 05 篇） 源码分析：Map<K, V>接口与其内部接口Entry<K,V>
• 集合框架 （第 06 篇） 源码分析：哈希冲突(哈希碰撞)与解决算法
• 集合框架 （第 07 篇） 源码分析：jdk1.7版 HashMap
• 集合框架 （第 08 篇） 源码分析：HashMap、Hashtable、ConcurrentHashMap之间的区别
• 集合框架 （第 09 篇） 源码分析：jdk1.7版 ConcurrentHashMap
• 集合框架 （第 10 篇） 源码分析：二叉树、平衡二叉树、二叉查找树、AVL树、红黑树
• 集合框架 （第 11 篇） 源码分析：jdk1.8版 HashMap
• 集合框架 （第 12 篇） 源码分析：jdk1.8版 ConcurrentHashMap
• 集合框架 （第 13 篇） 源码分析：LinkedHashMap
• 集合框架 （第 14 篇） 源码分析：TreeMap
• 集合框架 （第 15 篇） 源码分析：Set<E> 集合
• 集合框架 （第 16 篇） 源码分析：BlockingQueue 接口
• 集合框架 （第 17 篇） 源码分析：CopyOnWriteArrayList 与 CopyOnWriteArraySet

原文持续更新链接: https://github.com/about-cloud/JavaCore

正文

tree

一、树

浩瀚宇宙，从 点 到线，线到面，面到体，组成了丰富多彩的世界。动物、植物和其他物体正是存储在 宇宙 这个数据结构中。

前几篇文章介绍了 线性 的数据结构: ArrayList、LinkedList及其组合HashMap。从 线性 数据结构到 非线性 数据结构，就像 树干 发叉一样：

line to tree

从数据结构进化的角度来看，树(tree) 的生成是 链表 进化而来。链(Linked) 每个节点最多只有一个 前驱节点 ，那么可以称这个 链 为 🌴树(tree) 。数据结构中的树就像一颗倒挂的树。

链表 只不过是特殊的树，就像树没有树枝只有树干一样。

树的基本术语

1. 节点(Node)：树中的每个元素称为 节点(Node)；
2. 根节点(Root Node)：树最顶端的节点被称为根节点（树根），根节点无父节点；
3. 父节点(Parent Node)：节点的（上面的）前驱节点在树中被称为父节点；
4. 子节点(Child Node)：（下面的）后继节点被称为子节点；
5. 子树(Subtree)：子节点及其下面的节点组成的树称为子树 ；
6. 一棵树最多只有一个根节点，树中的每个子节点最多只有一个父节点；
7. 节点的度：一个节点含有的子树的个数称为该节点的度（叶子节点的度为0）；
8. 叶节点(Leaf Node)（叶子节点或终端节点）：度为0的节点称为叶节点（也就是没有子节点的节点称为叶子节点）；
9. 非终端节点 或分支节点：度不为0的节点（拥有子节点的节点）；
10. 兄弟节点：具有相同父节点的节点互称为兄弟节点；
11. 树的度：一棵树中，节点中最大的度称为树的度；
12. 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
13. 树的高度或深度：树中节点的最大层次；
14. 堂兄弟节点：双亲在同一层的节点互为堂兄弟；
15. 节点的祖先：从该节点上溯至根节点，所经分支上的所有节点；
16. 子孙节点：该节点下面所有所有的节点称为该节点的子孙节点；
17. 空树：没有节点的树称为空树；
18. 森林：由多棵互不相交（没有重叠节点）的树组成的集合称为森林（单棵树可以认为是特殊的森林）；

二、二叉树

二叉树是每个节点最多只有两个子树的树。子树通常被称为左子树(Left subtree)和右子树(Right subtree)。

BinaryTree

二叉树的特性

1. 在非空二叉树的 i 层上，至多有 个节点(i>=1)；
2. 在深度为 d 的二叉树上最多有 2d-1 个结点（d>=1);
3. 对于任何一棵非空的二叉树,如果叶节点个数为 n0，度数为 2 的节点个数为 n2，则有: n0 = n2 + 1。

二叉树的遍历

二叉树遍历：从树的根节点出发，按照某种 次序 依次访问二叉树中所有的节点，使得每个节点被访问仅且一次。

这里有两个关键词：访问 和 次序。访问 包括 增删改查， 次序 包括 前序、中序、后序，前中后是以树的根节点作为参照物，又规定不管如何遍历 左子树 的访问顺序要排在 右子树 前面（左边）。

1、前序遍历（先序遍历）

遍历步骤：先访问根节点，然后再先序遍历左子树，最后再先序遍历右子树即 根—左—右。

先序遍历

上图先序遍历的结果：

2、中序遍历

遍历步骤：先中序遍历左子树，然后再访问根节点，最后再中序遍历右子树即 左—根—右。

中序遍历

上图中序遍历的结果：

3、后序遍历

遍历步骤：先后序遍历左子树，再后序遍历右子树，最后再访问根节点，即 左—右—根。

后序遍历

上图后序遍历的结果：

三、平衡二叉树

平衡二叉树（Balanced Binary Tree）的 平衡性 体现在以下几点：

1. 树的左、右子树的 高度差 的绝对值不超过1；
2. 任意节点左、右子树也分别平衡二叉树；

一棵数频繁的删除和插入节点都有可能使数发生旋转。平衡二叉树中访问节点的操作(插入、查找、删除)的时间复杂度维持在一个“平衡”的水准，既最坏情况和最好情况的时间复杂度维持在 O(logN)。

平衡二叉树

四、二叉查找树

二叉查找树(二叉搜索树 Binary Search Tree)的 查找 特性体现在以下几点：

1. 如果它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 如果它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 任意节点左、右子树也分别为二叉查找树。

先序遍历

二叉查找树的查找过程

1. 从树的根节点开始查找，并沿着这棵树中的一条简单路径向下进行；
2. 若树为空树，则查找失败，返回 null；
3. 对于访问的每个节点 x，若指定的值 k 等于结点 x 的值，返回该节点x 并结束查找；
4. 若指定的值 k 小于节点 x 的值，则在节点 x 的左子树中查找（根据上面二叉查找树的性质判断）；
5. 相反，若指定的值 k 大于节点 x 的值，则查找在节点 x 的右子树中继续；
6. 若查找至 叶子节点 后仍未匹配到相等值，则表示不存在指定值的节点，返回null。

五、AVL树（高度平衡树）

AVL树 得名于它的两位发明者G. M. Adelson-Velsky和E. M. Landis的名字，树的特性是：

1. :wink:本身首先是一棵二叉查找树;
2. 每个节点的左右子树的高度之差的绝对值（平衡因子）最多为 1 ；

AVL

ALV追求极限的平衡性，优点是在查找元素时，时间复杂度低，查找元素快。那么问题来了，在添加/删除元素时，AVL树为了追求“绝对的平衡性”，不断的通过循环来达到自平衡，增加时间复杂度。适所以AVL树适用于添加/删除元素少、查找操作多的环境下。

六、红黑树

红黑树（Red Black Tree） 也是一种 平衡二叉树（而平衡二叉树又是一种二叉查找树，所以红黑树也是一种二叉查找树），但它不像 AVL树 那样追求绝对的平衡，它这种于查找和添加/删除之间。特性是：

1. 树中所有节点都被染成红色🔴或黑色⚫️（官方话语：节点是红色或黑色）；
2. 根节点和叶子节点都是黑色⚫️
3. 每个红色节点🔴的两个子节点都是黑色⚫️（从每个叶子到根的所有路径上不能有两个连续的红色节点🔴）；
4. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点⚫️。

红黑树

上述特性构成了一个最关键的约束：从根节点到叶子节点的最长路径不大于最短路径的两倍长。

所以红黑树可以不是那么绝对的高度平衡。对于在树中添加/删除元素，红黑树也不像AVL树那样，为了达到绝对的自平衡而“使劲费力”地旋转整颗树了。

最差平衡二叉树即树退化成链表（可以看成特殊的树、没有叉的树），这样的树添加/删除元素快，不需要自平衡，但是查找慢，最坏情况要遍历整棵树。而从增删改查的时间复杂度来讲，红黑树 介于 二叉查找树 和 链表 之间，这是在添加/删除和查找之间一个折中的选择。

总结：

链表：适用于添加/删除多、查找少的场景；

二叉查找树：适用于查找多、添加/删除少的场景；

红黑树：适用于查找、添加、删除都多的场景。

七、B-Tree、B+Tree、B*Tree

这种和MySQL的InnoDB索引息息相关，单独拿出一个章节去讲解，详见：

https://github.com/about-cloud/JavaCore

原文持续更新链接: https://github.com/about-cloud/JavaCore