Вопросы с тегом «trees»

11
Может ли предварительный заказ двух разных деревьев быть одинаковыми, даже если они разные?

Эта вопрос в значительной степени объясняет, что они могут, но не показывает никаких примеров наличия двух разных деревьев с одним и тем же обходом предварительного заказа. Также упоминается, что обход по порядку двух разных деревьев может быть одинаковым, хотя они структурно разные. Есть ли пример...

11
Предлагая уточнения типов

На работе мне было поручено вывести некоторую информацию о типах динамического языка. Я переписываю последовательности операторов во вложенные letвыражения, например так: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then {...

11
Структура данных для карты по интервалам

Пусть nnn будет целым числом, и пусть ZZ\mathbb{Z} обозначает множество всех целых чисел. Обозначим через [a,b][a,b][a,b] интервал целых чисел {a,a+1,a+2,…,b}{a,a+1,a+2,…,b}\{a,a+1,a+2,\dots,b\} . Ищу структуру данных для представления отображения f:[1,n]→Zf:[1,n]→Zf:[1,n] \to \mathbb{Z} . Я хочу,...

10
Какова средняя высота бинарного дерева?

Есть ли формальное определение средней высоты бинарного дерева? У меня есть вопрос по нахождению средней высоты двоичного дерева с помощью следующих двух методов: Естественным решением может быть определение средней длины всех возможных путей от корня до листа, то есть AVH1( Т) = 1# листья в  Т⋅ ∑V...

10
Обновление диапазона + запрос диапазона с двоичными индексированными деревьями

Я пытаюсь понять, как двоичные индексированные деревья (деревья Фенвика) могут быть изменены для обработки как запросов диапазона, так и обновлений диапазона. Я нашел следующие источники: http://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/...

10
Доказательство сложности времени для реализации дерева ранжированных сумм в дереве сегментов

Я понимаю , что сегментные дерева могут быть использованы , чтобы найти сумму юга массива . И что это может быть сделано за O ( log n ) в соответствии с руководством здесь .AAAO(logn)O(log⁡n)\mathcal{O}(\log n) Однако я не могу доказать, что время запроса действительно равно . Эта ссылка (и многие...

10
Какова вероятность того, что этот код заканчивается?

Я написал этот код на Python и подумал, а может ли он просто не завершиться (при условии, что у нас было бесконечное количество памяти / времени и нет предела глубины рекурсии). Интуитивно вы думаете, что он заканчивается, поскольку в какой-то момент вам повезет , а если он не закончится, у вас...

10
Какая структура данных будет эффективно хранить целочисленные диапазоны?

Мне нужно сохранить коллекцию целых чисел в диапазоне от 0 до 65535, чтобы я мог быстро сделать следующее: Вставьте новое целое число Вставьте диапазон смежных целых чисел Удалить целое число Удалить все целые числа ниже целого Проверьте, присутствует ли целое число У моих данных есть свойство...

10
Как эффективно создать все двоичные последовательности с одинаковым количеством нулей и единиц?

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

10
Почему минимальная высота бинарного дерева

В моем классе Java мы изучаем сложность различных типов коллекций. Вскоре мы будем обсуждать бинарные деревья, о которых я читал. Книга утверждает, что минимальная высота бинарного дерева составляет , но не дает дополнительных объяснений.log2(n+1)−1log2⁡(n+1)−1\log_2(n+1) - 1 Может кто-нибудь...

10
Алгоритм для проверки, является ли двоичное дерево поисковым деревом и подсчитывает ли количество полных ветвей

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

10
Доказательство того, что случайно построенное двоичное дерево поиска имеет логарифмическую высоту

Как доказать, что ожидаемая высота случайно построенного бинарного дерева поиска с узлами составляет ? В CLRS Введение в алгоритмы есть доказательство (глава 12.4), но я его не понимаю.O ( log n )nnnO(logn)O(log⁡n)O(\log...

9
Как восстановить лес синтаксических деревьев из вектора Эрли?

Использовать вектор Эрли в качестве распознавателя довольно просто: когда достигается конец строки, вам просто нужно проверить завершенную аксиоматическую постановку, начатую в позиции 0. Если у вас есть хотя бы один, тогда строка принимается. Использование вектора Эрли для восстановления дерева...

9
Splay дерево с нечетным числом поворотов

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

9
Логарифмическая или двойная логарифмическая сложность времени

В реальных приложениях есть ли конкретное преимущество при использовании алгоритмов вместо O ( log ( n ) ) ?O(log(log( н ) )О(журнал⁡(журнал⁡(N))\mathcal{O}(\log(\log(n))O (журнал( н ) )O(log⁡(n))\mathcal{O}(\log(n)) Это тот случай, когда можно использовать, например, деревья Ван Эмде Боаса вместо...

9
Полезны ли вероятностные структуры данных поиска?

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