Najbardziej efektywny sposób testowania dwóch drzew binarnych dla równości

Question

Jak zaimplementować w Javie klasę węzła drzewa binarnego i klasę drzewa binarnego w celu obsługi najbardziej wydajnej (z perspektywy czasu wykonywania) metody równego sprawdzania (również musi być wdrożone):

boolean equal(Node<T> root1, Node<T> root2) {} 

lub

boolean equal(Tree t1, Tree t2) {} 

Najpierw stworzyłem klasę Node następująco:

public class Node<T> { 
     private Node<T> left; 
     private Node<T> right; 
     private T data; 

     // standard getters and setters 
    } 

i sposób dorównuje trwa 2 węzłów korzeniowych jako argumenty i działa na standardowym rekurencyjne Porównanie:

public boolean equals(Node<T> root1, Node<T> root2) { 
     boolean rootEqual = false; 
     boolean lEqual = false; 
     boolean rEqual = false;  

     if (root1 != null && root2 != null) { 
      rootEqual = root1.getData().equals(root2.getData()); 

      if (root1.getLeft()!=null && root2.getLeft() != null) { 
       // compare the left 
       lEqual = equals(root1.getLeft(), root2.getLeft()); 
      } 
      else if (root1.getLeft() == null && root2.getLeft() == null) { 
       lEqual = true; 
      } 
      if (root1.getRight() != null && root2.getRight() != null) { 
       // compare the right 
       rEqual = equals(root1.getRight(), root2.getRight()); 
      } 
      else if (root1.getRight() == null && root2.getRight() == null) { 
       rEqual = true; 
      } 

      return (rootEqual && lEqual && rEqual); 
     } 
     return false; 
    } 

Drugą próbę było realizować przy użyciu macierzy drzewa i indeksy do przechodzenia. Następnie porównanie można wykonać za pomocą operacji bitowych (AND) na dwóch tablicach - odczytaj fragment z 2 tablic i zamaskuj jeden za drugim, używając logicznego AND. Nie udało mi się uruchomić mojego kodu, więc nie zamieszczam go tutaj (byłbym wdzięczny za implementację drugiego pomysłu i ulepszeń).

Jakieś przemyślenia, jak wykonać test równości drzew binarnych najefektywniej?

EDIT

Pytanie zakłada równość strukturalny. (Nie semantyczna równość)

Jednak kod testujący równość semantyczną, np. "Czy powinniśmy uznać te dwa drzewa za równe, jeśli ich zawartość jest identyczna, nawet jeśli ich struktura nie jest?" Po prostu będzie to powtarzanie po drzewie w kolejności i powinno być proste.

Answer 1

Cóż, z jednej strony jesteś zawsze sprawdzanie gałęzi, nawet jeśli zauważysz, że korzenie są nierówne. Twój kod byłby prostszy (IMO) i bardziej wydajny, gdybyś właśnie zwrócił false, gdy tylko zauważysz nierówność.

Inną możliwością uproszczenia jest umożliwienie akceptacji wartości equals i porównanie dwóch wartości null jako równych. W ten sposób można uniknąć wszystkich kontroli nieważności w różnych oddziałach. To nie będzie bardziej wydajny, ale to będzie prostsze:

public boolean equals(Node<T> root1, Node<T> root2) { 
    // Shortcut for reference equality; also handles equals(null, null) 
    if (root1 == root2) { 
     return true; 
    } 
    if (root1 == null || root2 == null) { 
     return false; 
    } 
    return root1.getData().equals(root2.getData()) && 
      equals(root1.getLeft(), root2.getLeft()) && 
      equals(root1.getRight(), root2.getRight()); 
} 

Należy pamiętać, że obecnie będzie to powieść, jeśli root1.getData() powraca null. (To może ale nie musi być możliwe w sposobie, w jaki dodajesz węzły.)

EDYCJA: Jak wspomniano w komentarzach, możesz użyć kodów skrótów, aby bardzo szybko "odczekać" - ale to by dodało złożoności.

Albo trzeba dokonać drzew niezmienna (co jest zupełnie inna dyskusja) lub trzeba każdy węzeł wiedzieć o jego rodzica, tak, że gdy węzeł ulegnie zmianie (np dodając liść lub zmianę wartość) musi zaktualizować swój kod skrótu i poprosić rodzica o aktualizację również.

Answer 2

Dla każdego drzewa najbardziej efektywnym sposobem jego reprezentacji, aby można było łatwo sprawdzić równość jest lista nadrzędna - przytrzymaj tablicę, w której dla każdego wierzchołka pamiętasz indeks jego rodzica (w rzeczywistości trzymaj parę - indeks ojca i wartość danych). Wtedy po prostu powinieneś porównać dwa ciągłe bloki pamięci.

Będzie to działać tylko wtedy, gdy drzewo jest statyczne (tzn. Nie zmienia się w czasie). Również będzie uważał, że drzewa są równe, jeśli indeksy wierzchołków są takie same w dwóch drzewach.

Wierzę w powszechny przypadek, w którym dwie powyższe stwierdzenia nie są prawdziwe, twoja implementacja powinna być tak szybka, jak tylko możesz.

EDIT: w rzeczywistości implementacja można poprawić jeśli się przypomina w odpowiedzi Jon Skeet (przynamniej return false tak szybko, jak wiesz, drzewa nie są równe)

