4551
правка
B-дерево (дерево многоканального поиска): различия между версиями
Перейти к навигации
Перейти к поиску
B-дерево (дерево многоканального поиска) (посмотреть исходный код)
Версия от 13:11, 1 ноября 2012
, 1 ноября 2012→Нотация
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 20: | Строка 20: | ||
4. Корень T либо является листом, либо имеет не менее двух потомков. | 4. Корень T либо является листом, либо имеет не менее двух потомков. | ||
5. Внутренняя вершина, имеющая k потомков <math>c_1[v], ... , c_k[v] \; </math>, хранит k – 1 ключей; лист хранит от m/2 – 1 до m – 1 ключей. Ключи | 5. Внутренняя вершина, имеющая k потомков <math>c_1[v], ... , c_k[v] \; </math>, хранит k – 1 ключей; лист хранит от m/2 – 1 до m – 1 ключей. Ключи <math>key_i[v], 1 \le i \le k \;</math> <math>- 1 \; </math> вершины <math>v \in T \; </math> хранятся в порядке сортировки, т.е. <math>key_1[v] \le ... \le key_{k-1}[v] \; </math>. | ||
хранятся в порядке сортировки, т.е. | |||
6. Если v – внутренняя вершина T с k потомками c1 [v],..: ; Cfc[v], то k – 1 ключей keyjv],].. ,keyi_1[v] вершины v делят диапазон ключей, хранящихся в поддеревьях с корнем в вершине потомков v. Если xi – любой ключ, хранящийся в поддереве, корнем которого является ci [v], выполняется следующее соотношение: | 6. Если v – внутренняя вершина T с k потомками c1 [v],..: ; Cfc[v], то k – 1 ключей keyjv],].. ,keyi_1[v] вершины v делят диапазон ключей, хранящихся в поддеревьях с корнем в вершине потомков v. Если xi – любой ключ, хранящийся в поддереве, корнем которого является ci [v], выполняется следующее соотношение: | ||
x1 < keyjv] < x2 < key2[v] < : : : <Xjt_i ^key^Jv] <xk : | x1 < keyjv] < x2 < key2[v] < : : : <Xjt_i ^key^Jv] <xk : | ||