Сегментно дърво

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

В информатиката сегментното дърво е структура от данни за съхранение на интервали или сегменти. То позволява да се разбере кои от съхранените интервали съдържат дадена точка. По принцип сегментното дърво е статична структура, чието съдържание не може да се променя след като се построи. Друга подобна структура от данни е интервалното дърво.

Сегментното дърво на множеството I от n интервала използва O(n log n) памет и може да се построи за O(n log n) време. То позволява да се намерят всички интервали, които съдържат дадена точка за време O(log n + k), като k е броят на откритите интервали или сегменти.

Сегментното дърво се прилага в алгоритмичната геометрия и в геоинформационните системи.

Криейтив Комънс - Признание - Споделяне на споделеното Лиценз за свободна документация на ГНУ Тази страница частично или изцяло представлява превод на страницата „Segment tree“ в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс - Признание - Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година — от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.