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?
Czy wiesz co wcześniej numer szukasz? – lynks
Czy to nie jest celem BST? – Jasoneer
To nie jest właściwe BST. Nie możesz mieć 8 na prawej gałęzi korzenia 10. –