Algorytmy i Struktury Danych

4b. Drzewa BST i czerwono-czarne.

1. (1p.) Napisz nierekurencyjną wersję procedury OS-Select.

2. (1p.) Napisz procedurę OS-Key-Rank(T, s), która dla danego drzewa sta-

tystyk pozycyjnych T oraz klucza k, wyznacza rangę k w zbiorze repre-
zentowanym przez T . (Można założyć, że klucze w T są parami różne.)

3. (1p.) Jak wyznaczyć i-ty następnik zadanego węzła x w drzewie statystyk

pozycyjnych w czasie O(lg n), gdzie n oznacza rozmiar drzewa?

4. (2p.) Jak użyć drzewa statystyk pozycyjnych do wyznaczenia liczby inwer-

sji w tablicy A o rozmiarze n w czasie O(n lg n)? (Para (i, j) jest inwersją
jeśli i < j oraz A[i] > A[j].)

5. (2p.) Opisz jak zaimplementować operacje: Minimum, Maximum, Successor

oraz Predecessor, aby na odpowiednio wzbogaconym drzewie statystyk
pozycyjnych ich czas działania wynosił O(1). Asymptotyczna złożoność
pozostałych operacji nie powinna ulec zmianie.

6. (1p.) Czy czarną wysokość węzła w drzewie czerwono-czarnym można

utrzymywać jako pole każdego węzła, nie zwiększając złożoności żadnej z
operacji?

7. (1p.) Czy głebokość węzła w drzewie czerwono-czarnym można utrzymy-

wać jako pole każdego węzła, nie zwiększając złożoności żadnej z operacji?

8. (1p.) Niech ⊗ będzie operatorem łącznym, natomiast a dodatkowym po-

lem w każdym węźle drzewa czerwono-czarnego. Załóżmy, że w każym
węźle x znajduje się dodatkowe pole f takie, że f [x] = a[x

1

] ⊗ a[x

2

] ⊗ . . . ⊗

a

[x

m

], gdzie x

1

, . . . , x

m

są węzłami poddrzewa o korzeniu x w kolejności

inorder. Pokaż, że pola f można aktualizować w czasie O(1) po wykonaniu
rotacji. Wykorzystaj ten fakt aby pokazać, że pola size po wykonaniu jed-
nej rotacji w drzewie statystyk pozycyjnych można aktualizować w czasie
O

(1).

9. (2p.) Napisz procedurę RB-Enumerate(x, a, b), która wypisuje wszystkie

klucze z przedziału [a, b] w drzewie czerwono-czarnym o korzeniu x w czasie
Θ(m + lg n), gdzie m jest liczbą wypisanych kluczy a n liczbą węzłów w
drzewie.

10. (1p.) Napisz Left-Rotate dla drzewa przedziałowego, poprawiającą pola

max

w czasie O(1).

11. (1p.) Zmień Interval-Search, aby działała poprawnie dla przedziałów

otwartych.

1

12. (1p.) Podaj algorytm, który dla danego przedziału zwraca zachodzący na

niego przedział o najmniejszym lewym końcu lub N IL, jeśli taki przedział
nie istnieje.

13. (2p.) Opisz, jak dla danego drzewa przedziałowego T oraz przedziału i

wyznaczyć w czasie O(min(n, k lg n)) wszystkie przedziały zachodzące na
i

gdzie k jest liczbą takich przedziałów. (Podaj rozwiązanie, które nie

modyfikuje drzewa.)

2