##
Segment Tree

Posted in Data structure by #care-crew

A Segment Tree is a data structure that enables you to find points in geometry.

It is dynamic and its simplest form is the binary tree. Each Node of the tree saves the top and bottom of the saved Interval, a list of Intervals(lines in this area) and its left and right brother.
A maximum of two nodes are used on each level. There are two colored exampled in the image. Inserting and deleting is done by going through each node. That is expensive. Finding is fast, it can be done in O(log N + t). t is the number of Intervals in which the line is saved.

Published at 2011-10-25, Updated at 2011-10-25

next: Hierarchical Data in a Relational Database
prev: Introduction to Data Structures