Повторяющиеся записи в двоичном дереве поиска

У меня очень простой вопрос относительно BST. Я видел несколько определений BST, касающихся повторяющихся записей. Некоторые определяют BST как не допускающие дублирования записей, другие определяют, что левый дочерний элемент узла ‹= значению узла, а правый дочерний элемент больше значения узла, а некоторые определения противоположны этому (левый дочерний элемент ‹, чем узел, правый ребенок >=).

Итак, мой вопрос: каково официальное определение (если оно существует) для BST в отношении дублирующихся записей? Например, как будет выглядеть BST после вставки значений: 3, 5, 10, 8, 5, 10?

Заранее спасибо за уточнение определения и ответ на мой вопрос!


python java c# binary-search-tree
person Tareq    schedule 02.01.2012    source источник
comment
официальное определение? Что бы вы назвали официальным? Какой уровень власти здесь требуется?   -  person S.Lott    schedule 02.01.2012
comment
Я предполагаю, что это не столько уровень полномочий, сколько то, что является наиболее общепринятым определением BST в отношении повторяющихся записей.   -  person Tareq    schedule 02.01.2012

Ответы (2)


arrow_upward
6
arrow_downward

Одной из известных книг в области алгоритмов и структуры данных является книга CLRS, также известная как библия структур данных и алгоритмов:

введите здесь описание изображения

Согласно определению этой книги, повторяющиеся записи размещаются в правом дереве узла, содержащего тот же ключ. В качестве примера взгляните на алгоритм вставки BST, взятый из этой книги:

введите здесь описание изображения

person Gupta    schedule 02.01.2012
comment
Вау очень интересный и кроткий ответ. - person Saeed Amiri; 16.02.2012

arrow_upward
3
arrow_downward

важным моментом является то, что отсутствие дубликатов в дереве обеспечивает быстрое время поиска. Если у вас есть дубликаты на одной стороне узла, ваше время поиска будет страдать, потому что вам нужно просмотреть все дубликаты, прежде чем вы сможете продолжить.

http://en.wikipedia.org/wiki/Binary_search_tree

person light_303    schedule 02.01.2012
comment
Внешняя ссылка не очень полезна в этом контексте. - person Niklas B.; 02.01.2012
comment
В деревьях, где левый дочерний элемент равен ‹ узлу, а правый дочерний элемент равен ›= узлу, это не имеет большого значения. Когда первый узел найден, можно просто проверить правильные дочерние элементы, чтобы получить все дубликаты. - person Nikolay Polivanov; 02.01.2012
comment
Конечно, каждый узел может просто содержать количество появлений элемента. - person C. Reed; 02.01.2012