数据结构

目录

1、树的一些基本概念

2、常用树的分类

1)、完全二叉树

2)、满二叉树

3)、堆（大顶堆、小顶堆）

4)、二叉搜索树

5)、平衡二叉树

6)、平衡二叉搜索树

7)、AVL树（自平衡二叉搜索树）

8)、红黑树

    数组和链表都是常用的数据结构，并且前面博客分析了队列、栈等都可以基于数组和链表实现，树也不例外。大部分情况下树都会基于链表进行实现称为链式存储法，只有在特定的情况下才会基于数组进行实现称为顺序存储法。那么什么是树呢？什么情况下树会基于顺序存储法进行存储？一种数据结构的出现都是为了解决问题，有其适用的场景，链表和树本身看似没有任何关系，并且我们进行画图都将链表从左到右形式画，树就真的与现实生活中的树一样，只是根在上。双向链表都会有前驱和后继指针指向相邻的节点，那么一个节点可不可以有多个后继指针呢？可是，那就是树。但是树有一个特点就是，每个节点都不能与自己的同级或上级（叔叔节点、爷爷辈的节点）相连，否则就成环了，这种特殊的树就是图了。不想对树本身下定义，使用现实生活中的树去理解就可以了。

    如上图，树的一些基本概念，父节点、子节点、左子节点、右子节点等都比较好理解，并且我们把没有父节点的节点叫做根节点，把没有子节点的节点称为叶子节点。树的高度、深度、层经常容易混淆，树的高度类比到现实的生活中，高度是从底下往上，从叶子节点 0 开始计算；树的深度类比到现实生活中，深度是从相对位置往下，从根节点 0 开始计算。树的层与深度类似，只是从1 开始往下数，即

层 = 深度 +1；

    树按照每个节点可以存储数据的个数、每个节点可以拥有的子节点个数、以及树的形状特征可以分为很多种类。但是树的出现就是为了解决特定的问题，有自己适用的场景。一般情况下，普通的数据结构没有任何的参考和使用价值，因为没有规律。例如：栈、队列都是操作受限的线性表，但是限制本身就特点，就能应用在特点的场景解决特定的问题。树也是，项目工程上常用的树有：堆、红黑树、B+树等。

    一般按照一个节点可以拥有子节点的个数，可以将树分为二叉树、三叉树（2-3树也是一种三叉树）、N叉树（B树、B+树）。B树和B+树应该不陌生，主要用于数据库，后面专门进行分析；使用最多的还是二叉树，下面对常用树和经常听到树的名称进行分类：

看起来比较多，比较乱，他们有自己的所属（包含）关系，整理如下图：

    下面只对二叉树进行分析：

    叶子节点都在最底下两层（即叶子节点差最大是1），最后一层的叶子节点都靠左排列，并且除了最后一层其他层都必须有左右节点（即达到二叉情况下，节点数最大，即：满二叉树）。说太多都没有图直观，如下图：

    二叉树基本都会基于链表实现，完全二叉树除外。下面的满二叉树、堆都是完全二叉树的特殊情况，都属于完全二叉树，所以都可以使用顺序存储法表示。完全二叉树使用数组存储的话，当我们将数组下标为 0 的位置不使用的话，那么所有的节点都满足：

如果父节点在数组中的下标位置为 n，那么左子节点在数组中的下标位置为 2 * n，右子节点在数组下标中的位置为 2 * n + 1，即堆也可以使用数组表示，并且满足该条件。

    满二叉树是完全二叉树的一种特殊情况（即完全二叉树的条件都必须满足），针对的是数据的排布结构。定义：叶子节点全部都在最底层（即叶子节点高度全部相同），除了叶子节点外，每个节点都必须有左右子节点。对满二叉树的高度（高度从0开始计算）与节点个数分析：

