14 июл. 2010 г.

Посадили дерево

В наших интервальных деревьях всю жизнь была ошибка. Интервалы перекрывались в следующем случае: есть два элемента A и B, имеющих одного родителя. A расположен левее B. Пусть B имеет два дочерних элемента C и D, примыкающих друг к другу, причем C расположен левее D и интервал C уже D. Тогда, при перемещении D в A, в процессе расширения интервалов вправо, интервал C будет перекрываться с A и B.

Комментариев нет:

Отправить комментарий