44 lines
3.6 KiB
Markdown
44 lines
3.6 KiB
Markdown
|
---
|
|||
|
|
aliases:
|
|||
|
|
- дерево
|
|||
|
|
tags:
|
|||
|
|
- maturity/🌱
|
|||
|
|
date: 2024-09-17
|
|||
|
|
zero-link:
|
|||
|
|
- "[[../garden/ru/meta/zero/00 Разработка|00 Разработка]]"
|
|||
|
|
parents:
|
|||
|
|
- "[[structure/Структура данных]]"
|
|||
|
|
linked:
|
|||
|
|
---
|
|||
|
|
Дерево — это иерархическая структура данных, состоящая из узлов (вершин), которые связаны друг с другом ребрами. Главные характеристики деревьев:
|
|||
|
|
- Корень: Узел, с которого начинается дерево. У него нет родительского узла.
|
|||
|
|
- Листья: Узлы, которые не имеют дочерних узлов.
|
|||
|
|
- Уровни: Глубина или высота узла относительно корня.
|
|||
|
|
- Родители и потомки: В каждом узле, кроме корня, есть родитель, и могут быть дочерние узлы (потомки).
|
|||
|
|
|
|||
|
|
Виды деревьев:
|
|||
|
|
- [[structure/Бинарное дерево поиска|Бинарное дерево]]: Каждый узел имеет не более двух потомков — левый и правый.
|
|||
|
|
- Двоичное дерево поиска (Binary Search Tree, BST): [[structure/Бинарное дерево поиска|Бинарное дерево]], в котором левый потомок содержит значения меньше родительского узла, а правый — больше.
|
|||
|
|
- AVL-дерево: [[structure/Сбалансированное дерево|Сбалансированное]] [[structure/Бинарное дерево поиска|бинарное дерево поиска]], в котором разница высот левого и правого поддерева любого узла не превышает 1.
|
|||
|
|
- Красно-черное дерево: [[structure/Бинарное дерево поиска|Бинарное дерево поиска]], которое поддерживает балансировку путём соблюдения определённых свойств цветных узлов.
|
|||
|
|
- [[structure/B-tree]] (B-дерево): Обобщение бинарного дерева для случаев, когда узлы могут иметь больше двух потомков, эффективно используемое для больших данных.
|
|||
|
|
- B+-дерево: Вариант B-дерева, в котором все ключи хранятся только в листьях, а внутренние узлы используются только для направления поиска.
|
|||
|
|
- Trie: Префиксное дерево, используемое для хранения строк, где каждый узел представляет часть строки.
|
|||
|
|
***
|
|||
|
|
## Мета информация
|
|||
|
|
**Область**:: [[../../meta/zero/00 Разработка|00 Разработка]]
|
|||
|
|
**Родитель**:: [[structure/Структура данных]]
|
|||
|
|
**Источник**::
|
|||
|
|
**Создана**:: [[2024-09-17]]
|
|||
|
|
**Автор**::
|
|||
|
|
### Дополнительные материалы
|
|||
|
|
-
|
|||
|
|
|
|||
|
|
### Дочерние заметки
|
|||
|
|
<!-- QueryToSerialize: LIST FROM [[]] WHERE contains(Родитель, this.file.link) or contains(parents, this.file.link) -->
|
|||
|
|
<!-- SerializedQuery: LIST FROM [[]] WHERE contains(Родитель, this.file.link) or contains(parents, this.file.link) -->
|
|||
|
|
- [[Бинарное дерево поиска]]
|
|||
|
|
- [[Сбалансированное дерево]]
|
|||
|
|
- [[B-tree]]
|
|||
|
|
<!-- SerializedQuery END -->
|