2-3 дерево — различия между версиями
(Новая страница: «''' 2-3 дерево ''' — структура данных являющаяся B-деревом cтепени 1, каждая вершина к…») |
|||
| Строка 1: | Строка 1: | ||
| − | ''' 2-3 дерево ''' — структура данных являющаяся [[B-дерево|B-деревом]] cтепени 1, каждая вершина которого может содержать двух или трех потомков. Информация в таких деревьях хранится в листьях, а остальные вершины содержат вспомогательную информацию для организации поиска.2-3 деревья сбалансированы, то есть каждое левое, правое, и центральное поддерево одинаковой высоты, и таким образом содержат равное (или почти равное) число данных. | + | ''' 2-3 дерево ''' — структура данных являющаяся [[B-дерево|B-деревом]] cтепени 1, каждая вершина которого может содержать двух или трех потомков. |
| + | |||
| + | == Структура == | ||
| + | |||
| + | Информация в таких деревьях хранится в листьях, а остальные вершины содержат вспомогательную информацию для организации поиска.2-3 деревья сбалансированы, то есть каждое левое, правое, и центральное поддерево одинаковой высоты, и таким образом содержат равное (или почти равное) число данных. | ||
| + | |||
| + | == Свойства == | ||
| + | * Все нелистовые вершины содержат одно поле и 2 поддерева или 2 поля и 3 поддерева. | ||
| + | * Все листовые вершины находятся на одном уровне (на нижнем уровне) и содержат 1 или 2 поля. | ||
| + | * Все данные отсортированы | ||
Версия 08:38, 8 марта 2011
2-3 дерево — структура данных являющаяся B-деревом cтепени 1, каждая вершина которого может содержать двух или трех потомков.
Структура
Информация в таких деревьях хранится в листьях, а остальные вершины содержат вспомогательную информацию для организации поиска.2-3 деревья сбалансированы, то есть каждое левое, правое, и центральное поддерево одинаковой высоты, и таким образом содержат равное (или почти равное) число данных.
Свойства
- Все нелистовые вершины содержат одно поле и 2 поддерева или 2 поля и 3 поддерева.
- Все листовые вершины находятся на одном уровне (на нижнем уровне) и содержат 1 или 2 поля.
- Все данные отсортированы
