# Geometric Applications of BST

## 1-D Range Search

This is the extension for symbol table.

* Insert key-value pair.
* Search for key `k`.
* Delete key `k`.
* **Range search:** Find all keys between `k1 & k2`.
* **Range count:** Number of keys between `k1 & k2`.

![](/files/ZVPvQBDYwEIieJL29CsF)

**Implementation**

* **Un Ordered List**: Fast Insertion and slow search
* **Ordered List**: Slow insert, binary search for k1 and k2 to do range search.

### BST Implementation

**Example1:**

![](/files/xGWFCPGPzPCxwvGibtGf)

**Java code to find the number of keys between** `low` **and** `high`

```java
// Running time is proportional to log(n)
public int size(key low, key high) {
    if(contains(high)){
        return rank(high) - rank(low) + 1;
    } else {
        return rank(high) - rank(low);
    }
}
```

**Example 2:**

![](/files/S329aCrc3zAQvGT9H0bg)

## Line Segment Intersection

Given N horizontal and vertical line segments, find all intersections.

![](/files/96QUUDX7vVcMAFiRJpc5)

### Sweep-line algorithm

Sweep vertical line between left to right and record your observations

**Algorithm:**

* x-coordinates define events.
* **h-segment (left endpoint):** insert y-coordinate into BST.
* **h-segment (left endpoint):** insert y-coordinate into BST.
* **v-segment:** Range search for interval of y-end points.

**Explanation:**

* Put x-coordinate in PQ (or Sort ) . -------------> `N * log(N)`
* Insert y-coordinate into the BST . -------------> `N * log(N)`
* Remove y-coordinate from the BST -------------> `N * log(N)`
* Range Searches in BST -------------> `N * log(N) + R`

## 1D Interval Search Trees

Data structure to hold the set of overlapping intervals.

Create BST, where each node stores an interval `(lo, hi)`.

* Use left endpoint as BST key.
* Store max endpoint in subtree rooted at node.

![](/files/HhG5r9KywJN4aezmVN17)

### Algorithm

* If interval in node intersects query interval, return it.
* Else if left subtree is null, go right.
* Else if max endpoint in left subtree is less than lo, go right.
* Else go left.

![](/files/RPeqnOCJ9g6iUJmYtzkT)

### Java Implementation

```java
..............

 TreeNode x = root;
 
 while(x!=null){
     if(x.interval.insersects(lo,hi)){
         return x.interval;
     }else if(x.left == null) {
         x = x.right;
     }else if(x.left.max < lo){
         x = x.right;
     }else {
         x = x.left;
     }
 }

return null;

..............
```

### Interval Search Tree Analysis

**Implementation:** Use a red-black BST ( easy to maintain auxiliary information using log N extra work per op ) to guarantee performance.

![order of growth of running time for N intervals](/files/5eabLIVaX4sZFUOTDWrn)

## Orthogonal rectangle intersection

**Goal**: Find all intersections among a set of N orthogonal rectangles.

![](/files/yY53drrDANORD2LZfTiV)

Here we use the same principle sweep line algorithm. Sweep one vertical line from left to right. when you encounter left end point insert y interval. and repeat the interval search until you get the right end point.

### Algorithm

* x-coordinates of left and right endpoints define events.
* Maintain set of rectangles that intersect the sweep line in an interval search tree (using y-intervals of rectangle).
* **Left endpoint:** Interval search for y-interval of rectangle; insert y-interval.
* **Right endpoint:** Remove y-interval.

![Orthogonal Rectangle Intersection](/files/7NeXOowB6ODRcyPt3pev)

**Analysis**

* Put x-coordinate in PQ (or Sort ) . -------------> `N * log(N)`
* Insert y-coordinate into the BST . -------------> `N * log(N)`
* Reomve y-coordinate from the BST -------------> `N * log(N)`
* Interval Search for y Coordinates -------------> `N * log(N) + R * log(N)`

## Summary

![](/files/06zIJdBFSnYEWjpfQpRt)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.sunilgudivada.dev/notebook/data-structures-and-algorithms/topics/binary-search-tree/geometric-applications-of-bst.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.