Skip to content

Latest commit

 

History

History
46 lines (32 loc) · 2.01 KB

Tree.md

File metadata and controls

46 lines (32 loc) · 2.01 KB

Деревья.

Дерево(tree) - набор связанных узлов.
Узел(node) - данные + ссылка на следующий узел.
Корень(root) - первый узел, без родителя.
Ребро - путь между узлами/листами.
Лист - конечный узел без последующих за ним узлов или листьев.
Внутренний узел - ветка, промежуточный узел имеющий потомков.

Дерево - рекурсивная структура.
Каждый узел содержит другие узлы, похожие на своего родителя, некий факториал.

Глубина - длинна пути от корня до узла.
Высота - самый длинный путь от узла до листа, кол-во ребер.

Двоичное дерево.

У каждого узла не более 2 потомков.

Сбалансированное двоичное дерево:
Разница высоты между правым и левым поддеревом не превышает k. [k = 1]
Не сбалансированное двоичное дерево:
Любое другое двоичное дерево.

Хранение в памяти.

@ слева <- Данные -> @ справа

[todo]

BST - Binary Search Tree.

Двоичное дерево поиска.
Слева - все узлы меньше корня.  
Справа - все узлы больше корня.  
Двоичный поиск - O(Log N)  
Добавление   -   O(Log N)  
Удаление    -    O(Log N)  

Red Black Search Tree

Самобалансирующее дерево красно-черное.

[todo]

Roman Brovko - Деревья
Stepic - Деревья