获取时间间隔内的数据库数据_数据结构中的间隔树

柔情只为你懂 2023-03-05 12:41 4阅读 0赞

获取时间间隔内的数据库数据

## 间隔树 **(**Interval Tree**)** ##

Interval tree is a [Red-black Tree][] in which each node has an interval represented by an ordered pair \[t1, t2\] such that t1 < t2.

间隔树是一棵 [红黑树][Red-black Tree] ，其中每个节点都有一个由有序对\[t1，t2\]表示的间隔，使得t1 <t2。

Here, **t1** is called lower end point and **t2** is called higher end point. If both the endpoints are mentioned in the nodes of the tree than it is called **closed Interval tree**. If we omit both the ends points then it is called an **open interval tree** and if we omit one end of the endpoints from the set then it is called **half-open interval**. In this section, we will discuss an interval tree with a closed interval.

在此，将**t1**称为下端点，将**t2**称为上端点。 如果在树的节点中都提到了两个端点，则将其称为“ **封闭间隔树”** 。 如果我们省略了两个端点，则将其称为**开放间隔树** ；如果我们从集合中省略端点的一端，则将其称为**半开放间隔** 。 在本节中，我们将讨论具有封闭间隔的间隔树。

The interval tree is a useful data structure for the database of real-time applications, the interval tree is a useful data structure for representing the events.

间隔树是实时应用程序数据库的有用数据结构，间隔树是用于表示事件的有用数据结构。

If the **interval \[t1,t2\]** is for an object **i** then **low \[i\] = t1** and **high \[i\] = t2**. There could be another **interval tree t2** which is overlapping with **t1** or **t2**. The **interval tree** for the following set of the interval,

如果**间隔\[t1，t2\]**用于对象**i，**则**低\[i\] = t1**和**高\[i\] = t2** 。 可能有另一个**间隔树t2**与**t1**或**t2**重叠。 以下**间隔**集的**间隔树** ，

If there are two intervals **i** and **i'** the following conditions can be possible:

如果存在两个间隔**i**和**i'** ，则可能出现以下情况：

1.  If **i** and **i'** overlap then **low\[i\] <= high \[i'\]** and **low \[i'\] <= high\[i\]**.
    
    如果**i**和**i'**重叠，则**low \[i\] <=高\[i'\]**和**low \[i'\] <= high \[i\]** 。
2.  If there are no overlapping intervals then **high\[i\] < low\[i'\]**.
    
    如果没有重叠间隔，则**high \[i\] <low \[i'\]** 。
3.  If the interval do not overlap **high \[i'\] < low\[i\]**.
    
    如果间隔不重叠，则**高\[i'\] <低\[i\]** 。

### 间隔树的增强 **(**Augment of Interval Tree**)** ###

let us now augment the interval tree data structure.

现在让我们增强间隔树数据结构。

**Step 1)** Choose the data structure which has to be augmented.

**步骤1)**选择必须扩充的数据结构。

We will choose a red-black tree with intervals. The inorder traversal of interval tree with low-end point gives the key value of each node.

我们将选择一个带有间隔的红黑树。 低端间隔树的有序遍历给出了每个节点的关键值。

**Step 2)** find out the additional information that is needed to support the algorithm.

**步骤2)**找出支持算法所需的其他信息。

Each node K contain a value max\[k\] which is the maximum value of any interval endpoints. This maximum value can be obtained using the following formula.

每个节点K包含一个值max \[k\]，它是任何间隔端点的最大值。 可以使用以下公式获得该最大值。

Max [k] = max(high[int[k]]), max[left[k]], max[right[k]])

**The interval tree can be shown with augmented data structure as:**

**间隔树可以用增强的数据结构显示为：**

![Interval Tree in D.S.][]

Consider a root node \[19, 22\] for which we want to find max value then:

考虑一个我们想要为其找到最大值的根节点\[19，22\]，然后：

=   max(high (node [19,22]), max(left[19,22])), max(right[27,35])))
        =   max (22, 21, 35)
        =   35

Hence, in the **max** field of root node we put the value **35**.

因此，在根节点的**max**字段中，我们输入值**35** 。

**Step 3)** Verification of additional information

**步骤3)**验证其他信息

With this additional field of max, the insertion and deletion operation do not lose their performance efficiency. The insertion and deletion can be performed in O(log n).

使用max的此附加字段，插入和删除操作不会失去其性能效率。 可以在O(log n)中执行插入和删除操作。

**Step 4)** Develop a new operation for additional information.

**步骤4)**开发新操作以获得更多信息。

Using the additional information max field we can search the desired node in interval tree using the following algorithm.

使用附加信息max字段，我们可以使用以下算法在间隔树中搜索所需的节点。

## 间隔树中的搜索算法 **(**Algorithm for searching in Interval Tree**)** ##

**INTERVAL SEARCH (T, i) -**  returns a pointer to an element X in the interval tree t such that int \[x\] overlap i1 on the sentinel nil \[T\] if no such element is in the set.

**INTERVAL SEARCH(T，i)-**返回指向间隔树t中元素X的指针，以使int \[x\]在前哨nil \[T\]上与i1重叠。

INTERVAL SEARCH (T, i)
        1.	 x = low [i].
        4.	Then x 
     Analysis
     If the height of the red-black tree is n than each operation takes O(1) time and the whole procedure searching will be executed in O(log n) time. Hence, time complexity of this algorithm is O(log n).
    
    
    
    
    
    
       
        TOP Interview Coding Problems/Challenges Run-length encoding (find/print frequency of letters in a string) Sort an array of 0's, 1's and 2's in linear time complexity Checking Anagrams (check whether two string is anagrams or not) Relative sorting algorithm Finding subarray with given sum Find the level in a binary tree with given sum K Check whether a Binary Tree is BST (Binary Search Tree) or not 1[0]1 Pattern Count Capitalize first and last letter of each word in a line Print vertical sum of a binary tree Print Boundary Sum of a Binary Tree Reverse a single linked list Greedy Strategy to solve major algorithm problems Job sequencing problem Root to leaf Path Sum Exit Point in a Matrix Find length of loop in a linked list Toppers of Class Print All Nodes that don't have Sibling Transform to Sum Tree Shortest Source to Destination Path Comments and Discussions Ad: Are you a blogger? Join our Blogging forum. Please enable JavaScript to view the comments powered by Disqus.

> 翻译自: [https://www.includehelp.com/data-structure-tutorial/interval-tree.aspx][https_www.includehelp.com_data-structure-tutorial_interval-tree.aspx]

获取时间间隔内的数据库数据

[Red-black Tree]: https://www.includehelp.com/data-structure-tutorial/red-black-tree.aspx
[Interval Tree in D.S.]: /images/20230208/2f1a0815885f4ca69ddfa5dd6ca4f5d8.png
[https_www.includehelp.com_data-structure-tutorial_interval-tree.aspx]: https://www.includehelp.com/data-structure-tutorial/interval-tree.aspx