什么情况下树会基于顺序存储法进行存储？

目录

数组和链表都是常用的数据结构，之前的博客分析过队列、栈等都可以基于数组和链表来实现，树也不例外。 大多数情况下，树是基于链表实现的，称为链式存储方法。 只有在特定情况下，树才基于数组来实现，称为顺序存储方法。 那么什么是树呢？ 什么情况下会基于顺序存储来存储树？ 数据结构的出现是为了解决问题，有其适用场景。 链表和树本身似乎没有什么关系，而且我们画图的时候总是从左到右画链表。 树木确实与现实生活息息相关。 它就像一棵树一样，只是根在上面。 双向链表会有前驱指针和后继指针指向相邻节点，那么一个节点可以有多个后继指针吗？ 但是，那是一棵树。 但树的一个特点是，每个节点都不能连接到自己的兄弟节点或上级节点（叔叔节点、爷爷节点），否则就会形成环路。 这棵特殊的树是一个图。 我不想定义树本身，只是用现实生活中的树来理解。

1.树的一些基本概念

如上图所示，树的一些基本概念，比如父节点、子节点、左子节点、右子节点等都比较容易理解，没有父节点的节点我们称为根节点，没有父节点的节点我们称为根节点。子节点称为叶节点。 。 树的高度、深度和层次常常很容易混淆。 树的高度与现实生活中的高度进行比较。 高度是从叶节点 0 开始自下而上计算的。树的深度与现实生活中进行比较。 深度是从相对位置向上计算的。 接下来从根节点0开始计算。树的层级与深度类似，只不过是从1开始计数，即

层=深度+1；

2.常用树的分类

根据每个节点可以存储的数据数量、每个节点可以拥有的子节点数量以及树的形状特征，树可以分为多种类型。 但树的出现是为了解决特定的问题，有自己的适用场景。 一般情况下，普通的数据结构因为没有规则，所以没有参考或使用价值。 例如：栈和队列都是操作有限的线性表，但其限制本身是独特的，可以应用于特定的场景，解决特定的问题。 树木也是如此。 项目工程中常用的树有：堆、红黑树、B+树等。

一般来说，根据一个节点可以拥有的子节点的数量，树可以分为二叉树、三叉树（2-3棵树也是三叉树）、N叉树（B树、B+树）。 B 树和 B+ 树您应该很熟悉。 主要用在数据库中，后面会具体分析。 最常用的树是二叉树。 以下是常用树木的分类和常听到的树名：

看起来数量很多，而且还很乱。 他们有自己的隶属（遏制）关系。 它们的组织方式如下：

下面仅分析二叉树：

1）、完全二叉树

叶子节点都在最下面两层（即叶子节点之间的最大差值为1）。 最后一层的叶子节点全部向左排列，除了最后一层外，其他所有层都必须有左右节点（即二分叉的情况下，节点数最大，即：满二叉树）。 想说的太多，但并不像下图那么直观：

二叉树除了完全二叉树外，基本上都是基于链表实现的。 以下完整二叉树和堆是完整二叉树的特例。 它们都属于完全二叉树，因此可以用顺序存储的方法来表示。 如果一棵完全二叉树存储在数组中，如果我们不使用数组索引为0的位置，那么所有节点都将满足：

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

2）、满二叉树

满二叉树是完全二叉树的特例（即必须满足完全二叉树的所有条件），它针对的是数据的排列结构。 定义：所有叶子节点都处于最低级别（即叶子节点的高度都相同）。 除叶子节点外，每个节点都必须有左右子节点。 满二叉树的高度（高度从0开始计算）和节点数分析：

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

3）、桩（大顶桩、小顶桩）

堆是完全二叉树的另一种特殊情况（即必须满足完全二叉树的所有条件），其目的是比较节点数据的大小。 堆中每个节点的值必须大于或等于（或小于或等于）其子树中每个节点的值。 大于或等于每个子树节点的值称为大顶堆，无论如何都称为小顶堆。 下面小节将具体分析堆，主要用于处理Top N值等问题。

4）、二叉搜索树

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

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

二叉搜索树：父节点>左子节点（或左子树）&&父节点<右子节点（或右子树），那么如果树比较满（接近满二叉树），则该节点只需判断查询范围可以一次性缩小一半，类似于二分查找，时间复杂度接近O(logN)。

5）、平衡二叉树

平衡二叉树的定义：任意节点的子树之间的高度差小于等于1，即树尽可能接近满二叉树，这本身就是让树尽可能的满树的高度尽可能低。

二叉树最坏的情况是它退化为链表，即搜索时，所有东西都在左子节点上（或者都在右子节点上）。 此时树的高度也最大，因此查询的时间复杂度降为O(N)。 当二叉树接近满二叉树时，节点的数量和高度接近上面的high=log2N。

6). 平衡二叉搜索树

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

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

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

AVL树，自平衡二叉搜索树。 非平衡主要发生在添加或删除元素时，这时需要向左或向右旋转，使树继续满足平衡（高度）和搜索（父节点大于左子节点且小于左子节点）的特性右子节点）。 红黑树在项目工程中基本都会用到，这里就不研究AVL树了。

8)、红树和黑树

红黑树并不是严格意义上的平衡二叉搜索树，因为红黑树的叶子节点之间的高度差可能会增加一倍。 但我们仍然相信红黑树是平衡二叉搜索树。 红黑树的性能是所有平衡二叉搜索树中最好的。 红黑树基本上用在所有需要平衡二叉搜索树的项目中。 树的实现。 比如Java中的TreeMap，在jdk 8之后，当HashMap的链表节点数大于8时，就会使用红黑树，基本上所有的语言库都会有红黑树的实现。 红黑树经过增删操作后，仍然需要满足条件，就会进行大量的左手、右手、颜色变化。 我们大多数人这辈子可能永远不会在项目开发中自己实现一棵树。 红树和黑树，所以不用花太多时间在这里研究。

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

1、根节点为黑色；

2、每个叶子节点都是一个黑色的空节点（Null），表示该叶子节点不存储数据。

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

3.任何相邻节点不能同时为红色，这意味着必须有一个黑色节点将红色节点分隔开。

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