Бинарное дерево поиска может иметь дублированные узлы. В операции вставки мы продолжаем сканировать правое поддерево, если наш новый элемент совпадает с данными в текущем узле. В результате в правом поддереве совпавшего узла возникают дублированные узлы.
Например, следующее дерево генерируется из списка 50 70 25 90 30 55 25 15 25.
Многие приложения не допускают дублирования узлов, а используют в данных поле счетчика экземпляров элемента. Это – принцип конкорданса, когда отслеживаются номера строк, в которых встречается некоторое слово. Вместо того чтобы несколько раз размещать слово на дереве, мы обрабатываем повторные случаи употребления этого слова путем помещения номеров строк в список.
