Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[127]

B-Tree-Split-Child(2;, г, у)

1

z <- Allocate-Node()

2

leaj[z] <r- leaj[y]

3

n[z] <r- t - 1

4

for j <- 1 to t - 1

5

do keyj[z] <r- keyj+t[y]

6

if not leaj[y]

7

then for j <- 1 to i

8

do Cj[z] <- cj+f[y]

9

raM * - 1

10

for j <- n[x]-\- 1 downto i + 1

11

do cj+i[a;] <- с[ж]

12

ci+1[x] <r- z

13

for j <- п[ж] downto г

14

do keyj+i[x] <- fcet/j[a;]

15

А;ег/г-[ж] keyt[y]

16

n[x] <- п[ж] + 1

17

DlSK-WRITE(y)

18

DlSK-WRITE(2:)

19

DiSK-WRiTE(a;)

Вершина у имела It детей; после преобразования в ней осталось t наименьших из них, а остальные t стали детьми новой вершины z, которая в свою очередь стала ребёнком вершины х. Ключ-медиана вершины у добавлен к вершине х и стал разделителем между вершиной у и следующей за ней вершиной z.

Строки 1-8 формируют вершину z и передают ей детей. Строка 9 меняет вершину у. Наконец, строки 10-16 вносят соответствующие изменения в вершину х. Строки 17-19 сохраняют изменения на диске. Время работы циклов (строки 4-5 и 7-8) равно 0(£). (Для остальных циклов требуется не больше t шагов).

Добавление элемента в Б-дерево

Процедура B-Tree-Insert добавляет элемент к в Б-дерево Г, пройдя один раз от корня к листу. На это требуется время O(th) = 0(t\ogt п) и 0(h) обращений к диску, если высота дерева h. По ходу дела мы с помощью процедуры B-Tree-Split разделяем встречающиеся нам полные вершины, используя такое наблюдение: если полная вершина имеет неполного родителя, то её можно разделить, так как в родителе есть место для дополнительного ключа. В конце концов мы оказываемся в неполном листе, куда и добавляем новый элемент.


Рис. 19.6 Рис. 19.6. Корень г Б-дерева (с t = 4) является полной вершиной. Он делится на две половины; при этом создается новый корень s, детьми которого становятся эти вершины. Новый корень s содержит ключ-медиану старого корня. Высота Б-дерева увеличилась на единицу.

10 else B-Tree-Insert-Nonfull (г, к)

Строки 3-9 относятся к случаю добавления в дерево с полным корнем (пример на рис. 19.6). Именно в этом случае увеличивается высота Б-дерева. Отметим, что точкой роста Б-дерева является корень (а не лист, как в двоичных деревьях поиска).

Сделав корень неполным (если он не был таковым с самого начала), мы вызываем процедуру B-TREE-lNSERT-NoNFULL(a;, к), которая добавляет элемент к в поддерево с корнем в неполной вершине х. Эта процедура рекурсивно вызывает себя, при необходимости (если вершина оказалась полной) выполнив разделение.

B-Tree-Insert(T, к)

1г <- root[T]

2if n[r] = 2t-l

3then s <- Allocate-Node()

4root[T] <- s

5leaj[s] - false

6n[s] <- 0

7ci[s] <- r

8B-Tree-Split-Child(s

9B-Tree-Insert-Nonfu


B-Tree-Insert-Nonfull (ж, к)

1г 4- п[х]

2if leaj[x}

3then while / 1 and к < кегц[х]

4do кеуг+1[х] <- А;ег/г[ж] 5

6A;eyi+i[a.] «- /г

7га[ж] <- га[ж] + 1

8Disk-Write (ж)

9else while г 1 and к < keyi[x]

10do / <- г - 1

11г - г + 1

12Disk-Read(c8])

13if га[сг[ж]] = 2t - 1

14then B-Tree-Split-Child (ж, i, ct[x])

15if к > &е?/г[ж]

16then г <r- i + 1

17B-Tree-Insert-Nonfull (сг[ж], /г)

Эта процедура работает следующим образом. Если вершина ж - лист, то ключ к в него добавляется (строки 3-8; напомним, что вершина ж предполагается неполной). В противном случае нам нужно добавить к к поддереву, корень которого является ребёнком ж. В строках 9-11 мы находим нужного ребёнка вершины ж. Если этот ребёнок оказывается полной вершиной (строка 13), то в строке 14 он разделяется на две неполных вершины, и в строках 15-16 определяется, в какое из новых поддеревьев следует добавить к. (Заметим, что после изменения г в строке 16 нет необходимости обращаться к диску - вновь созданная вершина, к которой мы обратимся в строке 17, уже находится в оперативной памяти.) Таким образом, мы знаем, что вершина сг[ж] - неполная, и в строке 17 добавляем ключ к в соответствующее поддерево с помощью рекурсивного вызова процедуры B-Tree-Insert-Nonfull. На рис. 19.7 показаны разные случаи добавления элемента в Б-дерево.

Процедура B-Tree-Insert-Nonfull использует 0(1) операций Disk-Read и Disk-Write (если не считать рекурсивного вызова). Следовательно, для Б-дерева высоты h процедура B-Tree-Insert обращается к диску 0(h) раз. Время вычислений есть 0(th) = 0(t\ogth). В процедуре B-Tree-Insert-Nonfull рекурсивный вызов является последним оператором (tail recursion), и поэтому мы могли бы заменить рекурсию циклом. Отсюда видно, что число секторов, которые необходимо держать в оперативной памяти, есть 0(1).



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]