Каталог курсов
Николай Разилов — новый член команды KursHub.ru

Николай Разилов — новый член команды KursHub.ru

В команде агрегатора онлайн курсов появился новый участник — Николай Разилов.

Краткая выжимка о Николае Разилове:

Senior разработчик. Программирует с 2012 года.
Основные языки и направления: C# .NET, Python, Java и разработка под Android.
Имеет свой блог razilov-code.ru, пишет заметки с решениями различных проблем.
Образование: Высшее.
Возраст: 42 года.
Опыт работы: работал в Rambler, Яндекс и EPAM.

Список направлений, которые будет развивать Николай на KursHub

Не так давно в своем блоге Николай делился последней информацией.

Бинарное дерево — двоичное дерево поиска. Основные операции с бинарными деревьями (C#, Java).

Что такое бинарное дерево

Бинарное дерево представляет собой иерархическую структуру данных, в которой каждый узел имеет не более двух дочерних узлов. Как правило, первый называется родительским узлом или корнем дерева (root), а дочерние узлы называются левым и правым наследниками.

Бинарное дерево либо является пустым, либо состоит из данных и двух поддеревьев, каждое из которых может быть пустым. Каждое поддерево в свою очередь тоже является деревом. Узлы без наследников принято называть листьями.

Для такого дерева должны выполняться следующие условия:

Левое и правое поддерево так же являются бинарными деревьями;
У всех узлов левого поддерева произвольного узла $x$ значения ключей данных меньше значения ключа данных самого узла $x$ ;
У всех узлов правого поддерева произвольного узла $x$ значения ключей данных больше либо равны значению ключа данных самого узла $x$ .

Основные операции с бинарным деревом

Основными операциями с бинарными деревьями являются добавление элемента в дерево, удаление элемента и поиск элемента в дереве. Сложность каждой из этих операций $O (l o g n)$ в лучшем случае, и $O (n)$ в худшем. Зависит от сбалансированности дерева. Пример сбалансированного бинарного дерева (лучший случай):

Пример несбалансированного бинарного дерева (худший случай):

Добавление элемента в дерево

При добавлении элемента $x$ в дерево проверяем значение текущего узла.

Если значение добавляемого элемента $x$ меньше значения текущего узла, спускаемся к левому поддереву. Если его не существует, то создаем его и присваиваем значение $x$ . Если существует, то обозначим левое поддерево как текущий узел и повторим сначала.
Если значение добавляемого элемента $x$ больше или равно значению текущего узла, спускаемся к правому поддереву. Если его не существует, то создаем его и присваиваем значение $x$ . Если существует, то обозначим правое поддерево как текущий узел и повторим сначала.

Пример добавления элемента в двоичное дерево

Создадим бинарное дерево с корневым элементом 33 и добавим в него элементы в следующей последовательности: 5, 35, 1, 20, 99, 17, 18, 19, 31, 4. Получим бинарное дерево такого вида…. Продолжение читайте в его блоге razilov-code.ru.

Мы очень рады сотрудничеству с Николаем и желаем ему успехов в личностном развитии и развитии нашего проекта!

Если хотите написать сообщение нашему новому члену команды, пишите на адрес admin@kurshub.ru с пометкой «Для Николая Разилова».

Смотрите так же: