Wstawianie między klucze w drzewie AVL.

Witam, mam problem. Tworzę drzewo AVL, które reprezentuje indeksowany ciąg liczb. Na tym drzewie wykonuję operacje dodawania i usuwania węzłów. Tu pojawia się problem...

Gdy mam indeksy 1 2 3 4 5 i chcę wstawić coś pomiędzy elementy 2 i 3, jak rozsunąć resztę aby nie popsuć drzewa i koszt był w miarę optymalny? Tak samo przy usuwaniu, gdybym przy tym samym ciągu chciał usunąć 3 to jak zmienić indeksy 4 i 5 na 3 i 4, bez psucia drzewa?

Pozdrawiam i dziękuję za podpowiedzi.

Jeszcze rozwiązaniem byłby szukanie i wstawianie, któregoś elementu z kolei. Wtedy indeksowanie nie byłoby potrzebne. Tylko nie mam pojęcia, jak to rozwiązać.

http://bit.ly/1yUW7Mv

Nie widzę żadnej pomocy w tym co napisałeś. Może czegoś nie widzę. Wiem jak działa drzewo AVL. I szukałem już odpowiedzi w google.
Proszę o jakąś wskazówkę.

Te fragmenty:

rykukuku napisał(a):

... jak rozsunąć resztę aby nie popsuć drzewa ...
oraz

rykukuku napisał(a):

Wiem jak działa drzewo AVL.
przeczą jedno drugiemu.
To tak jakby ktoś pytał jak zrobić aby iloczyn dwóch liczb ujemnych był dodatnim a przy tym twierdził że wie co to jest mnożenie.

A nie możesz po prostu napisać o co chodzi? Sam zaimplementowałem drzewo AVL, które działa, a nie zrobiłbym tego bez jego znajomości, prawda? Nie wiem jak to zrobić, nie psując drzewa.

Zaimplementowałeś drzewo które działa ale bez wstawiania elementów? Co za bzdura!

Wstawia elementy. Drzewo działa w 100%. Jednak problem polega na zaimplementowaniu indeksowanej listy na tym drzewie. Przy usunięciu elementu, chciałbym aby pozostałe indeksy się "zsunęły", a przy dodaniu "rozciągnęły". Nie wiem jak zrobić to optymalnie.

Dobra pokaż kod który to robi (wstawia pomiędzy 2 a 3) oraz wyświetla to co ci wychodzi oraz napisz co chciałbyś aby się wyświetliło.

Mam drzewo, które reprezentuje listę indeksowaną (każdy z węzłów ma swój index i indexy to po kolei liczby całkowite zaczynając od 0). Drzewo się super buduje, mogę w nim wyszukiwać elementy itd. Problem zaczyna się, gdy chcę dokonać operacji usunięcia, bądź dodania czegoś między indeksami.
Np. mam indeksy o węzłach 1 2 3 4 5, usuwam trójkę i indeksowanie traci przez to ciągłość bo jest 1 2 4 5. Analogicznie jest ze wstawianiem, jest ok jak wstawiam indeksy większe od tych do już są, jednak gdy chcę wstawić coś pomiędzy 3 i 4 to trzeba tak przebudować drzewo, aby 4 zamienił się w 5, 5 w 6 i żeby znalazło się miejsce na nowy element.

I tu jest mój problem, jak to optymalnie robić.

Mi to wygląda na to że mylisz klucz z indeksem.
Klucz na stałe jest przypisany do węzła drzewa, drzewo cały czas ma te klucze uporządkowane rosnąco lub malejąco (przeglądając w kolejności INORDER)
Natomiast indeks to numer tego węzła w kolejności INORDER.
Nie możesz ten indeks trzymać bezpośrednio w węźle (to znaczy możesz ale koszt aktualizacji jest zbyt wysoki).
W węźle trzymaj ilość liści - czyli sumaryczna ilość podpiętych NULL'ów
Aktualizacja tego wynosi log(N) i robi się w trakcie wstawiania/usuwania
Natomiast znalezienie wg indeksu (o ile masz wpisaną przy węźle ilość liści) jest bardzo prosta.

Tak masz rację, myliłem to. Dzięki wielkie, już wiem jak to zrobić. Następnym razem postaram się być bardziej konkretny ;)

Ok, mam już ilość liści przy każdym węźle. Teraz nie mogę dojść jak znaleźć ten element według indexu.

1. jeżeli nr<=0 lub nr>=node.leafs -> nie ma takiego
2. jeżeli nr<node.left.leafs to node=node.left
3. jeżeli nr=node.left.leafs to node -> ten właśnie indeks
4. jeżeli nr>node.left.leafs to node=node.right oraz nr=nr-node.left.leafs

Czyli ja mam przechowywać liczbę liści pod danym węzłem? Czy liczbę wszystkich węzłów pod tym węzłem?

liczbę NULL'i pod węzłem.
Z tym że sam NULL liczysz jako jeden.

A jak można rozwiązać to, że szukany element jest liściem? Trzeba zmieniać implementację drzewa, żeby na końcu były jakby puste węzły?

nie, napisz statyczną funkcję size_t getLeftLeaf(node*) { return node?node->leafs:1; }

Wtedy mi nie znajdzie zera, prawda?