#algorithm #binary-search-tree #time-complexity #binary-search
#алгоритм #двоичное дерево поиска #временная сложность #двоичный поиск
Вопрос:
Я изучаю структуры данных и алгоритмы, и я застрял на среднем неудачном случае двоичного поиска. Я не смог найти его в своей книге (структуры данных Липшутца), и даже на различных ресурсах в Интернете все они содержат только формулы без каких-либо пояснений. Формулы являются :
Sn= (I n)/n
и
Un= E/(n 1)
где
Sn= number of comparisons in case of successful search
Un= number of comparisons in case of unsuccessful search
I= internal path length of the binary tree, and
E= external path length of the binary tree.
n is the number of nodes in the binary tree.
Здесь я хочу заявить, что я знаю, как получить сравнения в обоих случаях, когда задается фактический случай двоичного поиска, путем создания для него двоичного дерева поиска, как описано здесь
Но после объяснения этого с помощью двоичного дерева они также просто сформулировали формулу, чтобы получить общее представление об этом. первую формулу для Sn я полностью понял, но формула для Un мне просто не ясна.
Комментарии:
1. Для начала, E в формуле Un исходит из того факта, что вам нужно проверить дочерние элементы самых низких узлов (которые будут равны null), где в Sn вам никогда не придется этого делать, потому что целевое значение будет в ненулевом узле. Однако не уверен, откуда берется /(n 1).
2. (n 1) связано с тем, что количество фиктивных узлов (нулевых дочерних элементов) в дереве с n узлами равно n 1. Доказательство смотрите в лемме 3.1 в примечаниях к лекции, на которые даны ссылки.
3. это даже я знаю, но чего я не могу понять, так это того, как одного E достаточно, чтобы выдать количество сравнений для всех неудачных случаев? длина внешнего пути будет на единицу меньше, чем количество сравнений, необходимых для достижения неудачного узла (поскольку длина внешнего пути учитывает количество ребер от корня до внешнего узла), тогда почему мы не добавляем (n 1) к E (1 для каждого неудачного узла), как мы делали в Sn — мы добавили n к длине внутреннего пути.
4. Вы можете найти подробное решение cse.iitkgp.ac.in /~pb/алгоритм-1-pb-10.pdf
Ответ №1:
Это потому, что среднее число сравнений при неудачном поиске равно «средней длине внешнего пути» дерева, которая задается выражением E / (n 1) , поскольку существует (n 1) внешних узлов, которые представляют все случаи сбоя.
Вы сравниваете его со средним успешным случаем, который вызывает у вас путаницу. В случае успешного поиска количество сравнений равно количеству узлов на пути от корневого узла к этому успешному узлу. Но неудачный поиск можно понимать как вставку этого конкретного узла в дерево. т.е. вставка элемента эквивалентна неудачному поиску для этого узла. И мы знаем, что количество сравнений для нахождения узла в дереве ровно на 1 больше, чем количество сравнений, необходимых для его вставки.
Например: рассмотрим отсортированный массив: 3,7,10,13,15
его двоичный поиск может быть представлен следующим деревом двоичного поиска:
10
/
/
/
3 13
/ /
F 7 F 15
/ /
F F F F
где F обозначает случаи сбоя.
Теперь это показывает, что если вы ищете 10 в этом массиве, потребуется всего одно сравнение, если вы ищете 3 или 13, для обоих потребуется по 2 сравнения каждое, аналогично, если вы ищете 7 или 15, потребуется по 3 сравнения каждое.
Длина внутреннего пути дает количество ребер от корня до определенного внутреннего узла, поэтому для каждого узла это будет на единицу меньше количества сравнений, необходимых для успешного поиска этого узла. Следовательно, мы добавляем 1 для каждого узла к длине внутреннего пути, что приводит к сумме n (поскольку существует n внутренних узлов), поэтому формула (I n) / n оправдана.
Теперь, переходя к случаю неудачного поиска, предположим, что в этом примере массива вы хотите выполнить поиск по 2 (которого нет в массиве), поэтому первое сравнение будет выполнено со средним элементом, т. Е. 10, затем второе сравнение с 3, и поскольку поиск не может идти ниже 3, наш поиск заканчивается здесь только 2 сравнениями, в отличие от того, что вы заявили, что потребуется 3 сравнения, поскольку он находится на уровне 2 дерева. Аналогично, при поиске 5 в этом массиве вам придется провести 3 сравнения, а не 4. Следовательно, мы видим, что для каждого неудачного узла требуются сравнения, равные длине его пути. И поэтому нам не нужно добавлять дополнительный 1 для каждого внешнего узла, а среднее сравнение при неудачном поиске равно средней длине внешнего пути двоичного дерева. что оправдывает формулу E/(n 1).
Я думаю, это должно рассеять ваши сомнения в том, почему мы не добавили дополнительный 1 для каждого узла.
приветствия!