Comments 2
Рад видеть, что вы поделились своими «копейками». В любом случае материал будет полезен многим исследователям! Спасибо, за хороший материал!
2-3-4-дерево — это частный случай Б-дерева. Если это понять, то дальше всё становится очень простым и понятным.
Б-деревья сбалансированы по высоте — так, что все листья находятся на одном ярусе.
Каждый узел, или страница, содержит K ключей (здесь — от 1 до 3) и, соответственно, K+1 возможных поддеревьев.
Почему именно 2-3-4, а не 2-8, или не 2-128, например?
Ну, во-первых, чем больше размер страницы, тем больше вероятность недозаполненных страниц, больше накладных расходов на память.
Но тут нужно смотреть и на минимальный размер блока памяти, и размер технических данных:
у 2-дерева на каждое место под ключ приходится 2 или 3 указателя (без или с указателем на родительский узел),
у 2-128 — всего лишь 128/127 или 129/127, т.е. практически 1 указатель на ключ. Есть разница, правда же?
Во-вторых, 2-3-4-дерево очень изящно отображается на двоичное дерево. И да, это хорошо знакомое нам красно-чёрное дерево.
Проще сказать, КЧД совмещает в себе простоту алгоритма обхода и поиска, как у произвольных двоичных деревьев, и простоту поддержки сбалансированности, присущей Б-деревьям. И всего-то нужно, двоичный признак (цвет).
На 2-3-кучу это дерево похоже лишь названием. Всё-таки разного рода кучи — это одно, а разного рода двоичные и Б-деревья поиска — совсем другое.
Б-деревья сбалансированы по высоте — так, что все листья находятся на одном ярусе.
Каждый узел, или страница, содержит K ключей (здесь — от 1 до 3) и, соответственно, K+1 возможных поддеревьев.
Почему именно 2-3-4, а не 2-8, или не 2-128, например?
Ну, во-первых, чем больше размер страницы, тем больше вероятность недозаполненных страниц, больше накладных расходов на память.
Но тут нужно смотреть и на минимальный размер блока памяти, и размер технических данных:
у 2-дерева на каждое место под ключ приходится 2 или 3 указателя (без или с указателем на родительский узел),
у 2-128 — всего лишь 128/127 или 129/127, т.е. практически 1 указатель на ключ. Есть разница, правда же?
Во-вторых, 2-3-4-дерево очень изящно отображается на двоичное дерево. И да, это хорошо знакомое нам красно-чёрное дерево.
Проще сказать, КЧД совмещает в себе простоту алгоритма обхода и поиска, как у произвольных двоичных деревьев, и простоту поддержки сбалансированности, присущей Б-деревьям. И всего-то нужно, двоичный признак (цвет).
На 2-3-кучу это дерево похоже лишь названием. Всё-таки разного рода кучи — это одно, а разного рода двоичные и Б-деревья поиска — совсем другое.
Sign up to leave a comment.
Структура данных 2-3-4 дерево