[Drzewa BST] Obliczanie sumy i różnicy

0

Szukałem już sporo w sieci i niestety znów mało znalazłem. Więc potrzebuję zaimplementować operacje dodawania i odejmowania dwóch drzew BST. Pierwszą operację już mam zaimplementowaną, znalazłem gdzieś w sieci info że trzeba przechodzić przez obydwa drzewa na przemian metodą in-order i dodawać wartości do drzewa wynikowego. Chciałem tylko się upewnić czy dobrze robię ?
Druga sprawa to odejmowanie, niestety nigdzie nie znalazłem żadych informacji na ten temat więc tak na chłopski rozum, pomyślałem że jeśli w drzewie a mamy klucze : 1, 2, 3, 4 a w drzewie b 1, 4, 6, 7 to wynikowe powinno po odjęciu zawierać : 2, 3, 6, 7 zgadza się ? No właśnie tylko jak to napisać. Zrobiłem metodę która miałaby to wykonywać i działać rekurencyjnie. Przechodzi przez drzewo a metodą in-order i dla każdej wartości w aktualnym węźle robi wyszukiwanie w drugim drzewie. Lecz jeśli drzewo a ma 4 węzły a drzewo b 15 to i tak wykona się tylko dla 4 węzłów. I na to pytanie szukam odpowiedzi, jak to zrobić ?

0

ciezko ocenic dokladna wydajnosc rozwiazania jakie proponujesz, bo ciezko zalozyc cos na temat samych obu drzew
jesli drzewo a jest wieksze niz b, moze wydajniej bedzie przejsc przez wszystkie elementy b i sprawdzac czy sa w a
poza tym nie napisales czy te drzewa sa w jakis sposob zbalansowane, wiec zakladam ze nie sa, a to znaczy ze kazda operacja ma zlozonosc pesymistyczna O(n) (liniowa)
poza tym ja przechodzilbym post-orderem, bo wtedy zaczynasz od lisci i pniesz sie wyzej, wiec jezeli zachodzi koniecznosc usuniecia danego wezla to usuniecie liscia wymaga mniejszej ilosci operacji
przede wszystkim napisz czy te drzewa sa w jakikolwiek sposob zbalansowane (np. AVL)

0

Dzięki za odpowiedź. Nie nie są zbalansowane. Ale z tym rozmiarem to chyba jest sens, bo wtedy wybiorę te w którym jest więcej elementów i dzięki temu wyszuka w całym.

Kolejne moje pytanie, zadanie dotyczy scalania dwóch drzew (też nie zbalansowanych). Mamy drzewa jak na rysunku :

http://img.nopaste.pl/upload/Clipboard01_4cd81a1b951e2.png

Dlaczego w drzewie wynikowym zgubiono liczbę 2 oraz 1? Przecież scalanie to sumowanie a nie odejmowanie.

0

To mi bardziej wygląda na różnicę symetryczną (odpowiednik XOR) niż na sumę.

Jeśli chodzi o dodawanie albo odejmowanie drzew to może potraktuj je jako drzewa rozchylane: http://en.wikipedia.org/wiki/Splay_tree i zastosuj odpowiednie metody z drzew rozchylanych.

Oczywiście zakładam, że mamy do czynienia z drzewami uporządkowanymi, jeśli nie to można zrobić np kopiec.

0

Masz rację, chodziło o XOR.
Jaki macie pomysł na wykonanie tego ? Mogę korzystać ze zwykłego drzewa BST i przechodzenia in-order, pre-order i reszty. Nie mam pomysłu na to żeby przejść przez wszystkie elementy w drzewie 1 i 2.

0

W drzewie rozchylanym po wyszukaniu węzła staje się on korzeniem. Wyszukiwanie wszystkich elementów w drzewie rozchylanym po kolei zajmuje czas liniowy ( http://en.wikipedia.org/wiki/Splay_tree#Performance_theorems - Scanning Theorem ). Myślę, że zrobienie efektywnego XORa wykorzystując te dwa fakty jest już proste.

1 użytkowników online, w tym zalogowanych: 0, gości: 1