数据结构-树（一）：二叉树族

大家好，欢迎来到IT知识分享网。

什么是树？

树（Tree）是一种由n个节点组成的具有层次关系的抽象数据结构，因其看起来像一个倒立的树而得名。它具有以下的特点：

• 每个节点都只有有限个子节点或没有子节点；
• 没有父节点的节点称为根节点；
• 每一个非根节点有且只有一个父节点；
• 除了根节点外，每个子节点可以分为多个不相交的子树；
• 树里面没有环路，即单向无环；

为什么要使用树？

为什么要使用树，我们可以从两个面来分析：

• 与线性数据结构如数组和链表不同，树是层次结构（或非线性）数据结构，而在现实世界中往往需要存储一些自然形成的层次结构信息，例如计算机文件系统。
• 我们常用的线性数据结构，他们的查询复杂度都是，而树这种结构的查询复杂度可以到。

树相关的基本概念

树的基本概念

• 节点的度：一个节点含有的子树的个数称为该节点的度；
• 树的度：在一棵树中，最大的节点度称为树的度；
• 叶子节点：度为0的节点；
• 父节点：若某个节点存在子节点，那么这个节点就是父节点；
• 根节点：没有父亲的节点称之为根节点；
• 兄弟节点：具有相同父节点的多个节点相互称作兄弟节点；
• 高度：任意节点与所有叶子节点中路径最长的节点间的径长；
• 深度：任意节点与根节点的路径长度；

树的分类

树族谱

树族谱相关简介：

• 从大的分类讲，树可以分为：无序树、有序树，我们主要讲有序树部分；
• 在有序树的大分类中可以划分为：二叉树与多叉（路）树；
• 多叉（路）树可分为：多路查找树与多维空间数据分隔树；
• 多路查找树按照平衡性又划分为：平衡多路查找树与多路查找树，他们的代表性实现分别是B+树、前缀树（也称字典树）。
• 树家族中最庞大的分支是大家耳熟能详的二叉树了，二叉树不但有着众多的子孙后代，其中还包含了一些与其他数据结构结合产生的混血树，二叉堆就是其中之一。
• 二叉树按照构型可以分为：斜树、完满二叉树、满二叉树和完全二叉树。
• 二叉树按照功能性划分：二叉查找树、哈夫曼树、哈希树、线索二叉树等等。
• 二叉查找树是其中最大的一个分支，在二叉查找树中自平衡二叉查找树的变种和实现非常的多，经典的AVL树、红黑树等等都是大家经常接触使用的。

接下来我将一一介绍树族谱中的所有树。

二叉树（Binary Tree）

首先我们来看树族谱中最大的一个分支：二叉树（Binary Tree）。

斜树

左斜树：所有的节点都在左子树。

右斜树：所有的节点都在右子树。

左/右斜树

满二叉树（Perfect Binary Tree）

满二叉树又称完美二叉树，其叶子节点都在同一层，所有的非叶子节点都有两个子节点。

满二叉树

完全二叉树（Complete Binary Tree）

除了最后一层之外的其它每一层都被完全填充，且所有的叶子节点向左紧密排列。

完全二叉树

完满二叉树（Full/Strictly Binary Tree）

除了叶子节点之外的所有节点都有两个叶子节点。

完满二叉树

二叉查找树（Binary Search Tree）

二叉查找树又称二叉搜索树、二叉排序树、BST。二叉查找树有以下明显特征：

• 若任意节点N的左子树不为空，则左子树上的所有节点的值都小于等于节点N的值。
• 若节点N的右子树不为空，则右子树上的所有节点的值都大于等于节点N的值。

从上面的两个特性可以总结出，二叉查找树的任意子树都是一个二叉查找树。

二叉查找树

操作时间复杂度：

• 查询：最好时间复杂度O(logN)，最坏时间复杂度O(N)。
• 插入/删除：最好时间复杂度O(logN)，最坏时间复杂度O(N)。

使用场景：

• 使用期实现简单的排序算法；
• 可以用去实现优先级队列（这个后续我会细讲）；

二叉查找树在最坏的情况下竟然和顺序查找效率相当了，造成这种情况的主要原因就是二叉查找树不够平衡，在树足够大时，左右子树的高度差就会非常大，为了解决这一问题，平衡树诞生了。

平衡二叉树（AVL Tree）

平衡二叉树又称平衡二叉查找树、平衡二叉排序树、AVL树。平衡二叉树具有以下特性：

• 其本质是一颗二叉查找树，因此二叉查找树具有的特性它都具有。
• 任意节点N的左右子树高度差绝对值不超过1。

平衡二叉树

操作时间复杂度：

• 查询：不会出现二叉查找树的不稳定情况，其时间复杂度稳定在O(logN)。
• 插入：因为要保持插入后的平衡性，每次插入最多需要一次旋转，其时间复杂度在O(logN)左右。
• 删除：执行删除操作的时间复杂度为O(2logN)，代价稍大。

使用场景：

• AVL树的是第一种实现平衡的二叉树，它本身应该被广泛应用，可惜的是既生瑜何生亮，更优秀的算法红黑树被发明，因此其很多应用场景都被红黑树代替了。

平衡二叉树的严格平衡策略换来的查询时间复杂度，其代价也非常的昂贵，它的代价是以牺牲其插入和删除性能换来的。我们更希望找到一种更加折中的策略，也就是既能减少平衡策略所带来的额外开销，又能保证高效的查询效率，红黑树应运而生。

