Является ли поиск по интервалам clrs третьего издания псевдокодом pg 351 наиболее оптимальным? - PullRequest
Новая
       35

Является ли поиск по интервалам clrs третьего издания псевдокодом pg 351 наиболее оптимальным?

0 голосов
/ 29 апреля 2019

Clrs представил псевдокод для поиска интервала, который должен найти интервал, который перекрывает интервал i в дереве T. Но я обнаружил, что с некоторыми из моих собственных модификаций он может работать быстрее с постоянным коэффициентом.

Псевдокод clrs выглядит как 

INTERVAL-SEARCH(T, i)
    x = T.root
    while x != T.nil and i does not overlap x.int
        if x.left != T.nil and x.left.max ≥ i.low
            x = x.left
        else x = x.right
    return x

Однако я понимаю, что если вы измените его на 

INTERVAL-SEARCH(T, i)
    x = T.root
    while x != T.nil and i does not overlap x.int
        if x.left != T.nil and x.left.max ≥ i.low
            x = x.left
        else if i.high > x.int.low and x.right.max ≥ i.low
            x = x.right
        else x = T.nil
    return x

С тех пор, как код идет вправо, его когда левыйбольше не имеет значения, потому что это либо T.nil, либо x.left.max x.high i.high.

Если это первое, имеет смысл идти вправо, поскольку правая сторона все еще имеет возможность найти интервал с x.high ≥ i.low, но если это последнее, то ни один интервал справа не изменитсятот факт, что x.low> i.high.Аналогично, если x.right.max Я понимаю, что это не меняет асимптотическое время выполнения, но мне было любопытно, потому что я не понимаю, почему в книге просто не указан самый оптимальный псевдокод, так как он кажется более оптимальным в этом смысле.И если код переходит к x.right очень рано, он потенциально может работать намного быстрее.

...