Wiele algorytmów określa, że duplikaty są wykluczone. Na przykład przykładowe algorytmy w książce MIT Algorithms zwykle przedstawiają przykłady bez duplikatów. Implementacja duplikatów jest dość trywialna (jako lista w węźle lub w jednym określonym kierunku).
Większość (jakie widziałem) określa lewe dzieci jako <= a prawe dzieci jako>. Praktycznie rzecz biorąc, BST, który pozwala prawemu lub lewemu potomkowi być równym węzłowi głównemu, będzie wymagał dodatkowych kroków obliczeniowych, aby zakończyć wyszukiwanie, w którym dozwolone są zduplikowane węzły.
Najlepiej jest użyć listy w węźle do przechowywania duplikatów, ponieważ wstawienie wartości '=' z jednej strony węzła wymaga przepisania drzewa po tej stronie, aby umieścić węzeł jako dziecko, lub węzeł jest umieszczony jako wielki -dziecko, w pewnym punkcie poniżej, co eliminuje część wydajności wyszukiwania.
Musisz pamiętać, że większość przykładów w klasie jest uproszczona, aby przedstawić i przedstawić koncepcję. Nie są warte przysiadu w wielu sytuacjach w świecie rzeczywistym. Jednak stwierdzenie „każdy element ma klucz i żadne dwa elementy nie mają tego samego klucza” nie jest naruszane przez użycie listy w węźle elementu.
Więc idź z tym, co mówi twoja książka o strukturach danych!
Edytować:
Uniwersalna definicja binarnego drzewa wyszukiwania obejmuje przechowywanie i wyszukiwanie klucza na podstawie przechodzenia przez strukturę danych w jednym z dwóch kierunków. W sensie pragmatycznym oznacza to, że jeśli wartość wynosi <>, przechodzisz przez strukturę danych w jednym z dwóch „kierunków”. W tym sensie zduplikowane wartości w ogóle nie mają sensu.
Różni się to od BSP lub partycji wyszukiwania binarnego, ale nie jest tak różne. Algorytm wyszukiwania ma jeden z dwóch kierunków dla „podróży” lub jest wykonywany (pomyślnie lub nie). Przepraszam więc, że moja pierwotna odpowiedź nie odnosiła się do pojęcia „uniwersalnej definicji”, ponieważ duplikaty są tak naprawdę odrębnymi temat (coś, czym zajmujesz się po udanym wyszukiwaniu, a nie jako część wyszukiwania binarnego).