数据结构中的区间树

在本节中，我们将介绍区间树。顾名思义，区间树就是与区间相关联的树。因此在讨论区间树之前，让我们来看一下基本区间。

一个区间基本上是一个范围。因此，如果一个区间写成 [a, b]，它表示范围从 a 开始到 b 结束。

现在假设有一个区间 [10, 20]。因此有三个范围值。第一个是 -∞ 到 10，10 到 20，最后是 20 到 ∞

现在，假设我们将创建第二个区间 [15, 25]。所以这将是这样的 −

从 [18, 22] 创建另一个区间，所以它将是这样的 −

因此有不同的区间和子区间。它们如下

区间名称区间范围子区间
区间 1[10, 20][10, 15], [15, 18], [18, 20]
区间 2[15, 25][15, 18], [18, 20], [20, 22], [22, 25]
区间 3[18, 22][18, 20], [20, 22]

我们可以从这些信息中构建一个区间树。子区间将被放置在子树中。

在区间树中，每个叶子节点都表示每个基本区间。在这些叶子之上，构建了一个完全二叉树。

于: 2020 年 8 月 11 日更新

2K+ 次浏览

开启你的 职业生涯

完成课程获认证

立即开始
广告