Разрешены ли дубликаты ключей в определении бинарных деревьев поиска?

Question

Я пытаюсь найти определение бинарного дерева поиска, и я продолжаю находить разные определения везде.

Некоторые говорят, что для любого данного поддерева левый дочерний ключ меньше или равен корню.

Некоторые говорят, что для любого данного поддерева правый дочерний ключ больше или равен корню.

И в моей старой книге о структурах данных колледжа сказано, что «у каждого элемента есть ключ, а у двух элементов нет одинакового ключа».

Есть ли универсальное определение bst? Особенно в том, что делать с деревьями с несколькими экземплярами одного и того же ключа.

РЕДАКТИРОВАТЬ: Может быть, я неясно, определения, которые я вижу, являются

1) слева <= корень <справа </p>

2) слева

3) left

Answer 1

Многие алгоритмы будут указывать, что дубликаты исключаются. Например, примеры алгоритмов в книге MIT Algorithms обычно представляют примеры без дубликатов. Реализовать дубликаты довольно просто (либо в виде списка на узле, либо в одном конкретном направлении.)

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

Лучше всего использовать список в узле для хранения дубликатов, так как для вставки значения '=' в одну сторону узла требуется переписать дерево на этой стороне, чтобы разместить узел в качестве дочернего, или узел помещается как внучка, в какой-то момент ниже, что исключает некоторую эффективность поиска.

Вы должны помнить, что большинство примеров в классе упрощены, чтобы изобразить и представить концепцию. Они не стоят приседать во многих реальных ситуациях. Но утверждение «каждый элемент имеет ключ и ни один из двух элементов не имеет одинаковый ключ» не нарушается использованием списка в узле элемента.

Так что следуйте тому, что сказала ваша книга структур данных!

Edit:

Универсальное определение бинарного дерева поиска включает в себя сохранение и поиск ключа на основе обхода структуры данных в одном из двух направлений. В прагматическом смысле это означает, что если значение <>, вы пересекаете структуру данных в одном из двух «направлений». Таким образом, в этом смысле повторяющиеся значения не имеют никакого смысла вообще.

Это отличается от BSP или бинарного поискового раздела, но не сильно отличается. Алгоритм поиска имеет одно из двух направлений для «путешествия», или он выполняется (успешно или нет). Поэтому я прошу прощения, что мой первоначальный ответ не касался концепции «универсального определения», поскольку дубликаты действительно отличны тема (что вы имеете дело после успешного поиска, а не как часть двоичного поиска.)

Answer 2

Если ваше двоичное дерево поиска представляет собой красно-черное дерево или вы намереваетесь выполнять любые операции «поворота дерева», дублирующиеся узлы будут вызывать проблемы. Представьте, что ваше древовидное правило таково:

левый <корень <= правый </p>

Теперь представьте простое дерево, корень которого равен 5, левый дочерний элемент равен нулю, а правый дочерний элемент равен 5. Если вы выполняете вращение влево по корню, в результате получается 5 у левого дочернего элемента и 5 у корня с правильный ребенок, будучи ноль. Теперь что-то в левом дереве равно корню, но ваше правило выше предполагает левый <корень. </p>

Я потратил часы, пытаясь выяснить, почему мои красные / черные деревья иногда выходили из строя, проблема заключалась в том, что я описал выше. Надеюсь, кто-нибудь прочтет это и сэкономит на часах отладки в будущем!

Answer 3

Все три определения являются приемлемыми и правильными. Они определяют различные варианты BST.

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

Конечно, разрешение дубликатов добавляет сложности. Если вы используете определение «left <= root <right» и у вас есть дерево вроде: </p>

      3
    /   \
  2       4

затем добавление дубликата ключа «3» к этому дереву приведет к:

      3
    /   \
  2       4
    \
     3

Обратите внимание, что дубликаты не находятся в смежных уровнях.

Это большая проблема при разрешении дубликатов в представлении BST, как показано выше: дубликаты могут быть разделены любым количеством уровней, поэтому проверка на наличие дубликатов не так проста, как просто проверка непосредственных дочерних элементов узла.

Возможность избежать этой проблемы - не представлять дубликаты структурно (как отдельные узлы), а вместо этого использовать счетчик, который подсчитывает количество вхождений ключа. В предыдущем примере было бы дерево типа:

      3(1)
    /     \
  2(1)     4(1)

и после вставки дублирующего ключа «3» оно станет:

      3(2)
    /     \
  2(1)     4(1)

Это упрощает операции поиска, удаления и вставки за счет некоторых дополнительных байтов и операций счетчика.

Answer 4

