4551
правка
B-дерево (дерево многоканального поиска): различия между версиями
Перейти к навигации
Перейти к поиску
B-дерево (дерево многоканального поиска) (посмотреть исходный код)
Версия от 13:06, 1 ноября 2012
, 1 ноября 2012→Нотация
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 20: | Строка 20: | ||
4. Корень T либо является листом, либо имеет не менее двух потомков. | 4. Корень T либо является листом, либо имеет не менее двух потомков. | ||
5. Внутренняя вершина, имеющая k потомков | 5. Внутренняя вершина, имеющая k потомков <math>c_1[v], ... , c_k[v] \; </math>, хранит k – 1 ключей; лист хранит от m/2 – 1 до m – 1 ключей. Ключи keyi [v], 1 < i < k – 1 вершины v 2 T < | ||
хранятся в порядке сортировки, т.е. keyjv] < | хранятся в порядке сортировки, т.е. keyjv] < | ||
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], выполняется следующее соотношение: | ||