Существует ли сбалансированный BST с каждым узлом, поддерживающим размер поддерева? - PullRequest
Новая
       28

Существует ли сбалансированный BST с каждым узлом, поддерживающим размер поддерева?

0 голосов
/ 28 февраля 2019

Существует ли структура balanced BST, которая также отслеживает размер поддерева в каждом узле?

В Java, TreeMap является красно-черным деревом, но не обеспечивает размер поддерева вкаждый узел.

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

Вопросы:

  • Можно ли реализовать такое дерево, сохранив при этом эффективность (O(lg(n)) для основных операций) ?
  • Если да, то есть ли сторонняябиблиотеки предоставляют такой импл?
    A Java импл это замечательно, но другие языки (например, c, go) также будут полезны.

Кстати:

  • Размер поддерева должен отслеживаться в каждом узле.
    Чтобы можно было получить размер, не пересекая поддерево.

Возможное применение:

  • Отслеживать ранг предметов, значение которых (от которых зависит ранг) может изменитьсялетать.

Ответы [ 3 ]

0 голосов
/ 28 февраля 2019

Дерево сбалансированного веса (также называемое деревом Адамса или деревом ограниченного баланса) сохраняет размер поддерева в каждом узле.

Это также позволяет найти N-й элемент,от начала или до конца, в log (n) время.

Моя реализация в Nim находится на github .Он имеет свойства:

  • Общий (параметризованный) ключ, карта значений
  • Вставка (добавление), поиск (получение) и удаление (удаление) в O (журнал (N))время
  • Упорядоченные по ключу итераторы (порядок и повтор):
  • Поиск по относительной позиции от начала или конца (getNth) за время O (log (N))
  • Получитьпозиция (ранг) по ключу в O (log (N)) время
  • Эффективные операции над множествами с использованием древовидных ключей
  • Сопоставление расширений для операций над множествами с дополнительным контролем слияния значений для дубликатов

В Scheme и Haskell также доступны реализации.

0 голосов
/ 28 февраля 2019

Это называется "деревом статистики заказов": https://en.wikipedia.org/wiki/Order_statistic_tree

Довольно просто добавить размер к любому сбалансированному двоичному дереву (красно-черное, avl, b-дерево и т. Д.),или вы можете использовать алгоритм балансировки, который работает с размером напрямую, например, деревья с балансом веса (ответ @DougCurrie) или (лучше) деревья с балансом размера: https://cs.wmich.edu/gupta/teaching/cs4310/lectureNotes_cs4310/Size%20Balanced%20Tree%20-%20PEGWiki%20sourceMayNotBeFullyAuthentic%20but%20description%20ok.pdf

К сожалению, я не думаю, что тамЛюбые реализации стандартной библиотеки, но вы можете найти с открытым исходным кодом, если вы ищете его.Вы можете свернуть свои собственные.

0 голосов
/ 28 февраля 2019

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

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

Этот принцип применяется рекурсивно на всем протяжении листьев.

...