2011-10-09 14 views
7

Mam BST, który ma zduplikowane wpisy. Próbuję znaleźć duplikaty wpisów. Teraz oczywiście mogę napisać głupi algorytm, który przemierza całe drzewo, co jest łatwe.Strategia wyszukiwania duplikatów w drzewie wyszukiwania binarnego

Jednak chcę napisać bardziej wydajną. Oto co zrobiłem/myślałem do tej pory:

Załóż następujące drzewo.

 10 
    / \ 
    5 15 
    /\ /\ 
    2 8 10 16 
     \ \ 
     8 12 

Jeśli chcę, aby znaleźć wszystkie 8'S, ja najpierw znaleźć 8 na lewym poddrzewie o 10. Aby znaleźć duplikat, jeśli nie ma prawa dziecka, czy to będzie lewicowo-najbardziej węzeł na prawym podtreście pierwszego rodzica, który jest większy niż ten węzeł (8)? A jeśli miałoby ono właściwe dziecko, to może znajdować się w lewym górnym węźle jego prawego poddrzewa lub w prawym górnym węźle w jego lewym poddrzewie?

Czy są to wszystkie przypadki, które można osiągnąć za pomocą wielu pętli i instrukcji if?

Jeśli nie, jakie jest lepsze podejście? Czy ktoś może pomóc?

Dzięki

EDIT: Właściwie Właśnie uświadomiłem sobie, że nie może być „lewo najbardziej węzeł” lub „prawy najbardziej węzeł”. To by znaleźć węzeł, który jest następną najwyższą wartością lub poprzednią najniższą wartością. Czy byłby to wcześniej jeden węzeł?

EDYCJA 2:

Poprawiono mój przykład BST. Wynika to z następującej metody wstawiania:

if (node == null) 
    return new NodeBST<Value>(name, value); 

if (node.key().compareTo(name) > 0) 
    node.setLeft(insert(node.left(), name, value));  
else 
    node.setRight(insert(node.right(), name, value)); 

Oznacza to, że duplikaty zostaną dodane na prawo od ich duplikatów .. prawda?

+0

Czy wiesz co wcześniej numer szukasz? – lynks

+0

Czy to nie jest celem BST? – Jasoneer

+1

To nie jest właściwe BST. Nie możesz mieć 8 na prawej gałęzi korzenia 10. –

Odpowiedz

2
  1. Znajdź element pasujący klucz przy użyciu zwykłych wyszukiwanie binarne drzewo. Jeśli nie zostanie znaleziony, przestań.
  2. Sprawdź pododdział LH. Jeśli jego klucz pasuje, ustaw bieżący węzeł i powtórz ten krok.
  3. Jesteś teraz na pierwszym elemencie drzewa za pomocą tego klucza. Teraz chodź z tego węzła drzewa, gdy klucze są równe, tj. Odwiedź ten węzeł, prawe pod-drzewo, rodzic, prawe pod-drzewo rodzica itp., Pozostawione jako ćwiczenie dla czytelnika.
+0

Wierzę, że w kroku 2 powinna to być pod-gałąź RH, ponieważ zgodnie z moją wstawką (jak pokazano w powyższej edycji 2), duplikaty są wstawiane do prawego dziecka węzła. Poprawny? – darksky

+0

@Nefef Przy pierwszym wejściu (2) możesz nie wiedzieć, że wszystkie duplikaty są tylko po prawej stronie. To zależy od tego, jak piszesz swój kod wyszukiwania. – EJP

+0

O tak, wiem o tym. Mówię tylko, że moja metoda wstawiania umieszcza duplikaty po prawej stronie węzła. (patrz powyższy kod + diagram). A więc nie uczyniłoby to kroku 2 jako: "Sprawdź pod-branżę RH" zamiast pod-gałęzi LH? – darksky

2

Drzewo, które pokazujesz, zakłada (cóż, przynajmniej zakładam ... ;-)), że mniej niż są po lewej, a większe - niż po prawej, mam rację?

więc istnieją dwie rzeczy, które należy rozważyć:

  1. Twoje drzewo jest złe! Drugie "8" z prawej strony "10" głowy nie może tam być, ponieważ jest mniej niż 10. Prawidłowe wstawienie i prawidłowe wyważenie, oba wpisywałyby się bardzo blisko, jeśli nie w prawo w "następnej" iteracji z "lewej 8".

  2. Definiując drzewo jako "mniejszy lub równy" po lewej stronie i "większy niż" po prawej stronie, uzyskasz pożądany wynik: wszystkie "8" zostaną powiązane lewo od siebie na prostym drzewie wstawiania.

+0

Tak tak, przepraszam za mój błąd. Zobacz edycję 2. Moje wstawienie łączy je na prawo od siebie. Więc kiedy znajdę duplikat, po prostu przejdź przez jego prawe dziecko/dzieci, aby zobaczyć wszystkie duplikaty? – darksky

+0

absolutnie. Ponadto, dla zwięzłości i wydajności, jeśli spodziewamy się dużej liczby duplikatów, rozszerzenie połączonej listy wszystkich obiektów o podobnej wartości od pierwszego, może być dobrym pomysłem. Jeśli naprawdę duże zestawy duplikatów, możesz uruchomić tablicę skrótów dla liścia zawierającego duplikaty ... wszystko w zależności od konkretnego problemu, który próbujesz rozwiązać! –

0

Algorytm rekurencyjny może rozwiązać to szybko. Nie musisz powtarzać całego drzewa, ponieważ możesz użyć struktury BST, aby wyłapać wartości, których potrzebujesz.

To, co narysowałeś, nie jest ściśle BST, może się mylę, ale uważam, że jest całkiem zepsuty - wszystkie liczby na lewym drzewie powinny być mniejsze niż 10 i odwrotnie.

+0

Przepraszam, wiem o tym. Popełniłem błąd, zobacz poprawioną edycję 2. Dzięki – darksky

0

Ta implementacja wykorzystuje metody rekurencyjnej i zwraca tablicę zduplikowanych wpisów

public class TreeNode<E> { 
    public int data; 
    public TreeNode left; 
    public TreeNode right; 
} 

public Integer[] findDuplicate(TreeNode tree) { 
    Map<Integer, Integer> entries = new HashMap<>(); 
    List<Integer> duplicates = new LinkedList<>(); 

    return (Integer[]) findDuplicate(tree, entries, duplicates); 
} 

private Integer[] findDuplicate(TreeNode tree, Map entries, List duplicates) { 
    if (tree == null) 
     return (Integer[]) duplicates.toArray(new Integer[] {}); 

    if (entries.containsKey(tree.data)) 
     duplicates.add(tree.data); 
    else 
     entries.put((int) tree.data, 1); 

    findDuplicate(tree.left, entries, duplicates); 
    findDuplicate(tree.right, entries, duplicates); 

    return (Integer[]) duplicates.toArray(new Integer[] {}); 
} 
Powiązane problemy