4551
правка
B-дерево (дерево многоканального поиска): различия между версиями
Перейти к навигации
Перейти к поиску
B-дерево (дерево многоканального поиска) (посмотреть исходный код)
Версия от 13:13, 1 ноября 2012
, 1 ноября 2012→Нотация
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 22: | Строка 22: | ||
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>. | 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 потомками | 6. Если v – внутренняя вершина T с k потомками <math>c_1[v], ..., c_k[v] \; </math>, то k – 1 ключей <math>key_1[v], ... ,key_{k-1}[v] \; </math> вершины v делят диапазон ключей, хранящихся в поддеревьях с корнем в вершине потомков v. Если <math>x_i \; </math> – любой ключ, хранящийся в поддереве, корнем которого является <math>c_i[v] \; </math>, выполняется следующее соотношение: | ||
x1 < keyjv] < x2 < key2[v] < : : : <Xjt_i ^key^Jv] <xk : | x1 < keyjv] < x2 < key2[v] < : : : <Xjt_i ^key^Jv] <xk : | ||