Делают дубликаты ключа, позволенные в определении деревьев двоичного поиска?
NullPointerException s - исключения, возникающие при попытке использовать ссылку, которая указывает на отсутствие местоположения в памяти (null), как если бы она ссылалась на объект. Вызов метода по нулевой ссылке или попытка получить доступ к полю нулевой ссылки вызовет функцию NullPointerException. Они наиболее распространены, но другие способы перечислены на странице NullPointerException javadoc.
Вероятно, самый быстрый пример кода, который я мог бы придумать для иллюстрации NullPointerException, be:
public class Example {
public static void main(String[] args) {
Object obj = null;
obj.hashCode();
}
}
В первой строке внутри main я явно устанавливаю ссылку Object obj равной null. Это означает, что у меня есть ссылка, но она не указывает на какой-либо объект. После этого я пытаюсь обработать ссылку так, как если бы она указывала на объект, вызывая метод на нем. Это приводит к NullPointerException, потому что нет кода для выполнения в местоположении, на которое указывает ссылка.
(Это техничность, но я думаю, что она упоминает: ссылка, которая указывает на null, равна 't то же, что и указатель C, указывающий на недопустимую ячейку памяти. Нулевой указатель буквально не указывает на в любом месте , который отличается от указаний на местоположение, которое оказывается недопустимым.)
6 ответов
Если Ваше дерево двоичного поиска будет красным черным деревом, или Вы предназначаете к любому виду "древовидного вращения" операции, то дублирующиеся узлы вызовут проблемы. Предположите, что Ваше древовидное правило - это:
оставил < корень < = право
Теперь воображает простое дерево, корень которого равняется 5, оставленному ребенка ноль, и правильному ребенку 5 лет. Если Вы делаете левое вращение на корне, Вы заканчиваете с 5 в покинутом ребенке и 5 в корне с правильным ребенком, являющимся нолем. Теперь что-то в левом дереве равно корню, но Ваше правило выше принятого оставило < корень.
я провел часы, пытаясь выяснить, почему мои красные/черные деревья будут иногда пересекать не в порядке, проблема была тем, что я описал выше. Надо надеяться, кто-то читает это и сохраняет себя часы отладки в будущем!
Много алгоритмов укажут, что дубликаты исключены. Например, алгоритмы в качестве примера в книге Алгоритмов MIT обычно представляют примеры без дубликатов. Это довольно тривиально для реализации дубликатов (или как список в узле, или в одном конкретном направлении.)
Большинство (что я видел) указывает оставленных детей как < = и правильные дети как>. В сущности BST, которое позволяет или правильных или покинутых детей быть равным корневому узлу, потребует, чтобы дополнительные вычислительные шаги закончили поиск, где дублирующиеся узлы позволяются.
Лучше использовать список в узле для хранения дубликатов, поскольку вставка '=' оценивает одной стороне узла, требует, чтобы перезапись дерева на той стороне поместила узел как ребенка, или узел помещается как внук, в какой-то момент ниже, который устраняет часть поисковой эффективности.
необходимо помнить, большинство примеров класса упрощено, чтобы изобразить и обеспечить понятие. Они не стоят приседания во многих реальных ситуациях. Но оператор, "каждый элемент имеет ключ и никакие два элемента, имеет тот же ключ", не нарушен при помощи списка в узле элемента.
Так идут с какой Ваша сказанная книга структур данных!
Редактирование:
Универсальное Определение Дерева двоичного поиска включает хранение, и ищите ключ на основе пересечения структуры данных в одном из двух направлений. В прагматическом смысле, который означает, является ли значение <>, Вы пересекаете структуру данных в одном из двух 'направлений'. Так, в этом смысле дублирующиеся значения не имеют никакого смысла вообще.
Это отличается от BSP, или раздела двоичного поиска, но не всего что отличающийся. Алгоритм для поиска имеет одно из двух направлений для 'перемещения', или это сделано (успешно или нет.), Таким образом, я приношу извинения, что мой исходный ответ не обратился к понятию 'универсального определения', поскольку дубликаты являются действительно отличной темой (что-то, с чем Вы имеете дело после успешного поиска, не как часть двоичного поиска.)
В BST все значения, убывающие на левой стороне узла, являются меньше, чем (или равный, посмотрите позже), сам узел. Точно так же все значения, убывающие на правой стороне узла, больше, чем (или равны), узлы оценивают <глоток> (a) .
Некоторый BSTs может принять решение позволить дублирующиеся значения, следовательно "или равный" спецификаторам выше.
следующий пример может разъясниться:
|
+--- 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 только поддерживает некоторый отсортированный порядок, возрастает ли это или убывает, не релевантно.
Любое определение действительно. Пока Вы последовательны в своей реализации (всегда помещаемые равные узлы направо, всегда помещайте их налево или никогда не позволяйте им), затем, Вы в порядке. Я думаю, что наиболее распространено не позволить им, но это - все еще BST, если им разрешают и размещают любого левого или правого.
Те три вещи, которые Вы сказали, все верны.
- Ключи уникальны
- , Налево ключи, меньше, чем этот
- Направо являются ключами, больше, чем этот
, я предполагаю, что Вы могли инвертировать свое дерево и поместить меньшие ключи справа, но действительно "левые" и "правильное" понятие просто что: визуальное понятие, чтобы помочь нам думать о структуре данных, которая действительно не имеет левого или правого, таким образом, оно действительно не имеет значения.
1.) оставил < = базируйтесь < право
2.) оставил < корень < = право
3.) оставил < корень < право, такое, которые не делают дубликаты ключа, существует.
мне, возможно, придется пойти и откопать мои книги алгоритма, но первое, что пришло на ум (3) каноническая форма.
(1) или (2) только появляются, когда Вы начинаете позволять узлы дубликатов , и Вы помещаете дублирующиеся узлы в само дерево (а не узел, содержащий список).