Answer 3

Z ciekawości, czy należy wziąć pod uwagę dwa drzewa są równe, jeśli ich zawartość jest identyczna, nawet jeśli ich struktura nie jest identyczna? Na przykład, czy są one równe?

B   C  C  A 
/\  /\ /\  \ 
A D  B D A D  B 
/ /  \   \ 
    C  A   B   C 
           \ 
            D 

Te drzewa mają tę samą zawartość w tej samej kolejności, ale ponieważ struktury są różne, testy nie będą równe.

Jeśli chcesz przetestować tę równość, osobiście po prostu zbudowałbym iterator dla drzewa, używając przejścia w kolejności i iteracji między drzewami, porównując je po elemencie.

Answer 4

Przede wszystkim robię kilka ogólnych założeń. Są to założenia, które są ważne dla większości klas oparty na drzewie zbiórki ale zawsze warto sprawdzić:

1. rozważyć dwa drzewa, aby być równe wtedy i tylko wtedy, gdy są one równe, zarówno pod względem struktury drzewa i pod względem wartości danych w każdym węźle (zdefiniowane przez data.equals (...))
2. wartości null danych są dozwolone w węzłach drzewa (może to być spowodowane tym, że jawnie zezwolisz na wartość null lub ponieważ struktura danych przechowuje tylko wartości nie -null wartości w węzłach liści)
3. Nie ma żadnych szczególnych faktów, które znasz na temat dystrybucji wartości danych, które możesz wykorzystać (na przykład, jeśli wiesz, że jedyne możliwe wartości danych były zerowe lub ciąg "foo", wtedy nie musisz porównywać dwóch niepustych wartości String)
4. Drzewa będzie zazwyczaj umiarkowany i odpowiednio zrównoważony. W szczególności zapewnia to, że drzewa nigdy nie będą tak głębokie, że istnieje ryzyko pojawienia się wyjątków StackOverflow spowodowanych głęboką rekurencją.

Przyjmując te założenia są prawidłowe, to chciałbym zaproponować podejście jest:

• Do odniesienia korzeń najpierw sprawdzić równość. to szybko eliminuje przypadek dwóch wartości zerowych lub tego samego drzewa, które są przekazywane w celu porównania z samym sobą. Oba są bardzo częstymi przypadkami, a sprawdzanie równości referencyjnej jest wyjątkowo tanie.
• Sprawdź następne wartości zerowe. Wartość niezerowa nie jest oczywiście równa wartości zerowej, co umożliwia Ci wykupienie wczesnej plus ustanawia ona niezerową gwarancję na późniejszy kod!Bardzo inteligentny kompilator mógłby teoretycznie skorzystać z tej gwarancji, aby zoptymalizować kontrolę pustych wyników poza puntem (nie ma pewności, czy obecnie maszyna JVM to robi)
• Sprawdź równoważność odniesienia danych i wartości puste następnej. Pozwala to uniknąć zejścia w dół gałęzi drzew, które można by zrobić nawet w przypadku nierównych danych, jeśli najpierw zejdzie się po gałęziach drzew.
• Sprawdź data.equals() następny. Znowu chcesz sprawdzić równość danych przed gałęziami drzewa. Robisz to po sprawdzeniu wartości null, ponieważ data.equals() jest potencjalnie droższa i chcesz zagwarantować, że nie uzyskasz NullPointerException
• Sprawdź równość oddziałów rekursywnie jako ostatni krok. Nie ma znaczenia, czy wykonasz pierwszy lub lewy numer , chyba że istnieje większe prawdopodobieństwo, że jedna strona będzie nierówna, w takim przypadku powinieneś najpierw sprawdzić tę stronę. Może tak być, jeśli np. większość zmian została dołączona do prawej gałęzi drzewa ....
• Dokonaj porównania metodą statyczną. Dzieje się tak dlatego, że chcesz używać go rekurencyjnie w sposób, który będzie akceptował wartości null jako jeden z dwóch parametrów (dlatego nie jest odpowiedni dla metody instancji, ponieważ this nie może być pusty). Ponadto JVM jest bardzo dobra w optymalizowaniu metod statycznych.

Moja implementacja byłaby zatem coś takiego:

public static boolean treeEquals(Node a, Node b) { 
    // check for reference equality and nulls 
    if (a == b) return true; // note this picks up case of two nulls 
    if (a == null) return false; 
    if (b == null) return false; 

    // check for data inequality 
    if (a.data != b.data) { 
     if ((a.data == null) || (b.data == null)) return false; 
     if (!(a.data.equals(b.data))) return false; 
    } 

    // recursively check branches 
    if (!treeEquals(a.left, b.left)) return false; 
    if (!treeEquals(a.right, b.right)) return false; 

    // we've eliminated all possibilities for non-equality, so trees must be equal 
    return true; 
} 

Answer 5

kod podany powyżej wróci prawda na dwie nierówne drzew z tymi samymi wartościami korzeniowych. Nie sądzę, że tego chcesz. Nie powinno być:

jeśli (! A == b) zwróci false;

W ten sposób metoda wykona resztę czeków.

(Nie można zalogować się tutaj z jakiegoś powodu.)