4551
правка
B-дерево (дерево многоканального поиска): различия между версиями
Перейти к навигации
Перейти к поиску
B-дерево (дерево многоканального поиска) (посмотреть исходный код)
Версия от 14:12, 1 ноября 2012
, 1 ноября 2012→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 94: | Строка 94: | ||
Мельхорн [17, глава III, 5.3.1] исследовал B-деревья (и более общий случай – (a, b)-деревья с <math>a \ge 2 \; </math> и <math>b \ge 2a \; </math> <math>- 1 \; </math>) в контексте очередей с приоритетами, допускающих слияние. ''Очереди, допускающие слияние'', представляют собой очереди с приоритетами, для которых можно выполнять сцепление и расщепление. | Мельхорн [17, глава III, 5.3.1] исследовал B-деревья (и более общий случай – (a, b)-деревья с <math>a \ge 2 \; </math> и <math>b \ge 2a \; </math> <math>- 1 \; </math>) в контексте очередей с приоритетами, допускающих слияние. ''Очереди, допускающие слияние'', представляют собой очереди с приоритетами, для которых можно выполнять сцепление и расщепление. | ||
Сцепление очередей с приоритетами для множества <math>S_1 \ne \empty \; </math> и множества <math>S_2 \ne \empty \; </math> определяется только для случая, если <math>max \; </math> {<math>x | x \in S_1</math>} <math>< min \; </math> {<math>x | x \in S_2 \; </math>}, в результате чего получается одна очередь с приоритетами | Сцепление очередей с приоритетами для множества <math>S_1 \ne \empty \; </math> и множества <math>S_2 \ne \empty \; </math> определяется только для случая, если <math>max \; </math> {<math>x | x \in S_1</math>} <math>< min \; </math> {<math>x | x \in S_2 \; </math>}, в результате чего получается одна очередь с приоритетами для <math>S_1 \cup S_2</math>. Расщепление очереди с приоритетами для множества <math>S_3 \ne \empty \; </math> в соответствии с некоторым <math>y \in dom(S_3) \; </math> приводит к появлению очередей с приоритетами для множества <math>S_4 := \; </math> {<math>x \in S_3 | x \le y \; </math>} и для множества <math>S_5 := \; </math>{<math>x \in S_3 | x > y \; </math>} (одно из этих множеств может быть пустым). Результат Мельхорна, переформулированный в контексте B-деревьев, выглядит следующим образом: | ||
Теорема 5 (теорема 6, глава III, 5.3.1 в [7]). Если множества S1 ф ; и S2 ф ; представлены B-деревьями, тогда операция Concatenate(S1; S2) выполняется за время O(logmaxfjS1j; jS2jg) и содержит O(logB maxfjS1j; jS2jg)) операций ввода-вывода, а операция Split(S1 ; y) выполняется за время O(logjS1j) и содержит O(log B jS1j) операций ввода-вывода. Все границы приведены для наихудшего случая. | |||
'''Теорема 5 (теорема 6, глава III, 5.3.1 в [7]).''' Если множества S1 ф ; и S2 ф ; представлены B-деревьями, тогда операция Concatenate(S1; S2) выполняется за время O(logmaxfjS1j; jS2jg) и содержит O(logB maxfjS1j; jS2jg)) операций ввода-вывода, а операция Split(S1 ; y) выполняется за время O(logjS1j) и содержит O(log B jS1j) операций ввода-вывода. Все границы приведены для наихудшего случая. | |||
Буферизованные структуры данных | Буферизованные структуры данных | ||