红黑树（Red Black Tree）

红黑树是一种含有红、黑两种节点，并且自平衡的二叉查找树，其具有以下性质：

• 每个节点要么是红色，要么是黑色。
• 根节点是黑色的。
• 叶子节点是黑色的（叶子节点为NIL节点），也就是说不会有红色的叶子节点。
• 若一个节点是红色的，那么其必然拥有两个黑色子节点。
• 任意一个节点到叶子节点路径中所包含的黑色节点数相同。

红黑树

操作时间复杂度：

• 查询：最好时间复杂度O(logN)，但在最坏情况下比AVL树要差，但是远优于BST的O(N)。
• 插入/删除：因为在红黑树的插入和删除操作会导致其不再符合性质，从而需要不超过三次的树旋转（插入操是两次）和少量的颜色变更操作（变色时间复杂度为O(logN)）。

使用场景：

• Java中的TreeSet与TreeMap以及1.8之后的HashMap等都用到了红黑树；
• Linux的虚拟内存管理；

关于红黑树的旋转变色算法，本文将不过多阐述，后续会在数据结构系列博文详细讲解。

替罪羊树(Scapegoat Tree)

替罪羊树是一种基于部分重建的自平衡二叉查找树，其关键点就在于部分重构。它的平衡策略不同于AVL树、红黑树等的旋转策略，它是所有平衡树中思路最简单的一种结构，它的策略是：

• 当发生插入操作后，从插入的位置开始一层层往根节点方向回溯，期间每一层都会进行，直到某一层不满足该条件，然后将以该层作为根的子树进行平衡性重构，该根节点就是替罪羊节点，重构的树称为替罪羊树（这也就是替罪羊树名称的由来，子节点发生变化而导致兄弟及父辈们全部发生变更）。
• 删除操作是逻辑删除，也就是只做删除标记，查询的时候会过滤掉有删除标记的节点，当树发生重构时在进行物理删除（这个和ES删除思路一致，先做逻辑删除，在Segment合并时物理删除）。

替罪羊树重构过程

操作时间复杂度：

• 查询：其查询时间复杂度稳定在O(logN)。
• 插入：均摊时间在复杂度左右O(logN)。
• 删除：执行删除操作的时间复杂度为O(logN)。

使用场景：

• 相较于红黑树的广泛应用，替罪羊树的应用不是很多，目前只在算法竞赛中有它的身影。

伸展树(Splay Tree)

伸展树也是一种自平衡的二叉查找树，它继承二叉查找树的性质，具体如下：

• 继承二叉查找树的所有性质；
• 能够实现自平衡；
• 最近被访问的数据可以被快速访问到，其也因此性质而得名伸展树；

伸展树

在执行查询、删除或者插入操作之后，伸展树将执行伸展操作，通过旋转操作将特定的元素放置到树的根部（结合特性3是不是第一时间就想到了LRU缓存算法，唯一不同的是伸展树不会淘汰数据），越热的数据就在树的根部周围，冷数据则在树的底部。

操作时间复杂度：

• 查询/插入/删除：其均摊时间复杂度在O(logN)。

使用场景：

• 因其特性3，它可以用作缓存管理。
• 可用其实现垃圾回收。

树堆（Treap）

树堆Treap一词是由Tree与Heap二词合成而来，它本身是一颗二叉查找树，它具有以下特性：

• Treap为每一个节点除了有值之外还记录了优先级；
• 值的排列遵循二叉查找树的全部规则；
• 而优先级是按堆的规则排列；

树堆

如上图，字母是按照二叉查找树的规则排列；而红色的数字是优先级，按照堆性质排列的。当每次插入新的节点会为其随机生成一个优先级，堆性质的维护使用到了旋转，这与其它平衡二叉树的操作基本一样。但与其它平衡类二叉树最大的不同在于，在所有节点优先级不变的情况下，不管是序列化后再反序列化，还是其它符合要求的操作，最终得到的树都是一样的。

操作时间复杂度：

• 查询/插入/删除：其均摊时间复杂度在O(logN)。

使用场景：

• 它的随机插入特性，使得其可以成为一种高效的动态数据容器。

总结

• 树族谱中主要分为二叉树与多路查找树量大分支。
• 二叉树与多路查找树附加平衡性策略又分别形成了平衡二叉查找树与平衡多路查找树两个大分支。
• 树与其它的数据结构相结合也形成了如树堆、二叉堆等混血结构。
• 红黑树、伸展树、替罪羊树、树堆等都是用不同的策略实现的平衡二叉树，为的就是降低操作的时间复杂度。
• 红黑树是通过红黑节点排列策略，以及变色相关操作实现平衡性的，其实算法现复杂。
• 替罪羊树是通过将打破其平衡规则的子树拍扁，然后重新构建的策略来实现平衡的，其算法实现较为简单。
• 伸展树是具有LRU相关算法的性质，它是通过旋转来实现平衡性的。
• 树堆是通过一个优先级属性，通过保证优先级属性的堆排列性质来实现树平衡性的。

受篇幅的影响，本文只介绍了树族谱中最大的一个分支二叉树相关的数据结构，后续还会介绍一些其它类型二叉树以及多路查找树。

以上就是本章介绍的所有内容，后续的博文中我会介绍更多相关数据结构，如果你看了本文后有所收获就请给作者一个关注+点赞吧！