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 element o wartosci a na i-tej pozycji wiec nie mozna mowic o porzadku. Moglibysmy miec zrownowazone drzewo sortowane wedlug pozycji, ale jesli np. mamy n elementow i wstawimy element na pozycji 2 to musimy zwiekszyc wszystkie klucze o wartosci wiekszej od 2, wiec wydaje sie to slabe. Jakies pomysly? Moze nie jest to mozliwe 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 element o wartosci a na i-tej pozycji wiec nie mozna mowic o porzadku. Moglibysmy miec zrownowazone drzewo sortowane wedlug pozycji, ale jesli np. mamy n elementow i wstawimy element na pozycji 2 to musimy zwiekszyc wszystkie klucze o wartosci wiekszej od 2, wiec wydaje sie to slabe. Jakies pomysly? Moze nie jest to mozliwe w czasie log n?
#programowanie