suma dwóch zbiorów w postaci drzewa BST

haneczka1830
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 28 maja 2010, o 19:05
Płeć: Kobieta
Lokalizacja: Polska

suma dwóch zbiorów w postaci drzewa BST

Post autor: haneczka1830 »

Dane są dwa zbiory A i B, reprezentowane jako drzewa binarnych poszukiwań. Zaproponuj algorytm, który znajduje sumę tych zbiorów w postaci drzewa BST.
Mile widziana kazda pomoc byle szybko bo czasu jest mało a nie wiem jak sie do tego zadania prostego z pozoru zabrac .POMOCY
Awatar użytkownika
paladin
Użytkownik
Użytkownik
Posty: 148
Rejestracja: 24 sty 2005, o 22:15
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 19 razy

suma dwóch zbiorów w postaci drzewa BST

Post autor: paladin »

Algorytm liniowy, za to z dużą dodatkową pamięcią:

1. Oba drzewa zamieniasz na posortowane tablice (czyli wypisujesz w porządku inorder)
2. Tablice scalasz w jedną posortowaną tablicę.
3. Z wynikowej tablicy tworzysz nowe drzewo.

Algorytm bez dodatkowej pamięci, za to z gorszą złożonością:

Z drzewa B usuwasz elementy po jednym, w dowolnej kolejności, i wstawiasz do A.
ODPOWIEDZ