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

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

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

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

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

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

EDIT: Возможно, я был неясен, определения, которые я вижу, это

1) left <= корень < вправо

2) слева < root <= right

3) слева < root < правильно, чтобы не существовало дублирующих ключей.

Ответ 1

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

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

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

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

Итак, переходите к тому, что говорится в ваших структурах данных!

Edit:

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

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

Ответ 2

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

left < root <= right

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

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

Ответ 3

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

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

В следующем примере может быть пояснено:

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

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

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

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 необходимо поддерживать только некоторый порядок сортировки, независимо от того, что восходящий или нисходящий не имеет значения.

Ответ 4

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

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

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

      3
    /   \
  2       4

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

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

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

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

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

и после вставки дубликата ключа "3" он станет следующим:

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

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

Ответ 5

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

left <= root <= right

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

Ответ 6

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

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

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

"Красно-черное дерево - это двоичное дерево поиска с одним дополнительным битом хранилища на node: его цвет"

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

Ответ 7

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

Ответ 8

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

Ключи уникальны.
Слева клавиши меньше этого
Справа находятся клавиши, превышающие этот

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

Ответ 9

1.) left <= корень < вправо

2.) left < root <= right

3.) left < root < правильно, чтобы не существовало дублирующих ключей.

Мне, возможно, придется пойти и выкопать книги по алгоритму, но с моей головы (3) есть каноническая форма.

(1) или (2) появляются только тогда, когда вы начинаете разрешать дубликаты узлов, и вы помещаете повторяющиеся узлы в самом дереве (а не в node, содержащий список).

Ответ 10

Отношение упорядочения элементов <= представляет собой общий порядок, поэтому отношение должно быть рефлексивным, но обычно двоичное дерево поиска (aka BST) дерево без дубликатов.

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

Ответ 11

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

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