树高0：存储1个节点，树高1：存储 2个节点，树高2：4个节点，树高h：存储 2^h 个节点。那么当树的节点个数为N时满足层高 h = ㏒₂N。

    堆是完全二叉树的另一种特殊情况（即完全二叉树的条件都必须满足），针对的是节点数据的大小对比。堆中每个节点的值都必须大于等于（或者小于等于）其子树中的每个节点的值。大于等于每个子树节点的值称为大顶堆，反正称为小顶堆。后面专门分析堆，主要用于处理Top N值等问题。

    二叉搜索树要求，二叉树中的每个节点都满足：左子节点的值小于父节点，右子节点的值大于父节点。即查询到每个节点后，左子树的值都比自己小，有子树的节点都比自己大。这点可以与堆进行相比：

大顶堆： 父节点 > 左子节点 && 父节点 > 右子节点，那么根节点值最大。 小顶堆： 父节点 < 左子节点 && 父节点 < 右子节点，那么根节点值最小。

二叉搜索树：父节点 > 左子节点（或左子树） && 父节点  < 右子节点（或者右子树），那么如果树比较饱满（趋近满二叉树）的情况下， 节点只需要判断一次就可以将查询范围缩小一半，类似二分查找，时间复杂度就趋近 O(logN)。

    平衡二叉树的定义：任意节点的子树高度差都小于等于1，即树尽量趋近于满二叉树，本身就是让树尽量的饱满，树的高度尽量低。

    二叉树的最差情况就是全部退化成一个链表，即查找时全部在左子节点（或者全部是右子节点），此时树的高度也是最大的，那么查询的时间复杂度就退化为O(N)。而当一颗二叉树趋近于满二叉树时，那么节点个数与高度就趋近于上面的 high = log₂N。

    平衡二叉搜索树 = 二叉搜索树 + 平衡二叉树。二叉搜索树在查询数据的时候可以通过判断就减少一部分数据，但是如果类似于上面整个二叉树退化成单链表，那么二叉搜索树本身也没有意义。平衡二叉树本身将树的高度降到了最低，但是如果没有二叉搜索树那样的减少数据查询的范围，那么查询一个数的时间复杂度任然是O(N)，这就是二叉树的前序、中序、后续遍历。

    所以只有平衡二叉搜索树才有意义，才能在实际项目中解决问题，每判断一次就将数据范围减小一半，与二分查找一样，查询的时间复杂度为O(logN)。常见的平衡二叉查找树有：AVL树（自平衡二叉查找树）、伸展树（Splay Tree）、树堆（Treap）、红黑树。

    AVL树，自平衡二叉查找树。非平衡主要发生在新增或删除一个元素的时候，那么需要通过左旋或右旋的方式，让树继续满足 平衡（高度）和搜索（父节点大于左子节点，小于右子节点）的特点。项目工程上基本都会使用红黑树，所以这里不展开研究AVL树。

    红黑树不是严格意义上的 平衡二叉搜索树，因为红黑树的叶子节点高度差可能达到一倍。但是我们任然认为红黑树是平衡二叉查找树，红黑树的性能是所有平衡二叉搜索树中最好的，所有项目上需要用到平衡二叉搜索树的地方基本都会使用红黑树实现。比如Java中的 TreeMap, jdk 8之后当HashMap的链表节点个数大于8时，会使用红黑树，并且基本上所有的语言库中都会有红黑树的实现。当新增和删除操作后，需要让红黑树任然满足条件，会做大量的左旋、右旋以及颜色的更换，我们大部分人可能这辈子都不会在项目开发中自己去实现一颗红黑树，所以这里【自己】不必花太多时间去研究。

    顾名思义，红黑树的节点有红色和黑色两种颜色，红黑树的特点：

1、根节点是黑色的；

2、每个叶子节点都是黑色的空节点（Null），也就是说叶子节点不存储数据。

     这一条的要求主要是为了在代码实现时稍微简单一点，因为红黑树的实现本身就不简单了。如果担心最后一层都需要创建黑色空节点浪费空间，增加空间复杂度，可以只创建一个黑色Null节点，让所有的叶子黑节点都指向该Null对象。

3、任何相邻的节点都不能同时为红色，也就是说红色节点中间一定有黑色节点隔开。

4、每个节点都满足，从该节点到达其可达的叶子节点的所有路径，黑色节点的个数必须相同。