Допускаются ли повторяющиеся ключи в определении деревьев двоичного поиска?

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

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

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

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

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

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

1) left <= root <right

2) left <root <= right

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

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

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

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

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

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

Редактировать:

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

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

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

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

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

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

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

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

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

      3
    /   \
  2       4

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

      3
    /   \
  2       4
    \
     3

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

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

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

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

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

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

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

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

Некоторые BST могут разрешить дублирование значений, отсюда и квалификаторы «или равно» выше. Следующий пример может прояснить:

     14
    /  \
  13    22
 /     /  \
1    16    29
          /  \
        28    29

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

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

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

^(b) Интересно, что если ваш ключ сортировки использует все значение, хранящееся в узле (так что узлы, содержащие один и тот же ключ, не имеют другой дополнительной информации для их различения), может быть повышение производительности от добавления счетчика к каждому узлу, а не позволяя дублировать узлы.

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

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

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

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

Например, следующие два дерева (не считая слева и считая справа) будут эквивалентны (в дереве подсчета i.cозначает cкопии элемента i):

     __14__                    ___22.2___
    /      \                  /          \
  14        22             7.1            29.1
 /  \      /  \           /   \          /    \
1    14  22    29      1.1     14.3  28.1      30.1
 \            /  \
  7         28    30

Удаление листового узла 22из левого дерева повлечет за собой перебалансировку (поскольку теперь у него разница в высоте 22-29-28-30равна двум) результирующего поддерева, такого как показано ниже (это один из вариантов, есть и другие, которые также удовлетворяют требованию «разность высоты должна быть равна нулю или единице. "правило):

\                      \
 22                     29
   \                   /  \
    29      -->      28    30
   /  \             /
 28    30         22

Выполнение той же операции в правом дереве представляет собой простую модификацию корневого узла с 22.2на 22.1(без необходимости повторной балансировки).

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

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

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

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

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

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

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

left <= root <= right

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

Я просто хочу добавить дополнительную информацию к тому, что ответил @Robert Paulson.

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

1. left <= cur <right

2. слева <cur <= справа

3. left <= cur <= right

4. left <cur <right && cur содержат узлы-братья с тем же ключом.

5. left <cur <right, так что не существует повторяющихся ключей.

1 и 2. отлично работает, если дерево не имеет функций, связанных с вращением, для предотвращения перекоса.
Но эта форма не работает с AVL-деревом или красно-черным деревом , потому что вращение нарушит принципал.
И даже если search () находит узел с ключом, он должен пройти вниз до конечного узла для узлов с повторяющимся ключом.
Создание временной сложности для search = theta (logN)

3. будет хорошо работать с любой формой BST с функциями, связанными с вращением.
Но поиск займет O (n) , разрушив цель использования BST.
Скажем, у нас есть дерево, показанное ниже, с 3) принципалом.

         12
       /    \
     10     20
    /  \    /
   9   11  12 
      /      \
    10       12

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

4. мой личный фаворит. Скажем, брат означает узел с тем же ключом.
Мы можем изменить верхнее дерево на нижнее.

         12 - 12 - 12
       /    \
10 - 10     20
    /  \
   9   11

Теперь любой поиск займет O (logN), потому что нам не нужно перемещаться по дочерним элементам для повторяющегося ключа.
И этот принцип также хорошо работает с деревом AVL или RB .

Все эти три вещи, которые вы сказали, правда.

• Ключи уникальные
• Слева ключи меньше этого
• Справа ключи больше, чем этот

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

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

2.) left <root <= right

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

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

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

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

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

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

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