PROGRAMOWANIE I ALGORYTMY

Drzewo BST z historią (zbiory z historią)


Gdy potrzebujemy zapamiętać poprzednie wersje drzewa BST możemy tworzyć kolejne jego kopie. Niestety takie rozwiązanie posiada bardzo poważną wadę. Złożoność czasowa i pamięciowa programu znacznie się pogarsza. Rozwiązaniem tego problemu może być tworzenie kopii tylko tej gałęzi, po której aktualnie się poruszamy dodając klucz. Rozpatrzmy następujący ciąg liczb:

$$4,\ 7,\ 3,\ 8\ 1,\ 6,\ 10$$

Drzewo BST będzie wyglądać jak na rysunku poniżej:

drzewo bst

Teraz chcemy dodać następny element jednocześnie pamiętając poprzednią wersję drzewa. Tworzymy kopię korzenia (na przykład dodając ją jako kolejny element wektora), następnie tworzymy tylko te elementy drzewa, przez które będziemy przechodzić, a ci synowie, którzy nie będą odwiedzeni pozostają pozostają bez zmian, przypisując do nich odpowiedni wskaźnik ojca. 

Załóżmy, że chcemy dodać do naszego drzewa liczbę 5. Poniższy rysunek przedstawia zaistniałą sytuację.

drzewo bst z historią