Создание двоичного дерева поиска с лучшей сложностью

Question

Вам предоставляется число, которое является корнем двоичного дерева поиска. Затем вам предоставляется массив из N элементов, которые вы должны вставить в двоичное дерево поиска. Сложность времени равна N^2, если массив находится в отсортированном порядке. Мне нужно получить одну и ту же структуру дерева в гораздо большей сложности (скажем, NlogN). Я много пробовал, но не смог его решить. Может ли кто-нибудь помочь?

Answer 1

Если вы ищете слово в словаре, вы открываете словарь примерно наполовину и смотрите на страницу. Затем вы узнаете, находится ли поисковое слово в первой или второй половине словаря. Повторите, исключая половину оставшихся слов на каждом проходе, и вы скоро сузите его до одного слова. 4 миллиарда словарей слова возьмут около 32 проходов.

Двоичное дерево поиска использует тот же принцип. Кроме того, вы также можете вставить. Вставка - это O (log N), если дерево не вырождается. Чтобы предотвратить вырождение дерева, вы используете систему «красных» и «черных» узлов (цвета просто обычные), и вы не разрешаете длинные прогоны любого цвета. Полное объяснение в моей книге, основные алгоритмы

http://www.lulu.com/spotlight/bgy1mm

Реализация здесь

https://github.com/MalcolmMcLean/babyxrc/blob/master/src/rbtree.c https://github.com/MalcolmMcLean/babyxrc/blob/master/src/rbtree.h

Но вам потребуется какое-то объяснение, если вы хотите узнать о красных черных деревьев от него.

Answer 2

Я предполагаю, что все числа различны (если это не так, вы можете использовать пару (число, индекс)).

Предположим, что мы хотим вставить, мы хотим вставить элемент X. Если это самый маленький/самый большой элемент до сих пор, он ясно, где он идет.

Let's a = max y: y in tree and y < X и . Я утверждаю, что:

1. Один из них является предком другого.

2. Либо a не имеет детей (b не имеет детей).

Доказательство:

1. Пусть это не так. Пусть l = lca(a, b). Так как a находится в левом поддереве и b находится в правом поддереве, a < l < b. Противоречие.

2. Позвольте a быть предком b. Если b имеет левого ребенка c. Чем a < c < b. Противоречие (другой случай обрабатывается аналогичным образом).

Таким образом, решение выглядит следующим образом:

1. Пусть это держать набор элементов, которые уже находятся в дереве (я имею в виду эффективный набор с работы LOWER_BOUND как std::set в C++ или TreeSet в Ява).

2. Давайте найдем a и b, как описано выше при каждом введении (в O(log N) время, используя операцию lower_bound установочных наборов). Именно у одного из них нет соответствующего ребенка. Вот где новый элемент.

Общая вычислительная проницаемость O(N log N).