2020-04-06
Podczas projektowania algorytmów często przeprowadza się wzbogacanie znanej struktury danych w celu przystosowania jej do wykonania dodatkowych zadań.
Wybieramy znaną strukturą danych.
Ustalamy jaką dodatkową informację chcemy przechowywać w naszej strukturze.
Sprawdzamy, czy możemy aktualizować efektywnie tę dodatkową informację podczas wykonywania operacji modyfikujących naszą podstawową strukturę danych.
Słowo „efektywnie” w powyższym zdaniu należy rozumieć jako „nie zwiększając asymptotycznej złożoności obliczeniowej operacji”, ale może się zdarzyć, że jest to niemożliwe. Wówczas dopuszczamy zwiększenie złożoności obliczeniowej operacji na strukturze dopóki użycie danej struktury „ma sens, jest uzasadnione innymi aspektami”.
Zaprojektowanie nowych operacji, które, używając dodatkowych informacji przechowywanych w strukturze danych, pozwolą nam na osiągnięcie zakładanego celu.
Dynamiczne statystyki pozycyjne – mając dynamiczny zbiór danych, chcemy szybko wyznaczać -tą statystyką pozycyjną oraz zwracać statystykę pozycyjną zadanego elementu.
Rozszerzymy tutaj strukturę RB-Tree.
Więcej na temat wzbogacania struktur danych: