Нод 30 и 40: НОД и НОК для 30 и 40 (с решением)

следующий → ← предыдущая

Поскольку мы знаем, что в бинарном дереве поиска узлы в левом поддереве имеют меньшее значение, чем корневой узел, а узлы в правом поддереве имеют большее значение, чем корневой узел.

Мы знаем ключевые значения каждого узла в дереве, а также знаем частоты каждого узла с точки зрения поиска, что означает, сколько времени требуется для поиска узла. Частота и ключ-значение определяют общую стоимость поиска узла. Стоимость поиска является очень важным фактором в различных приложениях. Общая стоимость поиска узла должна быть меньше. Время, необходимое для поиска узла в BST, больше, чем в сбалансированном двоичном дереве поиска, поскольку сбалансированное двоичное дерево поиска содержит меньшее количество уровней, чем BST. Существует один способ, который может снизить стоимость двоичного дерева поиска, известный как 9.0010 оптимальное бинарное дерево поиска

Давайте разберемся на примере.

Если ключи 10, 20, 30, 40, 50, 60, 70

В приведенном выше дереве все узлы левого поддерева меньше значения корневого узла, а все узлы правого поддерева больше значения корневого узла. Максимальное время, необходимое для поиска узла, равно минимальной высоте дерева, равной logn.

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

Например: 10, 20, 30 — это ключи, а следующие — бинарные деревья поиска, которые можно составить из этих ключей.

Формула расчета количества деревьев:

Когда мы используем приведенную выше формулу, оказывается, что всего можно создать 5 деревьев.

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

В приведенном выше дереве можно сделать всего 3 сравнения. Среднее количество сравнений можно сделать следующим образом:

В приведенном выше дереве среднее количество сравнений, которые можно выполнить, равно:

В приведенном выше дереве среднее количество сравнений, которые можно выполнить, равно:

В приведенном выше дереве общее количество сравнений может быть равно 3. Таким образом, среднее количество сравнений, которое может быть выполнено, равно:

В приведенном выше дереве общее количество сравнений может быть равно 3. Таким образом, среднее количество сравнений, которое может быть выполнено, равно:

В третьем случае количество сравнений меньше, потому что высота дерева меньше, поэтому это сбалансированное бинарное дерево поиска.

До сих пор мы читали о сбалансированном по высоте бинарном дереве поиска. Для нахождения оптимального бинарного дерева поиска определим частоту поиска ключа.

Предположим, что частоты, связанные с клавишами 10, 20, 30, равны 3, 2, 5.

Вышеуказанные деревья имеют разные частоты. Дерево с наименьшей частотой будет считаться оптимальным бинарным деревом поиска. Дерево с частотой 17 является самым низким, поэтому его можно рассматривать как оптимальное бинарное дерево поиска.

Динамический подход

Рассмотрим приведенную ниже таблицу, содержащую ключи и частоты.

Сначала вычислим значения, где j-i равно нулю.

Когда i=0, j=0, тогда j-i = 0

Когда i = 1, j=1, тогда j-i = 0

Когда i = 2, j=2, тогда j-i = 0

Когда i = 3, j=3, тогда j-i = 0

Когда i = 4, j=4, тогда j-i = 0

Следовательно, c[0, 0] = 0, c[1 , 1] = 0, c[2,2] = 0, c[3,3] = 0, c[4,4] = 0

Теперь посчитаем значения где j-i равно 1.

Когда j=1, i=0, тогда j-i = 1

Когда j=2, i=1, тогда j-i = 1

Когда j=3, i=2, тогда j-i = 1

Когда j=4, i=3, тогда j-i = 1

Теперь для расчета стоимости будем учитывать только j-е значение.

Стоимость c[0,1] равна 4 (Ключ равен 10, а стоимость, соответствующая ключу 10, равна 4).

Стоимость c[1,2] равна 2 (Ключ равен 20, а стоимость, соответствующая ключу 20, равна 2).

Стоимость c[2,3] равна 6 (Ключ равен 30, а стоимость, соответствующая ключу 30, равна 6)

Стоимость c[3,4] равна 3 (Ключ равен 40, а стоимость, соответствующая ключу 40, равна 3)

Теперь посчитаем значения где j-i = 2

Когда j=2, i=0, тогда j-i = 2

Когда j=3, i=1, тогда j-i = 2

Когда j=4, i=2, тогда j-i = 2

В данном случае мы будем рассматривать два ключа.

• Когда i=0 и j=2, то ключи 10 и 20. Есть два возможных дерева, которые можно составить из этих двух ключей, показанных ниже:

В первом бинарном дереве стоимость будет: 4*1 + 2*2 = 8

Во втором бинарном дереве стоимость будет: 4*2 + 2*1 = 10

Минимальная стоимость 8; следовательно, c[0,2] = 8

• Когда i=1 и j=3, то ключи 20 и 30. Есть два возможных дерева, которые можно составить из этих двух ключей, показанных ниже:

В первом бинарном дереве стоимость будет: 1*2 + 2*6 = 14

Во втором бинарном дереве стоимость будет: 1*6 + 2*2 = 10

Минимальная стоимость 10; следовательно, c[1,3] = 10

• Когда i=2 и j=4, мы будем рассматривать ключи 3 и 4, то есть 30 и 40. Есть два возможных дерева, которые можно составить из этих двух ключей, показанных ниже:

В первом бинарном дереве стоимость будет: 1*6 + 2*3 = 12

Во втором бинарном дереве стоимость будет: 1*3 + 2*6 = 15

Минимальная стоимость 12, поэтому c[2,4] = 12

Теперь посчитаем значения при j-i = 3

Когда j=3, i=0, тогда j-i = 3

Когда j=4, i=1, тогда j-i = 3

• Когда i=0, j=3, мы будем рассматривать три ключа, то есть 10, 20 и 30.

Ниже приведены деревья, которые можно построить, если 10 считать корневым узлом.

В приведенном выше дереве 10 — это корневой узел, 20 — правый потомок узла 10, а 30 — правый потомок узла 20.

Стоимость будет: 1*4 + 2*2 + 3*6 = 26

В приведенном выше дереве 10 — это корневой узел, 30 — правый дочерний элемент узла 10, а 20 — левый дочерний элемент узла 20.

Стоимость будет: 1*4 + 2*6 + 3*2 = 22

Следующее дерево может быть создано, если 20 считается корневым узлом.

В приведенном выше дереве 20 является корневым узлом, 30 — правым дочерним элементом узла 20, а 10 — левым дочерним элементом узла 20.

Стоимость будет: 1*2 + 4*2 + 6*2 = 22

Ниже приведены деревья, которые можно создать, если 30 считается корневым узлом.

В приведенном выше дереве 30 — это корневой узел, 20 — левый дочерний элемент узла 30, а 10 — левый дочерний элемент узла 20.

Стоимость будет: 1*6 + 2*2 + 3*4 = 22

В приведенном выше дереве 30 — это корневой узел, 10 — левый дочерний элемент узла 30, а 20 — правый дочерний элемент узла 10.

Стоимость будет: 1*6 + 2*4 + 3*2 = 20

Таким образом, минимальная стоимость составляет 20, что составляет корень 3 ^rd . Итак, c[0,3] равно 20.

• При i=1 и j=4 будем рассматривать ключи 20, 30, 40

c[1,4] = min{ c[1,1] + c[2,4], c[1,2] + c[3,4], c[1,3] + c[4, 4] } + 11

= мин{0+12, 2+3, 10+0}+ 11

= мин{12, 5, 10} + 11

Минимальное значение 5; следовательно, c[1,4] = 5+11 = 16

• Теперь рассчитаем значения при j-i = 4

Когда j=4 и i=0, тогда j-i = 4

В данном случае мы будем рассматривать четыре ключа, т. е. 10, 20, 30 и 40. Частоты 10, 20, 30 и 40 равны 4, 2, 6 и 3 соответственно.

w[0, 4] = 4 + 2 + 6 + 3 = 15

Если считать 10 корневым узлом, то

C[0, 4] = мин {c[0,0] + c[1,4]}+ w[0,4]

= мин {0 + 16} + 15 = 31

Если считать 20 корневым узлом, то

С[0,4] = мин{с[0,1] + с[2,4]} + ш[0,4]

= мин{4 + 12} + 15

= 16 + 15 = 31

Если считать 30 корневым узлом, то

С[0,4] = мин{с[0,2] + с[3,4]} +w[0,4]

= мин {8 + 3} + 15

= 26

Если считать 40 корневым узлом, то

С[0,4] = мин{с[0,3] + с[4,4]} + ш[0,4]

= мин{20 + 0} + 15

= 35

В приведенных выше случаях мы заметили, что 26 — это минимальная стоимость; следовательно, c[0,4] равно 26,

Оптимальное бинарное дерево может быть создано как:

Общая формула расчета минимальной стоимости:

C[i,j] = min{c[i, k-1] + c[k,j]} + w(i,j)

Очередь Next TopicPriority с использованием связанного списка

← предыдущая следующий →