В BST все значения, нисходящие с левой стороны узла, меньше (или равны, см. Позже) самого узла. Аналогично, все значения, нисходящие на правой стороне узла, больше (или равны) значению узла ^(a) .

Некоторые BST могут разрешить дублирование значений, следовательно, квалификаторы "или равно" выше.

Следующий пример может прояснить:

            |
      +--- 14 ---+
      |          |
+--- 13    +--- 22 ---+
|          |          |
1         16    +--- 29 ---+
                |          |
               28         29

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

Это можно сделать рекурсивно с помощью чего-то вроде:

def hasVal (node, srchval):
    if node == NULL:
         return false
    if node.val == srchval:
        return true
    if node.val > srchval:
        return hasVal (node.left, srchval)
    return hasVal (node.right, srchval)

и вызывая его с помощью:

foundIt = hasVal (rootNode, valToLookFor)

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

---

^(a) Вы могли бы на самом деле отсортировать их в обратном направлении, если пожелаете, при условии, что вы настроите поиск определенного ключа. BST нужно поддерживать только некоторый отсортированный порядок, независимо от того, возрастает он или нет.

Answer 5

В книге "Введение в алгоритмы", третье издание Кормена, Лизерсона, Ривеста и Стейна, двоичное дерево поиска (BST) явно определено как , допускающее дубликаты . Это можно увидеть на рисунке 12.1 и ниже (стр. 287):

"Ключи в бинарном дереве поиска всегда хранятся таким образом, чтобы удовлетворять свойству бинарного дерева поиска: пусть x будет узлом в бинарном дереве поиска. Если y является узлом в левое поддерево x, затем y:key <= x:key. Если y является узлом в правом поддереве x, то y:key >= x:key. "

Кроме того, дерево красно-черный затем определяется на странице 308 как:

«Красно-черное дерево - это двоичное дерево поиска с одним дополнительным битом памяти на узел: его цвет»

Поэтому красно-черные деревья, определенные в этой книге, поддерживают дубликаты.

Answer 6

Работая над реализацией красно-черного дерева, у меня возникали проблемы при проверке дерева с несколькими ключами, пока я не понял, что с вращением красно-черной вставки необходимо ослабить ограничение до

left <= root <= right

Поскольку ни одна из документов, на которые я смотрел, не позволяла дублировать ключи, и я не хотел переписывать методы ротации, чтобы учесть это, я просто решил изменить свои узлы, чтобы учесть несколько значений внутри узла, и нет дубликаты ключей в дереве.

Answer 7

Те три вещи, которые вы сказали, все верны.

• Ключи уникальны
• Слева находятся клавиши меньше этой
• Справа находятся ключи больше этой

Полагаю, вы могли бы перевернуть свое дерево и поместить меньшие клавиши справа, но на самом деле концепция «левый» и «правый» - это всего лишь визуальная концепция, которая помогает нам думать о структуре данных, которая в действительности иметь левую или правую, так что это не имеет значения.

Answer 8

Любое определение является действительным. Пока вы последовательны в своей реализации (всегда ставьте равные узлы справа, всегда ставьте их слева или никогда не разрешайте их), тогда все в порядке. Я думаю, что наиболее распространено, чтобы не допустить их, но это все еще BST, если они разрешены и размещены либо слева, либо справа.

Answer 9

Дубликаты ключей • Что произойдет, если имеется более одного элемента данных с тот же ключ? - Это представляет небольшую проблему в красно-черных деревьях. - Важно, чтобы узлы с одинаковым ключом распределялись по обе стороны других узлов с одинаковым ключом. - То есть, если ключи поступают в порядке 50, 50, 50, • вы хотите, чтобы вторые 50 шли справа от первого, а третий 50, чтобы идти налево от первого. • В противном случае дерево становится неуравновешенным. • Это может быть обработано какой-то рандомизацией процесс в алгоритме вставки. - Тем не менее, процесс поиска становится более сложным, если все предметы с одинаковым ключом должны быть найдены. • Проще запретить предметы с тем же ключом. - В этом обсуждении мы будем предполагать, что дубликаты не допускаются

Можно создать связанный список для каждого узла дерева, который содержит дубликаты ключей, и сохранить данные в списке.

Answer 10

Отношение упорядочения элементов <= представляет собой <a href="http://en.wikipedia.org/wiki/Total_order" rel="nofollow"> общий порядок , поэтому отношение должно быть рефлексивным, но обычно двоичное дерево поиска (также известное как BST) представляет собой дерево без дубликатов.

В противном случае, если есть дубликаты, вам нужно дважды или более запустить одну и ту же функцию удаления!