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
suma dwóch zbiorów w postaci drzewa BST
-
- Użytkownik
- Posty: 3
- Rejestracja: 28 maja 2010, o 19:05
- Płeć: Kobieta
- Lokalizacja: Polska
- paladin
- 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
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.
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.