Сложность времени создания двоичного дерева

Я пытаюсь создать дерево из источника, который обеспечивает: 2 узла, которые будут добавлены к дереву, и узел, который должен добавить эти 2 новостных узла. Чтобы найти, где этот узел находится в дереве, я использовал обход ордера, который принимает O (n). Поэтому, если в дереве было добавлено n количество узлов, будет создано все дерево O (n^2). Мое ограничение состоит в том, что для создания дерева требуется только O (n).Сложность времени создания двоичного дерева

источник

2012-03-11 Dan

Я действительно не вижу, как можно добавить n узлов в двоичное дерево один за другим меньше, чем 'O (n log n)'. Кажется, что что-то не хватает в вашем описании. Также я предполагаю, что это домашняя работа, поэтому вы должны добавить правильные метки. – Voo

Зачем вам нужен обход, чтобы найти нужное место в дереве? Узлы должны быть расположены таким образом, чтобы вы могли найти данный узел в среднем времени O (log (n)). Если у вас нет такой договоренности, возможно, двоичное дерево не является правильной структурой для ваших данных. – Gigatron

Вы можете хранить ссылки на каждый узел дерева в HashMap [1], чтобы получить доступ к каждому узлу вместо O(log(n)), который является типичным для деревьев. Это позволило бы построить дерево в O(n) времени, потому что этот HashMap позволяет вам перейти непосредственно к узлу вместо того, чтобы пересекать его из корневого узла дерева.

[1] Ключ был бы тем, что использует источник для однозначной идентификации узлов (я предполагаю, что это целое число или строка). Значение будет ссылкой на узел в дереве. Обратите внимание, что реализация дерева должна сделать все ее узлы общедоступными, поэтому вам, вероятно, потребуется написать дерево самостоятельно или найти подходящую библиотеку (деревья JDK, такие как TreeMap, сохраняют свою внутреннюю структуру конфиденциальной, поэтому они не будут ее обрезать).

источник

2012-03-11 22:23:33

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

twain249: True. Если это домашнее задание, я сомневаюсь, что есть какая-то настоящая причина использовать дерево, кроме того, что говорится в задании. :) Одна из реалистичных (но редких) причин, по которой я мог бы придумать, - это то, что системе необходимо быстро восстановить свое состояние из файла после перезапуска (таким образом, время запуска O (n)), и при нормальной работе система имеет строгий худший случай (таким образом, амортизационная карта хэш-карты O (1) неприемлема, но требуется предсказуемое значение O (log (n)) дерева). –

Слова ** O (1) амортизированное время с учетом совершенной хэш-функции ** или 'O (1) average' должны появляться более в основном в этом ответе :-) –

Поиск уровня узла в двоичном дереве равен O(log(n)), потому что дерево имеет log(n) уровней (каждый уровень занимает в два раза больше уровня выше). Поэтому для создания/вставки n элементов в двоичное дерево это O(nlog(n)).

источник

2012-03-11 22:19:33 twain249

для сложности двоичного дерева поиска будет O (nlogn), когда элементы не отсортированы и отсортированы, это займет O (n^2). Это связано с тем, что для вставки одного элемента в отсортированный список в BST O (n) время берется так для n элементов O (n^2) и для сбалансированного или почти сбалансированного дерева двоичного поиска максимальное время для вставки logn так для n элементов это nlogn

источник

2015-09-18 09:44:49 Guest

Сложность времени создания двоичного дерева

ответ

Смежные вопросы