什么是二叉树？

语言: CN / TW / HK
时间 2022-11-29 11:15:06

theme: jzman

本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。

前言

大家好，我是小彭。

在前面的文章里，我们聊到过数组、链表、栈和队列等基础数据结构，也聊到过它们的一些衍生数据结构，例如 单调栈、单调队列、散列表 等等，这些都是线性表或者是以线性表为主体的数据结构。

从这篇文章开始，我们来讨论非线性的数据结构 —— 树和图。非线性数据结构相比于线性表结构要复杂得多，涉及到的内容也更广。虽然树也是一种特殊的图，但是考虑到树的特点更容易理解也更常用，所以我们把树单独分类，而把图当成树的衍生数据结构。

今天，我们就先从树的基本概念开始，并逐渐延伸到二叉堆、红黑树、线段树、树状数组、图等更复杂的数据结构上，请关注。

思维导图：

1. 隐藏在递归代码中的树

其实，很多代码中都存在树型结构，比如递归代码。

递归 是一种通过 “函数自己调用自己” 的方式，将问题重复地分解为同类子问题，并最终解决问题的编程技巧。当你在使用递归思想解决问题的时候，往往你也是在使用树型结构解决问题。

举个例子，要求一个数 $n$ 的阶乘 $n! = n(n-1)(n-2)…2*1$ 。如果使用递归思想解决问题是，我们可以把 $n!$ 的问题拆分为一个 $(n-1)!$ 的问题，如果我们知道 $(n-1)!$ 的解，那么将它乘以 $n$ 就可以得出 $n!$ 的解。以此类推。

求 n!

由于阶乘在每次递归调用时，原问题和子问题只是 “线性” 地减少一个问题规模，所以这里面的树型结构可能还不太明显。 那我们可以再举一个稍微复杂的例子：求斐波那契数列，LeetCode · 509. 斐波那契数：该数列从 $1$ 开始，每一项数字都是前面两项数字的和。

这个问题我们可以使用递归的方式自顶向下地分解问题，在编码上是很容易实现的。如果我们把代码一层层分解的过程画成图形，我们会发现代码自然地形成了一个树。 这棵在递归调用中隐式存在的树我们也称之为递归树。

递归（未优化）

