Постраничные бинарные деревья против деревьев AVL и / или B-деревьев

Question

Чем двоичные деревья с разбивкой по страницам отличаются от деревьев AVL и / или B-деревьев?

Answer 1

Несмотря на разную структуру AVL и B-дерева, заявленную Конрадом, использование AVL и B-дерева, я думаю, также отличается. B-дерево обычно используется для реализации индексации. Целью использования B-дерева является уменьшение дискового ввода-вывода, в то время как данные AVL-дерева часто полностью сопротивляются в памяти, а не частично в памяти, частично на диске, как B-дерево. Цель AVL-дерева состоит в том, чтобы избежать появления левого / правого дерева ветвей в некоторой экстремальной ситуации, обеспечивая идеальную сложность времени O (logn) при выполнении операции поиска.

Answer 2

Предлагаю прочитать отличные статьи Википедии на эту тему.

Очень коротко:

• AVL-деревья являются бинарными деревьями поиска (т.е. бинарными деревьями, используемыми для наложения упорядочения на его элементы). Разница заключается в том, что деревья AVL реализуют стратегию самобалансирующегося распределения, чтобы равномерно распределить узлы, чтобы уменьшить максимальную глубину дерева.
• B-деревья являются обобщением бинарных деревьев поиска, т. Е. Они больше не являются бинарными.