Hej mirki, macie moze pomysl na dynamiczna strukture ktora wykona ponizsze operacje w czasie log n?
Wstaw(a, i) - wstaw element a jako i-ty
Usun(i) - usun i-ty element ciagu.
Podaj(i) - podaj i-ty element ciagu.
Ogolnie wiadomo, jak mamy podac k-ty element ale co do wielkosci to latwo jest to zrealizowac na drzewach Splay/AVL. Wystarczy pamietac ile elementow jest w naszym lewym poddrzewie i w naszym prawym poddrzewie. Tutaj mamy powiedziane
Wstaw(a, i) - wstaw element a jako i-ty
Usun(i) - usun i-ty element ciagu.
Podaj(i) - podaj i-ty element ciagu.
Ogolnie wiadomo, jak mamy podac k-ty element ale co do wielkosci to latwo jest to zrealizowac na drzewach Splay/AVL. Wystarczy pamietac ile elementow jest w naszym lewym poddrzewie i w naszym prawym poddrzewie. Tutaj mamy powiedziane
#programowanie