线段树的递归实现 1 of 2: 构造、查询及更新(翻译)

本文翻译自https://leetcode.com/articles/recursive-approach-segment-trees-range-sum-queries-lazy-propagation/,如有侵权请直接Email我

简介

什么是线段树(Segment Tree)

线段树是一种二叉树,树中的每一个节点代表一段区间。通常一个节点储存这个区间的一个或多个属性用于后续查询。

What is a Segment Tree
What is a Segment Tree

为什么要使用线段树(它的特点是什么)?

许多问题需要我们给出数据集在某个区间或者片段内的查询结果。特别是当出现大量、重复的查询时,这类操作会变得冗长或缓慢。一个线段树可以让我们在对数级时间复杂度内得到这类问题的查询结果。

线段树在计算集合学、GIS等领域有相关应用。例如,我们可能会在距离某个中心点/原点附近一段距离的空间范围内有大量的参考点。假设我们需要查询距离原点指定距离范围内的相关参考点。一个普通的查询表需要线性阶的时间来扫描所有的点或所有可能的距离(想一下hash map)。线段树允许我们在对数时间内解决这个问题,并且拥有更少的空间消耗。这类问题被称作 Planar Range Searching。高效解决这类问题是至关重要的,特别是在处理那些快速变换、无法预知的动态数据时(例如,一个空管雷达系统)。

本文稍后会解决区间和查询问题(Range Sum Query Problem)作为一个例子,借此说明线段树是如何节省空间及实时代价。

我们将会使用上图作为一个实例来介绍用于“区间和查询”的线段树它长什么样,以及有何特性。

如何生成一个线段树

我们将数据保存在大小为n的数组 arr[] 中。

  1. 线段树树的根通常表示整个数据的区间范围,即 arr[0:n-1] ;
  2. 树的每一个叶节点表示单个元素(或只有一个元素的区间)。因此叶节点表示的数值为 arr[0] , arr[1] 直至 arr[n-1] ;
  3. 树的非叶节点表示其子节点合并(merge/union)后的结果;
  4. 每一个子节点都能表示其父节点一半的区间范围;

一个包含n个元素范围的线段树可以用一个\approx 4 * n大小的数组表示。(其原因在StackOverflow上有详尽的讨论。如果你仍不相信,没关系,我们稍后会进一步讨论。)

怎么(用数组)存呢?

思路很简单:一个索引号为i的节点,他的子节点的索引号为(2*i+1)以及(2*i+2).

在使用递归方法构建时,线段树非常直观且容易使用。

线段树的递归方法

我们将使用数组 tree[] 来保存线段树(用0值初始化)的节点属性。以下是具体的存储方案(使用以0开始的索引号):

  • 树的根节点索引为0,即 tree[0]
  • 节点 tree[i] 的子节点存储在 tree[2*i+1] 及 tree[2*i+2] 中
  • 当数组元素数量不是2的k次方(如2,4,8,16,32…)时,用  0  或 null 填充不足的元素值
我们真的需要用0填充么?

不完全是。只是需要保证tree[]足够大,并且初始值都是0,而且不需要担心额外的叶节点没有被处理过。

  • 叶节点的索引范围是2^k-12^(k+1)-2

我们只需要下列三个方法:

1.根据给定数据构造线段树

该方法自下而上地构造整个 tree 。当满足条件lo=hi时,我们处理的区间只包含单个元素(即 arr[lo] )。这就是树的叶节点。余下的非叶节点通过合并其子节点的结果构造而成。 treeIndex 是当前正在处理的线段树的索引号。

举个例子,上图中的树可以由下面的输入数据构造出:(本文通篇都会使用这个例子)

你能猜到本例中的 merge 操作是什么吗?在构造完毕后, tree[] 数组看起来是这样的:

注意到 tree[] 数组末尾的那些0了么?这些就是我们用来填充树,使之成为完全树的 null 值(因为我们只有10个叶节点。假若我们有16个叶节点,我们就不需要用 null 填充了。你能证明为什么吗?)

注意:对于不同的问题, merge 操作是不同的。在构造线段树之前,你需要仔细考虑到底在线段树的节点中需要存什么数据,以便在合并的时候能够给出最终的结果。

2. 读取/查询数据区间或片段

在查询的范围完全匹配当前节点的范围时,该方法返回一个结果。否则,它将深入树的下一层来寻找满足(部分)查询范围的节点。

这就是线段树的美丽所在

在上述例子中,我们试图找到[2,8]范围内的节点值的和。没有一个区间能直接满足搜索范围[2,8]。然而,我们发现范围[2,8]可以由几个小范围[2,2], [3,4], [5,7], [8,8]来表示。验证一下,我们可以看到索引范围在[2,8]的节点值,他们的和是13+19+15+11+20+12+33=123。而刚才提到的那些小区间[2,2], [3,4], [5,7], [8,8],他们所对应的节点的和是13+34+43+33=123.

3.更新元素的值

这个操作类似于 buildSegTree 。我们根据更新请求来更新对应的叶子节点。随后这些变更向上传递到其父节点。

在这个例子中,位于(输入数据中)索引1,3和6的元素,他们的值对应增加了+3, -1与+2。从图中可以看出这些值是如何向上传递更新,直至根节点的。

复杂度分析

我们来看一下 build 过程。我们会访问线段树的每个叶节点(对应到输入数组 arr[] 中的每个元素)。这就形成了n个叶节点。此外我们还有n-1个非叶节点。因此总共会有约2*n个节点。这样说来整个构造树的过程的会在O(n)即线性时间内完成。

update 过程在达到目标叶节点的过程中,在递归的每一层都会丢弃一半的范围。这个过程类似于二分搜索,需要对数级的时间。在叶节点更新过后,它的每一个直系父节点也都将被更新,这个过程耗费的时间是树的高度的线性级别。

read/query 过程按照深度优先遍历树,寻找符合搜索条件的节点范围。在最优情况下,我们的范围大于或等于根节点的范围,此时直接能从根节点得到结果。最差情况下,我们搜索一个长度为1的范围(对应于线段树中的一个叶节点),此时我们访问的节点个数等于树的高度;即搜索的时间复杂度和树的高度线性相关。

这就是之前说过的:

一个含有n个元素范围的线段树可以用一个大小约为4*n的数组表示

这保证了我们我们生成的线段树是一个完全二叉树,进一步又保证了这棵树高度的上界是输入规模的对数级。

Viola! 不论是 read 还是 update 的查询都只需要对数级的O(log_2(n))时间,这正是我们想要的。

LeetCode 173. Binary Search Tree Iterator

思路

画一个简单的BST,然后可以看出有三种情况

  • 如果当前节点有右孩子,那就在右子树里找到值最小的那个,显然是右子树里最左下侧的那个节点
  • 如果当前节点没有右孩子,由于左子树的值肯定都比当前节点的值小,左右要找父节点
    • 如果找到某个父节点的值比当前节点值大,那这个父节点就是下一节点
    • 否则,当前节点就是最后一个节点

因此,需要一个栈结构记录当前节点的父亲们(有点像调用栈)。

测试例:NULL根节点,只有一个节点,只有单侧树

代码

 

LeetCode 116. Populating Next Right Pointers in Each Node

思路

发现是一个树的遍历的题目,而且题目限制的比较死,是个满二叉树,这样处理的时候就避免了比较烦人的跨树指针的情况。比如下面这种建立4->5的指针:

第一时间想到的解法是弄个工作队列,然后一层一层遍历下去就行了,这个解法的空间复杂度是O(n),不符合题目要求。后来再一想,其实既然上一层已经把下一层的next指针建立好了,就不用再从工作队列里去“回忆”了,只要在每一行的开头记住下一行在哪里就行,这样只要O(1)空间复杂度。

另外是如何设置next指针,一共有两个情况:

  1. node自己的左孩子和右孩子连起来
  2. node的右孩子与node右侧节点它的左孩子连起来

代码

O(n)空间复杂度方法

O(1)空间复杂度方法

 

B+树的一些资料,留着备用

近期数据库老师要求写一个B+树,还是要存储在磁盘上的,暂时收集到下列资料: