Вам бонус- начислено 1 монета за дневную активность. Сейчас у вас 1 монета

Двоичное дерево определение и применение кратко

Лекция



Привет, сегодня поговорим про двоичное дерево, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое двоичное дерево , настоятельно рекомендую прочитать все из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика..

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

Для практических целей обычно используют два подвида бинарных деревьев — двоичное дерево поиска и двоичная куча.

Рекурсивное определение

Существует следующее рекурсивное определение двоичного дерева (см. БНФ):

<дерево> ::= ( <данные> <дерево> <дерево> ) | nil .

То есть двоичное дерево либо является пустым, либо состоит из данных и двух поддеревьев (каждое из которых может быть пустым). Об этом говорит сайт https://intellect.icu . Очевидным, но важным для понимания фактом является то, что каждое поддерево в свою очередь тоже является деревом. Если у некоторого узла оба поддерева пустые, то он называется листовым узлом (листовой вершиной) или терминальным элементом.

Например, показанное справа на рис. 1 дерево, согласно этой грамматике можно было бы записать так:

 (m 
    (e 
        (c 
            (a nil nil)
            nil
        )
        (g 
            nil
            (k nil nil)
        )
     )
     (s
        (p (o nil nil) (s nil nil) )
        (y nil nil)
     )
 )
Двоичное дерево определение и применение

Рис. 1. Двоичное дерево поиска, в котором ключами являются латинские символы упорядоченные по алфавиту.

Каждый узел в дереве задает поддерево, корнем которого он является. У вершины m=(data, left, right) есть два потомка (левый и правый) left и right и, соответственно, два поддерева (левое и правое) с корнями left и right.

Применение

Многие полезные структуры данных основаны на двоичном дереве:

  • Двоичное дерево поиска
  • Двоичная куча
  • АВЛ-дерево
  • Красно-черное дерево
  • Матричное дерево
  • Дерево Фибоначчи
  • Суффиксное дерево

Надеюсь, эта статья про двоичное дерево, была вам полезна, счастья и удачи в ваших начинаниях! Надеюсь, что теперь ты понял что такое двоичное дерево и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика.

Из статьи мы узнали кратко, но содержательно про двоичное дерево
создано: 2015-01-06
обновлено: 2021-03-13
132734



Рейтиг 9 of 10. count vote: 2
Вы довольны ?:


Найди готовое или заработай

С нашими удобными сервисами без комиссии*

Как это работает? | Узнать цену?

Найти исполнителя
$0 / весь год.
  • У вас есть задание, но нет времени его делать
  • Вы хотите найти профессионала для выплнения задания
  • Возможно примерение функции гаранта на сделку
  • Приорететная поддержка
  • идеально подходит для студентов, у которых нет времени для решения заданий
Готовое решение
$0 / весь год.
  • Вы можите продать(исполнителем) или купить(заказчиком) готовое решение
  • Вам предоставят готовое решение
  • Будет предоставлено в минимальные сроки т.к. задание уже готовое
  • Вы получите базовую гарантию 8 дней
  • Вы можете заработать на материалах
  • подходит как для студентов так и для преподавателей
Я исполнитель
$0 / весь год.
  • Вы профессионал своего дела
  • У вас есть опыт и желание зарабатывать
  • Вы хотите помочь в решении задач или написании работ
  • Возможно примерение функции гаранта на сделку
  • подходит для опытных студентов так и для преподавателей



Комментарии


Оставить комментарий
Если у вас есть какое-либо предложение, идея, благодарность или комментарий, не стесняйтесь писать. Мы очень ценим отзывы и рады услышать ваше мнение.
To reply

Дискретная математика. Теория множеств . Теория графов . Комбинаторика.

Термины: Дискретная математика. Теория множеств . Теория графов . Комбинаторика.