Чем дерево AVL отличается от B-дерева?
Опубликовано: 26 Февраля, 2023
АВЛ-деревья:
AVL tree is a self-balancing binary search tree in which each node maintain an extra factor which is called balance factor whose value is either -1, 0 or 1.
B-дерево:
A B-treeis a self – balancing tree data structure that keeps data sorted and allows searches, insertions, and deletions in O(log N) time.
Разница между деревом AVL и B-деревом:
| С.№ | АВЛ-деревья | B-дерево |
|---|---|---|
1 | Это самобалансирующееся бинарное дерево поиска. | Это многоходовое дерево (N – арное дерево). |
2 | Каждый узел содержит не более 2 дочерних узлов | В этом дереве узлы могут иметь несколько дочерних узлов. |
3 | Он имеет коэффициент баланса, значение которого равно -1, 0 или 1. Коэффициент баланса = (высота левого поддерева)-(высота правого поддерева) или же Коэффициент баланса = (высота правого поддерева)-(высота левого поддерева) | B-дерево определяется термином минимальная степень «t». Значение t зависит от размера блока диска. Каждый узел, кроме корня, должен содержать не менее t-1 ключей. Корень может содержать минимум 1 ключ. |
4 | Дерево AVL имеет высоту журнала (N) (где N — количество узлов). | B-дерево имеет высоту журнала (M * N) (где «M» — порядок дерева, а N — количество узлов). |