Оптимальные деревья двоичного поиска (Темы на автомат)

Оптимальные деревья двоичногопоиска1Двоичное дерево поискаДеревом двоичного поиска для множестваS называется помеченное двоичноедерево, каждый узел v которого помеченэлементом l(v) ∈ S так, что1. l(u) < l(v) для каждого узла u из левогоподдерева2. l(u) > l(v) для каждого узла u из правогоподдерева3. для каждого элемента a ∈ S существуетровно один узел v, для которого l(v) = a5321648792 . 1СвойстваВремя поика элемента – высота дерева ~ O(log n)Время вставки/удаления ~ O(log n)2 .

2ЗадачаПостроить дерево двоичного поиска так, чтобы минимизировать среднее премя поискаэлементов из последовательности Q.3 . 1ЗадачаДано:1. Множество элементов S = {a , a , … , a } для размешения в дереве2. p – вероятность появления элемента a в последовательности Q3. q – вероятность появления в Q элемента a такого, что a < a < a . (q – вероятностьпоявления a < a ; q – вероятность появления a > a )1i2niii1ni+10n3 . 2ЗадачаПредположение:Введем n + 1 фиктивный лист f которые будут отражать элементы из S¯¯¯i536214f3f4f1f58793 . 3ЗадачаЦелевая функция:nn∑ pi depth (ai ) + ∑ qi (depth (fi ) − 1) → mini=1i=03 . 4РешениеПрименим подход "разделяй и влавствуй": выберем элемент a , который нужнопоместить в корень, а затем рекурсивно применим процедуру к правому и левомуподдеревьям.iВопрос: Как выбрать корень?Ответ: переберем все возможные варианты.

При этом придется решать 2n подзадач.Можно заметить, что подзадачи часто пересекаются, значит можно эффективноприменить динамическое программирование.4 . 1РешениеДинамическое программированиеДинамическое программирование применимо тогда, когда подзадачи не являютсянезависимыми, иными словами, когда у подзадач есть общие подзадачи. Алгоритм,основанный на динамическом программировании, решает каждую из подзадачединожды и запоминает ответы в специальной таблице. Это позволяет не вычислятьзаново ответ к уже встречавшейся подзадаче.4 .

2РешениеПусть T – дерево наименьшей стоимости для подмножества {a , … , a– его корень. T – пустое дерево, c = 0 .ijiiijki,k−1jcij =ijijи правого поддерева T , то:kjj∑ pl depthij (al ) + ∑ ql (depthij (fl ) − 1) =l=i+1=; c – его стоимость; riiТогда если дерево T состоит из корня a , левого поддерева Tk−1j}i+1l=ijk−1j∑ pl depthij (al ) + ∑ ql (depthij (fl ) − 1) + ∑ pl depthij (al ) + ∑ ql (depthij (fl ) − 1) + pk =l=i+1l=il=k+1k−1k−1jl=kjjj= ci,k−1 + ckj + pk + ∑ pl + ∑ ql + ∑ pl + ∑ ql = ci,k−1 + ckj + ∑ pl + ∑ qll=i+1l=il=k+1l=kl=i+1l=iwij4 .

3РешениеТаким образом будем выбиратьk = argmin (ci,l−1 + clj )i<l≤jПосле чего поставим a в корень и построим поддеревья Tki,k−1иTkj4 . 4Алгоритм123456789101112131415161718for i = 0:nw[i,i] = q[i]c[i,i] = 0endfor len = 1:n, i = 0:n-lenj = i + lenw[i,j] = w[i,j-1] + p[j] + q[j]k = i+1min = c[i,k-1]+c[k,j]for m = i+2:jif c[i,m-1] + c[m,j] < mink = mmin = c[i,m-1] + c[m,j]endendc[i,j] = min + w[i,j]opt[i,j] = kend1 function makeTree(i,j)2if i == j3return nothing4end5k = opt[i,j]6return Node(7value = a[k],8left = makeTree(i, k-1),9right = makeTree(k, j)10)11 end5ПримерПусть S,= {1, 2, 3, 4} p1 =14, p2 =18, p3 = p4 =116,q0=18, q1 =316, q2 = q3 = q4 =len\i012340w = 2/16w = 3/16w = 1/16w = 1/16w = 1/16c = 0c = 0c = 0c = 0c = 0w = 9/16w = 4/16w = 3/16w = 3/16c = 9/16c = 4/16c = 3/16c = 3/16opt = 1opt = 2opt = 3opt = 4w = 12/16w = 8/16w = 5/16c = 18/16c = 11/16c = 8/16opt = 1opt = 2opt = 3w = 14/16w = 10/16c = 25/16c = 18/16opt = 1opt = 21234116w = 1c = 33/16opt = 26 .

1ПримерПусть S,= {1, 2, 3, 4} p1 =14, p2 =18, p3 = p4 =116,q0=18, q1 =316, q2 = q3 = q4 =11621346 . 2АнализТеорема:Алгоритм сторит оптимальное дерево двоичного поика за время O(n3)Доказательство:Оптимальность:Очевидно, что если G – оптимальное дерево построеное на элементах {a , … , a } скорнем a , то его левое поддерево – оптимальное дерево G, построенное наэлементах {a , … , a } . Аналогично для правого поддерева.ijikji,k−1ik−1Тогда индукцией легко проверить, что алгоритм строит оптимальное дерево.7 .

1АнализТрудоемкость:1 for i = 0:n2w[i,i] = q[i]3c[i,i] = 04 end5 for len = 1:n, i = 0:n-len6789101112131415161718 endj = i + lenw[i,j] = w[i,j-1] + p[j] + q[j]k = i+1min = c[i,k-1]+c[k,j]for m = i+2:jif c[i,m-1] + c[m,j] < mink = mmin = c[i,m-1] + c[m,j]endendc[i,j] = min + w[i,j]opt[i,j] = k2t1 = O (n) + O (n3⋅ n) = O (n )nt1 ≈ n + 1 + ∑len=1∑n−leni=0( (i + l) − i) =j= n + 1 +163n+122n+133n = O (n )7 . 2АнализТрудоемкость:1 function makeTree(i,j)2if i == j3return nothing4end5k = opt[i,j]6return Node(7value = a[k],left = makeTree(i, k-1),8right = makeTree(k, j)910)11 endt2 = O (n + (n + 1)) = O (n)Итого: t = t13+ t2 = O (n ).7 .

3ЗамечаниеД. Кнут в статье "Optimum Binary Search Trees" (1971) показал, что можно искать кореньдерева T между корнями деревьев TиT, т.е. r≤ r≤ rИдея:iji,j−1i+1,ji,j−1iji+1,jЕсли a – корень оптимального дерева на элементах `{a , … , a } `, то при добавлениеэлемента a , т.ч. a> a ∀i = 1, … , n , оптимальный корень не может сметитьсявлево.k1n+1n+1ni8 .

1ЗамечаниеАлгоритм21 <...>2 for len = 2:n, i = 0:n-lenj = i + len34w[i,j] = w[i,j-1] + p[j] + q[j]5k = opt[i,j-1]6min = c[i,k-1]+c[k,j]7for m = opt[i,j-1]+1 : opt[i+1,j]if c[i,m-1] + c[m,j] < min8k = m9min = c[i,m-1] + c[m,j]1011end12end13c[i,j] = min + w[i,j]14opt[i,j] = k15 endt1 = O (n) + O (n ⋅ (n + n)) = O (n )8 . 2Оптимальные деревья двоичногопоиска9.