Каковы преимущества хранения всех элементов в конечных узлах?

Question

Я читаю Расширенные структуры данных Питера Брасса.

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

Что такоепреимущества второй модели перед первой?

Answer 1

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

Например, если у меня есть возможный набор данных от 0 до 1 миллиона, но подавляющее большинство элементов находится либо в верхнем, либо в низком конце, но не в середине, я все же могу захотеть провести первое сравнение с 500 000 - , хотя этого числа нет в моем наборе данных . Если бы у каждого узла были данные, я бы не смог этого сделать. Хотя в теории это обычно не требуется, я много раз сталкивался с этим разделением на основе значения, выходящего за рамки упрощенной реализации моих данных.

Answer 2

B + деревья - пример случая, когда все ключи / значения хранятся в конечных узлах. Основное преимущество здесь состоит в том, что, поскольку все элементы находятся в конечных узлах, конечные узлы могут быть связаны вместе, чтобы сформировать связанный список, который обеспечивает быстрый обход в порядке. Если вы обращаетесь к определенному элементу, вы всегда можете найти следующий элемент в последовательности, не посещая никаких родителей, потому что конечные узлы связаны друг с другом. Файловые системы и системы хранения баз данных могут использовать эти структуры для поиска диапазона и прочего.

Answer 3

Допустим, вы строите дерево над некоторыми объектами по некоторым сложным критериям.На примере рассчитано из нескольких свойств.Иногда вы не можете изменить этот объект, чтобы сохранить вычисленное значение, и вычисление этого критерия является обширным.Таким образом, вы рассчитываете этот критерий только один раз и сохраняете объекты в листах на основе результатов критериев.Затем, когда ваше дерево будет завершено, вы сможете найти нужный объект гораздо быстрее, поскольку вам не нужно рассчитывать критерии для каждого узла дерева на вашем пути.

Answer 4

хорошее хранение информационных объектов в узлах, в данном случае мы говорим о три, полезно для быстрого извлечения информации (быстрее, чем хранение вещей в массиве / хеш-таблице, где наихудший случай доступа O (n) в дереве это O (m) [m - длина n])

смотрите здесь: https://en.wikipedia.org/wiki/Trie

В дереве поиска эти операции могут быть намного более сложными (смотрите AVL Tree O (log n)) и поэтому могут быть медленнее и более полными для реализации.

Какую структуру данных выбрать ?? Ну, это зависит от того, что ты хочешь сделать