kotlin class Solution { fun fib(N: Int): Int { if(N == 0){ return 0 } if(N == 1){ return 1 } // 拆分问题 + 组合结果 return fib(N - 1) + fib(N - 2) } }

递归是一种树型结构

2. 什么是树（Tree）？

2.1 树的逻辑结构

树这种数据结构与现实中的 “树” 在形态上非常相似， 树的逻辑结构是一种非线性结构，相邻的父子节点形成 1 对 N 的关系，树的节点中包含元素值和所有子节点的列表。

从这阶乘和斐波那契数列的例子可以看出，线性表和树在结构上的主要区别在于相邻节点的引用关系上：

  • 1、线性结构： 前驱节点和后继节点的引用关系为 1 对 1；
  • 2、树型结构： 前驱节点和后继节点的引用关系为 1 对 N；
  • 3、图型结构： 再进一步延伸，当前驱节点和后继节点的引用关系为 N 对 N 时就是图型结构。如果按照图的理论来说，树可以看作是一种特殊的图，即包含 N 个节点和 N - 1 条边的有向无环图，树的方向是从根节点指向叶子节点。

2.2 树的物理实现

树的物理结构可以采用数组或链表实现：

  • 1、链表实现： 即通过引用来建立节点之间的父子关系，每个节点都持有子节点的引用。树的链表实现更简单直接，所以大部分的二叉树代码也是通过链表结构来实现的；
  • 2、数组实现： 即通过数组下标来建立节点之间的父子关系，节点内部不需要存储子节点引用的内存空间。

在额外内存消耗上，链表实现在子节点指针有额外内存占用，而数组实现会在数组本身上存在额外内存占用。如果树是一棵非常稀疏的树的话，树的数组实现会导致数组中存在非常多的闲置空间。

树的数组实现有 2 种计算节点位置的方式：

  • 方式 1 - 根节点存储在第 [0] 位：

    • 对于第 [i] 位上的节点，第 [2 * i +1] 位是左节点，第 [2 * i + 2] 位是右节点；
    • 对于第 [i] 位上的节点，第 [(i-1) / 2] 位是父节点。

  • 方式 2 - 根节点存储在第 [1] 位：

    • 第 [0] 位不存储，根节点存储在第 [1] 位
    • 对于第 [i] 位上的节点，第 [2 * i] 位是左节点，第[2 * i + 1] 位是右节点
    • 对于第 [i] 位上的节点，第 [i / 2] 位是父节点

2.3 树的基本概念

  • 深度（Depth）： 表示节点到根节点的距离（可以参考递归栈的深度理解，递归越深的节点深度越大）；
  • 层级（Level）： 也是表示节点的深度，数值是深度 + 1；
  • 高度（Height）： 表示节点到叶子节点的距离；
  • 宽度： 表示一层节点中最左节点与最右节点之间的长度（两端之间的空节点也计入宽度）；

2.4 树的路径

  • 路径 / 最短路径： 指两个节点之间经过的所有节点。由于树是有方向的，因此路径一定会经过两个节点的最近共同祖先，树中的路径概念本身就是最短路径；
  • 距离 / 最短距离： 即路径长度，指两个节点的路径上所有边的个数。同理树中的距离概念本身就是最短距离；
  • 权： 表示一个节点的权重；
  • 带权路径长度： 表示一个节点到根节点的路径长度与节点权重的乘积；
  • 树的带权路径长度： 表示一棵树中所有节点的带权路径长度之和，简称 WPL，Weighted Path Length of Tree；
  • 最优树： 表示带权路径长度最小的树，即哈夫曼树。哈夫曼树其实只是生成哈夫曼编码的一个工具，我们在专栏后续文章里再讨论。

树的路径

3. 二叉树与特殊二叉树

前面我们将的树都是普通的树的特征，也叫多叉树，即节点的子节点个数不固定，可以是一个，两个或者多个。不过我们最常见的还是二叉树，即每个节点最多只有两个子节点，分别是左子节点和右子节点。

下面讨论常见的几种特殊的二叉树：

3.1 满二叉树（Full Binary Tree）

对于一棵满二叉树来说，任何一棵子树上都是满二叉树。

满二叉树的每一层节点都是铺满的，除了最底层的节点外，所有节点都有左右两个子节点，所有的叶子节点也集中在树的最底层。

3.2 完全二叉树（Complete Binary Tree）

对于一棵完全二叉树来说，任何一棵子树都是完全二叉树。

完全二叉树与满二叉树类似，但没有那么 “满”。除了最底下两层节点外，大部分节点都有左右两个子节点，所有的节点也都铺满在树的左上角，所有的叶子节点都几种在树的最底下两层。

那么，为什么要定义完全二叉树这种数据结构呢？这就需要跟稀疏的树做相比了。稀疏的树如果用数组实现的话，会存在非常多的闲置空间。而完全二叉树或满二叉树能够完全利用数组的所有空间或前部分空间，数组的利用率更高。

3.3 二叉搜索树（Binary Search Tree，BST）

对于一棵二叉搜索树来说，任何一棵子树上都是二叉搜索树。

在二叉搜索树中，树中的任意一个节点的值，都大于（或小于）左子树上所有节点的值，且均小于（或大于）右子树上所有节点的值。

那么，为什么要定义二叉搜索树这种数据结构呢？ 这就需要跟链表做对比了，二叉搜索树是为了优化链表的查询效率而产生的。链表在进行查询、插入和删除时的时间复杂度是 O(n)，而在二叉查找树上进行查询、插入和删除时的时间复杂度是 O(Height)，与树的高度有关。

3.4 平衡二叉搜索树（Balance Binary Search Tree）

对于一棵平衡二叉树来说，任何一棵子树上都是平衡二叉树。

平衡二叉搜索树是一种特殊的二叉搜索树，简称就是平衡二叉树。在平衡二叉树中，任何节点的左右子树高度差不大于 1。

那么，为什么要定义平衡二叉树这种数据结构呢？ 这就需要跟二叉查找树做对比了，平衡二叉树能够避免二叉搜索树退化为链表。

在二叉查找树中，查找、插入、删除等操作的时间复杂度跟树的高度成正比，在最好情况下会优化为完全二叉树，而在最坏情况下会退化为链表，各项操作的时间复杂度也会退化 O(n)。而平衡二叉树会避免树的左右子树高度相差太大，各项操作的时间复杂度可以稳定在 O(logn)，但是在增加和删除操作上会增加维护平衡性的开销。

3.5 红黑树（Red-Black Tree，R-B）

平衡二叉树追求的是 “完全平衡” 的状态，但是考虑到维护树的平衡性本身也是一种成本，因此实践中使用的平衡二叉树往往是 ”近似平衡“ 或 ”弱平衡“ 的。即只保证左右子树高度相对平均，而不严格准守树的高度差不大于 1 的定义，通过牺牲一部分查找的效率，来节省维持树的平衡状态的成本。

这些 “弱平衡” 的红黑树虽然不符合平衡二叉树的严格定义，但一般也视为平衡二叉树。平衡二叉搜索树有很多种，例如伸展树（Splay Tree）、树堆（Treap）、红黑树（AVL），但其中最常见的莫过于红黑树。在 Java HashMap 的分离链表法中，就采用了链表 + 红黑树的方案。

红黑树的性质如下：

  • 1、节点非红即黑；
  • 2、Null 节点是叶子节点；
  • 3、根节点和 Null 叶子节点是黑色的；
  • 4、红色节点不会连续，红色节点的子节点一定是黑节点；
  • 5、任何节点到叶子节点的路径上黑色节点的数量。

红黑树的定义很复杂， 关键在于红黑树可以满足一个节点到叶子节点的最长路径的长度不超过最短路径的 2 倍， 所以红黑树不会出现左右子树特别不平衡的情况。

为什么呢？假设最长路径上存在 N 个黑节点和 N - 1 个红色节点，由于要满足 “5、任何节点到叶子节点的路径上黑色节点的数量相同”，所以最短路径上也存在 N 个黑节点。那么即使最短路径上一个红色节点都没有，至少也有 N 个节点，所以不会超过两倍。

3.6 二叉堆（Binary Heap）

对于一个二叉堆来说，任何一棵子树上都是二叉堆。

二叉堆是一种特殊完全二叉树，在二叉堆中，树中的任意一个节点的值，都大于等于（或小于等于）左右子树上所有节点的值。

二叉堆看起来和二叉搜索树很像，但其实两者差别很大，二叉堆也并不是二叉搜索树。在二叉搜索树中会要求节点与左右子树的关系是 “左子树 < 节点 < 右子树” ，而二叉堆只要求 “节点 > 左子树 and 右子树” 。所以，二叉搜索树中兄弟节 点之间也是有序的，而二叉堆不关心兄弟节点之间的相对关系，所以对于同一组数据，我们可以构建多种不同形态的堆。

3.7 哈夫曼树（Huffman Tree）

哈夫曼树与哈夫曼编码有关。

哈夫曼编码是一种变长编码，对出现频率高的字符采用较短的码元，对出现频率低的字符采用较长的码元，从而达到无损压缩编码长度的目的。哈夫曼树也成最优二叉树，是 WPL 带权路径长度最小的树。

其实，哈夫曼树就是生成哈夫曼编码的工具，通过哈夫曼树这个数据结构能够将 “设计最优编码” 的问题转换为求 “最小带权路径长度” 的问题。

4. 总结

今天，我们讨论了树的基本概念，也介绍了最常见的二叉树以及特殊的二叉树。在专栏接下来的文章中，我们会逐渐延伸到这些特殊的二叉树，请关注。

版权声明

本文为稀土掘金技术社区首发签约文章，14天内禁止转载，14天后未获授权禁止转载，侵权必究！

参考资料

  • 数据结构与算法分析 · Java 语言描述（第 4、6 章）—— [美] Mark Allen Weiss 著
  • 算法导论（第 6、12、13 章 · 散列表）—— [美] Thomas H. Cormen 等 著
  • 300分钟搞定算法面试 —— 力扣&拉勾网 出品
  • 数据结构与算法之美（第 23~29 讲） —— 王争 著，极客时间 出品

「」
「」