1. What is a KD-Tree?
A KD-Tree is a binary search tree used to organize k-dimensional vector
data.
Each node stores:
A k-dimensional point
A splitting dimension (x, y, z, …)
👉 It is mainly used for spatial searching such as:
Nearest neighbor search
Range search
Multidimensional indexing
2. Why KD-Tree is Needed
Traditional BST works only for 1-D data.
KD-Tree extends this idea to multi-dimensional space.
Example problem:
“Find the nearest hospital to a given location (x, y).”
➡ KD-Tree solves this efficiently.
3. Structure of a KD-Tree
Binary tree
Each level uses one dimension for comparison
Dimensions are chosen cyclically
Example (2-D):
Level Split Dimension
0 X-axis
1 Y-axis
2 X-axis
3 Y-axis
4. KD-Tree Construction (Step-by-Step)
Given Points (2-D):
(3,6), (17,15), (13,15), (6,12),
(9,1), (2,7), (10,19)
Step 1: Choose root (split by X)
Sort by X
Median → (9,1)
Step 2: Left subtree (X < 9)
Split by Y
Step 3: Right subtree (X > 9)
Split by Y
👉 Alternate dimensions at each level.
5. Example KD-Tree (2-D Conceptual)
(9,1) [X]
/ \
(2,7)[Y] (17,15)[Y]
/ \ /
(3,6) (6,12) (13,15)
6. Operations on KD-Tree
1 Insertion
Compare based on current dimension
Move left or right
Alternate dimension at each level
2 Search
Similar to BST, but comparison is dimension-based.
3 Range Search
Find all points inside:
Rectangle: x ∈ [5,15], y ∈ [5,20]
KD-Tree avoids searching unnecessary branches.
4 Nearest Neighbor Search (IMPORTANT 🔥)
Steps:
1. Traverse tree to reach leaf
2. Track current nearest point
3. Backtrack and check other subtrees if needed
4. Prune branches using distance comparison
➡ Faster than brute-force search
7. Time Complexity
Operation Average Worst
Construction O(n log n) O(n²)
Search O(log n) O(n)
Nearest Neighbor O(log n) O(n)
⚠ Performs poorly in very high dimensions (curse of dimensionality).
8. KD-Tree vs R-Tree
Feature KD-Tree R-Tree
Data type Points Spatial objects
Structure Binary tree Balanced tree
Best for Nearest neighbor Range queries
Dimensions Low–medium Any
9. Applications of KD-Tree
✔ GIS systems
✔ Computer graphics
✔ Image processing
✔ Pattern recognition
✔ Nearest location search
✔ Machine learning preprocessing
10. Advantages and Limitations
Advantages
✔ Efficient spatial searching
✔ Simple structure
✔ Good for low-dimensional data
Limitations
❌ Poor performance in high dimensions
❌ Unbalanced tree possible
❌ Static data (updates expensive)
11. Exam-Ready Definition ✍️
KD-Tree Definition:
A KD-Tree is a binary search tree that organizes k-dimensional points by
recursively partitioning the space using different dimensions at each level. It is
widely used for multidimensional search operations such as nearest neighbor
and range queries.
12. Short Example for Exams
Points: (2,3), (5,4), (9,6), (4,7)
Root (X split): (5,4)
Left subtree (Y split): (2,3)
Right subtree (Y split): (9,6)
1. What is an R-Tree?
An R-Tree (Rectangle Tree) is a height-balanced tree used to index spatial data objects
such as:
Points
Lines
Rectangles
Polygons
Instead of storing single values, it stores Minimum Bounding Rectangles (MBRs).
👉 Think of R-Tree as a B+ Tree for spatial data.
2. Why R-Tree is Needed
KD-Tree works well for points, but real GIS data includes:
Roads (lines)
Buildings (polygons)
Regions (areas)
R-Tree can index all of these efficiently.
Example problem:
“Find all hospitals inside this city area.”
➡ R-Tree solves this using rectangle overlap checks.
3. Basic Idea of R-Tree
Each node contains several MBRs
Each MBR encloses its child nodes
Tree remains balanced
Leaf nodes store actual spatial objects
4. Structure of an R-Tree
Node Types
🔹 Internal Node
[MBR1 | pointer1]
[MBR2 | pointer2]
[MBR3 | pointer3]
Each MBR covers all rectangles in its child.
🔹 Leaf Node
[MBR | ObjectID]
Stores real spatial objects.
5. Minimum Bounding Rectangle (MBR)
An MBR is the smallest rectangle that fully encloses an object.
Example:
Line → smallest rectangle covering the line
Polygon → bounding box around it
MBR = (xmin, ymin, xmax, ymax)
6. Example of R-Tree (Conceptual)
Suppose we have 6 buildings.
Step 1: Group nearby buildings
Step 2: Create MBRs
Step 3: Build hierarchy
Root MBR
/ \
MBR A MBR B
/ | \ / | \
Obj1 Obj2 Obj3 Obj4 Obj5 Obj6
7. Operations on R-Tree
1️⃣ Insertion
Steps:
1. Choose leaf with minimum area enlargement
2. Insert object
3. Update MBRs
4. Split node if overflow occurs
2️⃣ Search (Range Query)
Find all objects inside a region:
Query rectangle Q
Algorithm:
Start at root
Check overlapping MBRs
Visit only relevant branches
3️⃣ Deletion
Remove object
Adjust MBRs
Reinsert orphan nodes if needed
8. Node Splitting (Very Important 🔥)
When a node exceeds capacity:
Common Split Methods:
Linear split
Quadratic split
R*-Tree split (optimized)
Goal:
✔ Minimize overlap
✔ Minimize coverage area
9. Time Complexity
Operation Average
Search O(log n)
Insert O(log n)
Delete O(log n)
(Depends on overlap and distribution)
10. R-Tree vs KD-Tree
Feature R-Tree KD-Tree
Data Spatial objects Points
Structure Balanced tree Binary tree
Split Rectangular regions Axis-based
Best for GIS, maps Nearest neighbor
Overlap Allowed Not allowed
11. Applications of R-Tree
✔ GIS & Maps
✔ Google Maps / Navigation
✔ Spatial databases
✔ CAD systems
✔ Image databases
✔ Location-based services
12. Advantages and Limitations
Advantages
✔ Supports dynamic data
✔ Handles complex spatial objects
✔ Balanced tree structure
Limitations
❌ Overlapping MBRs reduce performance
❌ Complex implementation
13. Exam-Ready Definition ✍️
R-Tree Definition:
An R-Tree is a height-balanced tree used for indexing multi-dimensional spatial data. It stores
objects using minimum bounding rectangles and supports efficient range and spatial queries.
14. Short Example for Exams
Road segment → MBR = (2,4,8,6)
Building → MBR = (5,7,9,12)
Both objects are stored as rectangles in leaf nodes of the R-Tree.
If you want next, I can help you with:
R-Tree vs B+ Tree
R-Tree*
Interval Tree
KD-Tree vs R-Tree (exam answer)
Lab manual diagrams
MCQs & viva questions
Just tell me 😄