Дерево AVL по сравнению с B-деревом
Как AVL является деревом, отличающимся от B-дерева?
3 ответа
Деревья AVL предназначены для использования в памяти, где произвольный доступ относительно дешев. B-деревья лучше подходят для дискового хранилища, потому что они группируют большее количество ключей в каждый узел, чтобы минимизировать количество поисков, требуемых операцией чтения или записи. (Вот почему B-деревья часто используются в файловых системах и базах данных, таких как SQLite .)
Дерево AVL - это самобалансирующееся двоичное дерево поиска, сбалансированное для поддержания высоты O (log n).
B-дерево - это сбалансированное дерево, но это не двоичное дерево. У узлов больше дочерних узлов, что увеличивает время поиска для каждого узла, но уменьшает количество узлов, которые необходимо посетить при поиске. Это делает их удобными для дисковых деревьев. Дополнительные сведения см. В статье Википедии .
AVL является самобалансирующимся, гарантируя, что все операции выполняются за O (log n) в среднем и худшем случаях.