B-дерево против бинарного дерева
Содержание
- Содержание: Разница между B-деревом и Бинарным деревом
- Сравнительная таблица
- В-дерево
- Бинарное дерево
- Ключевые отличия
- Заключение
- Пояснительное видео
Различие между B-деревом и бинарным деревом состоит в том, что B-дерево - это отсортированное дерево, где узлы сортируются в порядке обхода, тогда как двоичное дерево - это упорядоченное дерево, имеющее указатель на каждый узел.
Структуры данных являются наиболее важными понятиями в компьютерном программировании, а в структурах данных двумя наиболее важными понятиями являются B-дерево и Binary tree. Оба отличаются друг от друга. B-дерево - это отсортированное дерево, где узлы сортируются в порядке обхода, тогда как двоичное дерево - это упорядоченное дерево, имеющее указатель на каждый узел. B-дерево и двоичное дерево являются нелинейными структурами данных. По названию оба термина кажутся одинаковыми, но они не одинаковы, поскольку они разные. Код двоичного дерева хранится в ОЗУ, тогда как код B-дерева хранится на диске.
B-дерево - это сбалансированное M-дерево, B-дерево известно как сбалансированное дерево сортировки. В B-дереве происходит обход по порядку. Пространственная сложность B-дерева O (n). Сложность времени вставки и удаления составляет O (log n). В B-дереве высота дерева должна быть минимально возможной. В B-дереве не должно быть пустого поддерева. Все листья дерева должны быть на одном уровне. Каждый узел может иметь максимальное число детей M и минимальное число детей M / 2. Каждый узел в B-дереве должен иметь меньше ключа, чем дочерний ключ. В B-дереве ключи в поддереве, присутствующем слева от ключа, являются предшественниками. Когда узел заполнен и вы пытаетесь вставить новый узел, дерево разделяется на две части. Вы можете объединять узлы в B-дереве, пока узлы не будут удалены.
Бинарное дерево имеет два указателя, которые содержат адрес его дочерних узлов. Существуют типы двоичных деревьев, такие как строго двоичное дерево, полное двоичное дерево, расширенное двоичное дерево и т. Д. В строго двоичном дереве должны быть левое поддерево и правое поддерево, в полном двоичном дереве должно быть два узла в на каждом уровне и в двоичном дереве с резьбой должно быть от 0 до 2 узлов. Если мы говорим о трансверсальных техниках, то три трансверсальных техники: трансверсальный порядок, трансверсальный порядок и трансверсальный порядок.
Содержание: Разница между B-деревом и Бинарным деревом
- Сравнительная таблица
- В-дерево
- Бинарное дерево
- Ключевые отличия
- Заключение
- Пояснительное видео
Сравнительная таблица
основа | В-дерево | Бинарное дерево |
основа | B-дерево - это отсортированное дерево, в котором узлы сортируются в порядке обхода. | Бинарное дерево - это упорядоченное дерево, имеющее указатель на каждый узел. |
хранить | Код B-дерева хранится на диске. | Код двоичного дерева хранится в оперативной памяти |
Высота | Высота B-дерева будет бревенчатой N | Высота бинарного дерева будет лог2 N |
заявка | СУБД является приложением B-дерева. | Кодирование Хаффмана - это приложение Binary Tree. |
В-дерево
B-дерево - это сбалансированное M-дерево, B-дерево известно как сбалансированное дерево сортировки. В B-дереве происходит обход по порядку. Пространственная сложность B-дерева O (n). Сложность времени вставки и удаления составляет O (log n). В B-дереве высота дерева должна быть минимально возможной.
В B-дереве не должно быть пустого поддерева. Все листья дерева должны быть на одном уровне. Каждый узел может иметь максимальное число детей M и минимальное число детей M / 2. Каждый узел в B-дереве должен иметь меньше ключа, чем дочерний ключ. В B-дереве ключи в поддереве, присутствующем слева от ключа, являются предшественниками. Когда узел заполнен и вы пытаетесь вставить новый узел, дерево разделяется на две части. Вы можете объединять узлы в B-дереве, пока узлы не будут удалены.
Бинарное дерево
Бинарное дерево имеет два указателя, которые содержат адрес его дочерних узлов. Существуют типы двоичных деревьев, такие как строго двоичное дерево, полное двоичное дерево, расширенное двоичное дерево и т. Д.
В строго двоичном дереве должны быть левое поддерево и правое поддерево, в полном двоичном дереве должно быть два узла на каждом уровне, а в многопоточном двоичном дереве должно быть от 0 до 2 узлов. Если мы говорим о трансверсальных техниках, то есть три трансверсальные техники: трансверсальный порядок, трансверсальный порядок и трансверсальный порядок.
Ключевые отличия
- B-дерево - это отсортированное дерево, в котором узлы сортируются в порядке обхода, в то время как двоичное дерево - это упорядоченное дерево, имеющее указатель на каждый узел.
- Код B-дерева хранится на диске, тогда как код Binary Tree хранится в оперативной памяти.
- Высота B-дерева будет logN, тогда как высота бинарного дерева будет log2 N
- СУБД - это приложение B-дерева, тогда как кодирование Хаффмана - это приложение Binary Tree.
Заключение
В этой статье выше мы видим четкую разницу между B-деревом и Binary деревом с их реализацией.