前言
面试过程中，多多少少会问一点数据结构（二叉树）的问题，今天我们来复习一下二叉树的相关问题，文末总结。
1. 二叉树的由来
在 jdk1.8 之前，HashMap 的数据结构由「数组+链表」组成，数组是 HashMap 的主体，链表是为了解决 Hash 冲突引入的，正常的数据存放是直接存在数组中，但如果发生 Hash 冲突就会以链表的形式进行存储，而在 jdk1.8之后，当链表的长度超过 8 之后，将会转换成红黑树经常存储...
相信这一段 HashMap 的描述，一定是大家所熟知的，其实细品之后，我们可以从这段描述中发掘这些信息。
数组 > 链表 > 树。
正所谓有需求就会有发展，我们来看看为什么在有「数组+链表」的情况下，还出来个树结构。
数组优点：
- 简单易用，随机访问性强
- 无序数组插入速度很快，效率为O1
- 有序数组查找速度较快，效率为O(logN)
数组缺点：
- 插入和删除效率低
- 数组大小固定，无法动态扩容
链表优点：
- 大小不固定，无限扩容
- 插入和删除速度很快
链表缺点：
- 查询效率低，不支持随机查找，必须从第一个开始遍历
- 在链表非表头的位置进行插入、删除很慢，效率为O(N)
从数组到链表的优缺点，我们可以看出是各有千秋，不能很准确的说链表比数组就一定要高效，而正是因为这种关系的存在，所以二叉树出现了。
所以二叉树的由来：二叉树整合了数组和链表的优缺点，使得插入、删除、查找的速度都很快，效率比较高。
2. 二叉树是什么
二叉树是树形结构的一个重要类型，也是众多数据结构的基石。
树有很多类型，每个节点最多只能有两个子节点的叫二叉树。
所以，二叉树的特性就是每个节点的子结点不允许超过两个。
3. 二叉查找树
二叉查找树是一种特殊的二叉树，二叉查找树的特点就是，左子树节点比父节点小，右子树节点值比父节点大。
极端现象
二叉查找树有一种极端的存在，二叉树的大部分子节点都比父节点值小，然后导致所有的数据偏向左侧，进而退化成链表，如下图所示：
我们使用二叉树的目的是因为其效率高于链表查询，但这种退化为链表的现象很显然就突兀，怎么办呢。
所以为了解决二叉树退化成一棵链表就引入了平衡二叉树。
4. 平衡二叉树
平衡二叉树，又被称为AVL树，是为了解决二叉树退化成一棵链表而诞生的。
平衡二叉树特点：
- 拥有二叉查找树的全部特性。
- 每个节点的左子树和右子树的高度差至多等于1。
其中左右子树的高度差是通过左旋右旋实现的。
下面是一个平衡二叉树和非平衡二叉树的图：
到底是如何判断高度差的呢？我们可以来数节点最长连接数，比如左侧节点最长连接数为「3 > 4 > 5」3个节点，右侧为「9」一个节点，所以高度差为2。
再比如下面一个平衡二叉树：
左侧最长连接点为「3(9) > 7 >11」，即高度为2，右侧最长连接点为「14(16) > 15 > 18 > 11」，即高度为3，所以高度差为1。
为了维持二叉树的平衡，平衡二叉树是通过左旋、右旋来保证的，从大的方向旋转过程又被分为单旋转和双旋转，总之，旋转的作用就是避免出现节点偏向一边的情况，具体左旋、右旋操作在这就不详细阐述了。
但是平衡二叉树这种高度差为 1 的要求太严格了，尤其是对于频繁删除、插入的场景非常浪费时间...
5. 红黑树
对于那种频繁删除、插入的场景，平衡二叉树的调整过程显然是存在性能问题的，所以为了解决这个问题，进而又引入了红黑树。
红黑树的特点：
- 具有二叉树所有特点。
- 每个节点只能是红色或者是黑色。
- 根节点只能是黑色，且黑色根节点不存储数据。
- 任何相邻的节点都不能同时为红色。
- 红色的节点，它的子节点只能是黑色。
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
红黑树如下图所示：
概括为：红黑树所有的根节点都是黑色的的空节点，也就是根节点不存数据；任何相邻的节点都不能同时为红色，红色节点是被黑色节点隔开的；每个节点，从该节点到达其可达的叶子节点的所有路径都包含相同数目的黑色节点。
正是因为这种特点，红黑树不同于平衡树的操作，红黑树不会因为插入、删除等操作追求绝对的平衡，它的旋转次数少，插入最多两次旋转，删除最多三次旋转，所以对于搜索、插入、删除操作较多的情况下，红黑树的效率是优于平衡二叉树的。
但是需要注意的是，如果应用场景中对插入、删除不频繁，只是对查找要求较高，那么平衡二叉树还是较优于红黑树。
总结
为什么有了数组和链表还要引入二叉树？
针对数组和链表的优缺点，无法说链表一定优于数组，或者是数组一定优于链表，因为某些长期的需要，所以就推出一个相对折中的二叉树。
为什么有了二叉树还要引入平衡二叉树？
有了二叉树还不算完，二叉树有一种极端的情况，就是所有的子结点偏向一端，二叉树退化成链表，这就相当于我选择了这种的二叉树，你现在罢工不干了，找了个链表来糊弄我...
所以为了解决二叉查找树退化为链表的情况，引入了平衡二叉树，即：
平衡二叉树是为了解决二叉树退化成一棵链表而诞生的。
既然有了平衡二叉树，这下总没有问题了吧？
为什么有了平衡二叉树还要引入红黑树？
但是是实际使用过程中，因为平衡二叉树追求绝对严格的平衡关系，显然这个规则在于频繁的插入、删除等操作的情景性能肯定会出现问题...
所以为了解决这个问题，进而又引入了红黑树。
平衡二叉树追求绝对严格的平衡，平衡条件必须满足左右子树高度差不超过1，红黑树是放弃追求完全平衡，它的旋转次数少，插入最多两次旋转，删除最多三次旋转，所以对于搜索、插入、删除操作较多的情况下，红黑树的效率是优于平衡二叉树的。
红黑树是终结吗？
时代总是进步的，大胆猜测不会是，就跟当初从数组、链表到二叉树一样。
至此，通过这篇希望大家对整个树结构的出现有一个基础的概念，目前面试中最为常问的就是红黑树了，当然这得益于 HashMap，但红黑树还有挺多其他的知识点可以考察，例如红黑树有哪些应用场景？红黑树与哈希表在不同应该场景的选择？红黑树有哪些性质？红黑树各种操作(插入删除查询)的时间复杂度是多少？等等等等...
原文连接：https://www.cnblogs.com/niceyoo/p/13941947.html
标签：链表,二叉树,数组,红黑树,平衡,节点 From： https://www.cnblogs.com/zhusf/p/16831359.html