A) Jeśli jest mniejszy niż y to idziemy cały czas w lewo, i sprawdzamy czy natkniemy się na wartość mniejszą niż x
Nie idziemy cały czas w lewo. Naszym zadaniem jest znalezienie największej wartości mniejszej niż x. Wierzchołek, który taką wartość przechowuje wcale nie musi być lewym dzieckiem, tym bardziej "skrajnym" lewym dzieckiem.
Aby rozwiązać to zadanie wystarczy policzyć
\(\displaystyle{ S_{(x,y)} = S_{(-\inf,y>} - S_{(-\inf,x>}}\)
Jeżeli przechowuje się sumy częściowe lewego poddrzewa należy znaleźć wierzchołek, którego wartość jest największą wartością mniejszą lub równą x i zapisać jego sumę częściową jako
\(\displaystyle{ S_{(-\inf),x>}}\) oraz wierzchołek, którego wartość jest największą wartością mniejszą lub równą y i zapisać jego sumę częściową jako
\(\displaystyle{ S_{(-\inf),y>}}\). Można to zrobić bardzo łatwo wykorzystując zmodyfikowany algorytm wyszukiwania.
Algorytm wyznaczania
\(\displaystyle{ S_{(-\inf,x>}}\)
Kod: Zaznacz cały
Nazwa: smin(T,x)
Dodatkowe oznaczenia: L(T) - lewe dziecko; P(T) prawe dziecko, V(T) wartość T, S(T) suma lewego poddrzewa T
Notatka: suma prawego poddrzewa jest obliczana tylko w celu utworzenia drzewa i nie jest wykorzystywana w algorytmie
wejście: wierzchołek R, wartość x
wyjście: suma wartości wierzchołków mniejszych od x w drzewie o korzeniu R
1. Jeżeli V(R) > x:
a. jeżeli L(R):
zwróć smin(L(R),x)
w przeciwnym wypadku
zwróć 0
w przeciwnym wypadku:
a. jeżeli P(R)
zwróć smin(P(R),x) + S(R) + V(R)
w przeciwnym wypadku
zwróć S(R) + V(R)
Można usprawnić przedstawiony algorytm i wykorzystać podobną ideę do obliczenia
\(\displaystyle{ S_{<y,\inf)}}\) oraz zastosować wzór
\(\displaystyle{ S_{(x,y)} = S - S_{<y,\inf)} - S_{(-\inf,x>}}\)