вот бы сделать отдельный стрим по дереву с подробным объяснением , было бы очень полезно начинающим, и еще я бы хотел разобраться как балансировку делать)))Спасибо большое за труды, Сергей))
спасибо , стало понятно ! смотрел обход дерева на другом канале , там не уточняли , что бинарное дерево заполняется по правилам, было не понятно для чего оно вообще нужно !
Вы ошиблись по поводу словоря в c#. У него под капотом не дерево, а хэш таблица и доступ по ключу у хэш таблицы всегда o(1). А у бинарного дерева в среднем о(lgn) и в худщем o(N), если мы почитаем документацию по словарю увидим, что чтение из словаря в c# занимает o(1)
Эх, помню писал бинарный поиск. Хорошая практика! public int BinarySearch(int[] arr, int _item) { int _low = 0; //первый элемент массива для пойска int _high = arr.Length - 1; //последний элемент массива для пойска while (_low _item) // если много { _high = _mid - 1; // идем к найменьшему элементу } else // если мало { _low = _mid + 1; // идем к найбольшему элементу } } return 0; // если элемент не найдент, то возвращаем 0 }
Удаление узла из бинарного дерева поиска. Не благодарите Нерекурсивная реализация Для удаления узла из бинарного дерева поиска нужно рассмотреть три возможные ситуации. Если у узла нет дочерних узлов, то у его родителя нужно просто заменить указатель на null. Если у узла есть только один дочерний узел, то нужно создать новую связь между родителем удаляемого узла и его дочерним узлом. Наконец, если у узла два дочерних узла, то нужно найти следующий за ним элемент (у этого элемента не будет левого потомка), его правого потомка подвесить на место найденного элемента, а удаляемый узел заменить найденным узлом. Таким образом, свойство бинарного дерева поиска не будет нарушено. Данная реализация удаления не увеличивает высоту дерева. Рекурсивная реализация При рекурсивном удалении узла из бинарного дерева нужно рассмотреть три случая: удаляемый элемент находится в левом поддереве текущего поддерева, удаляемый элемент находится в правом поддереве или удаляемый элемент находится в корне. В двух первых случаях нужно рекурсивно удалить элемент из нужного поддерева. Если удаляемый элемент находится в корне текущего поддерева и имеет два дочерних узла, то нужно заменить его минимальным элементом из правого поддерева и рекурсивно удалить этот минимальный элемент из правого поддерева. Иначе, если удаляемый элемент имеет один дочерний узел, нужно заменить его потомком
6:23 На самом деле очень даже можем . если создадим в двусвязном списке ссылку на средний элемент тогда то сможем отталкиваться от него и двигаться либо в сторону начала , или в сторону конца(как вариант))
7:00 вот тут было бы неплохо, может быть, забежать вперед и рассказать, как в такое дерево добавлялось бы, например, число 2. Когда есть узел со значением 1 и из него уже выходит дочерний узел со значением 30. Это можно сделать, не переписывая дерево?
А что если на вход подается ряд значений, уже отсортированный по возрастанию/убыванию, все элементы будут уходить каждый раз в правую/левую ветку? Как тогда быть с идеально сбалансированными бинарными деревьями?
Сижу я такой смотрю про двусвязные списки и димаю , а почему бы не организовать структуру .. ( и такой в голове придумываю нечто похожее на бинарное дерево) . Открываю следующее видео и .. а ну да , точно)) Кстати эти все структуры данных описаны в книге Дональда Кнута 1 том, но как хорошо описаны я не знаю так как без математической подготовки я просто пока - что открываю книгу и просто нюхаю))) Но там описание не привязано к конкретному языку программирования , так что очень полезно
Доброго времени суток! Спасибо за качественные уроки! В одном из первых ваших видео Вы говорили, что также планируете делать уроки по C#. Хотелось бы узнать когда их ждать?
6:15 >> Поиск по индексу будет проходить очень медленно, и нам никак не обойти ... Можно обойти - нужно хранить в узле дерева количество всех дочерних узлов.
Для того, чтобы формально была понятна разница м/у связанными списками и бин. деревьями надо бы указывать сложности для тех и других. А так, это "лучше и быстрее" плохо осязаемо же.
Насколько я понял по механике бинарного дерева, оно просто не может быть неупорядоченным, т.к. упорядочение происходит прямо в процессе создания бинарного дерева
@@Dungeon_masster228 Бинарное дерево может быть не упорядоченным. Более того, в дереве могут быть не только числа, но и объекты любого типа. Главное условие бинарного дерева - каждый узел содержит не более двух потомков. Не более. А упорядочивание, балансирование(см. красно-черные деревья) это разновидность обычного бинарного дерева
смотри, ты можешь делать его неупорядоченным, если будешь рандомно класть элементы в дерево, но если ты создашь какой либо принцип вставки элемента в дерево(ну в основном как в видео), то ты сможешь быстро складывать элементы в дерево и быстро вынимать, что по должно быть само собой разумеющееся , иначе это трата ресурсов (ну рандомно кидать элементы) , которое ни к чему не приводит( брать элементы хз как)
public class BinaryTree { public int Value; public BinaryTree Left; public BinaryTree Right; public BinaryTree(int value) { Value = value; } public void Add(int value) { if (value < Value) { if (Left == null) Left = new BinaryTree(value); else Left.Add(value); } else { if (Right == null) Right = new BinaryTree(value); else Right.Add(value); } } } // Как-то так, дальше сам додумывай
Вопрос: на работе программисту обязательно знать наизусть что и как писать код , чтобы решить ту или иную задачу ? Ну допустим он понимает как это работает и у него есть под рукой готовый для решения данной задачи код ... его же работодатель за это никак занижать не будет ?
GameStudio Вы искренно верите, что работодатель будет ковыряются в вашем коде? ))) А в общем, для этого и существуют либы, паттерны, ну и копипаст ). Просто без понимания вы не сможете их применить и будете изобретать велосипед. А изобретательство велосипедов оно такое. Часто даже затягивает, как правило во вред результату. )
было бы хорошо если б вы привели пример ипользования бинарного дерева, так как к примеру если добавлять данные по мере роста или убыванию их значения, тогда получится тот же односвязный список
Все правильно. И скорость поиска в таком случае будет одинаковая (по сравнению с односвязанным списком). К сожалению не раскрыта тема балансировки и удаления.
В таком случае можно сделать счетчик повторяющихся элементов, но вообще со стандартной реализацией повторяющиеся элементы в большинстве случаев будут попадать правее от себе подобного числа (но в теории могут быть и под ними, то есть изначально зайти в правую ветку от него, но потом свернуть влево), которое добавлялось раньше
@@KiberDoktoR а что на счет добавления в места, которые уже заняты (к примеру, если попробовать добавить число 52 на моменте 7:25 , то что-то не складывается)
@@Mike-hp3fh в плюсах бинарный поиск - это функция работающая с итераторами, ей все равно за сколько есть возможность получить Эл-т, если она есть. Другое дело если мы говорим о её скорости работы. Но факт есть факт и бин поиск на листе запустить можно.
![[LIVE] : ONE ลุมพินี 89 | คู่เอก "ยอดไอคิว vs คิริลล์"](http://i.ytimg.com/vi/Z3vYkHJ_5Ig/mqdefault.jpg)
![[ ออกกอง ] วัยหนุ่ม 2544 โลกหลังลูกกรง..ทัวร์กองถ่ายหนังใน "คุกของจริง" | JUSTดูIT.](http://i.ytimg.com/vi/vB--aOkZCpw/mqdefault.jpg)
*Cамый лучший способ сказать "спасибо" - поставить лайк и и поделиться уроком с друзьями. Это очень мотивирует создавать полезные уроки =)*
Ждем программной реализации)
Спасибо большое за такие уроки!
Какие минусы бинарного дерева?
Читал несколько методических пособий, но смысл и преимущества бинарного дерева дошли до меня только после просмотра данного видеоурока. Спасибо!
Единственный канал где понятно объясняется программирование
вот бы сделать отдельный стрим по дереву с подробным объяснением , было бы очень полезно начинающим, и еще я бы хотел разобраться как балансировку делать)))Спасибо большое за труды, Сергей))
Большое спасибо за Ваш труд! Вы делаете нас умнее)
Огромное спасибо от моей нервной системы за наглядную визуализацию проговариваемых слов в фотошопе. Все три видео на одном дыхании
Спасибо большое!!! Сейчас я на курсах в школе программирования и как раз тема бинарных деревьев! Ваше видео поможет!
Большое спасибо за ваш труд! Очень нужно реализация бинарного дерева в вашем исполнении!
Большое спасибо.
Очень наглядно просто и понятно объяснили!
Красавчик :3
Как легко и понятно объясняешь
До этого я и не знал зачем нужны бинарные деревья спасибо, что пояснил!
Очень понятное объяснение, спасибо, респект автору🎉
Очень хорошо объяснено. Спасибо большое!
Кому интересно, вот реализация бинарного дерева
#include
#include
using namespace std;
struct Tree
{
Tree *left;
Tree *right;
int num;
Tree(int n = 0, Tree* l = nullptr, Tree* r = nullptr) :num(n), left(l), right(r) {} // Конструктор принимает данные, и указатель на левый и правый элемент, по умолчанию инициализируя их нулями. Далее конструктор передает эти значения дальше через двоеточие
};
class BTree
{
Tree *root;
public:
BTree() {
root = nullptr;
}
~BTree()
{
Tree *temp = root;
int rootValue = root->num;
Tree *previous = root;
while (temp != nullptr && rootValue == temp->num ) {
if (root->left==nullptr && root->right==nullptr)
{
if (previous->left != nullptr && previous->left->num == root->num)
{
previous->left = nullptr;
}
else if (previous->right !=nullptr && previous->right->num == root->num)
{
previous->right = nullptr;
}
delete root;
root = temp;
}
else if (root->left != nullptr && root->left->num < root->num)
{
previous = root;
root = root->left;
}
else
{
previous = root;
root = root->right;
}}}
void add(Tree *&t, int n) {
if (t == nullptr) {
t = new Tree(n);
}
else {
if (n < t->num) {
//cout left, n);
}
else {
add(t->right, n);
//cout left);
cout num right);
}
//else cout
Скажи что делает функция inorder?
Подтолкнул на правильную мысль. Реализовал чуть иначе, но принцип тот же. Спасибо
Сергей !!! спасибо за видео !!! У Вас талант -- объяснять не необъяснимые вещи !!!!!
Просто максимально полезный поток информации))
Спасибо!! Однозначно лайк, подписка!)
спасибо , стало понятно ! смотрел обход дерева на другом канале , там не уточняли , что бинарное дерево заполняется по правилам, было не понятно для чего оно вообще нужно !
Коротко и ёмко! Пока пил кофе, разобрался в том, что другие по часу жуют в своих видео и не могут донести
Прекрасное изложение материала. Спасибо!
#бинарноедерево #динамическиеструктурыданных #SimpleCode #урокипрограммирования
Спасибо за урок.
Очень крутые и полезные видео, спасибо!
Вы ошиблись по поводу словоря в c#. У него под капотом не дерево, а хэш таблица и доступ по ключу у хэш таблицы всегда o(1). А у бинарного дерева в среднем о(lgn) и в худщем o(N), если мы почитаем документацию по словарю увидим, что чтение из словаря в c# занимает o(1)
Топ! выучил плюса на ютубе! ты бог
Еще б немного математики сюда)
Расчет сложности поиска элемента например…
Где-нибудь в конце, чтоб не пугать большинство)
Спасибо, очень доступно объясняете
Спасибо за вашу работу!!)
Спасибо за урок!
Эх, помню писал бинарный поиск. Хорошая практика!
public int BinarySearch(int[] arr, int _item)
{
int _low = 0; //первый элемент массива для пойска
int _high = arr.Length - 1; //последний элемент массива для пойска
while (_low _item) // если много
{
_high = _mid - 1; // идем к найменьшему элементу
}
else // если мало
{
_low = _mid + 1; // идем к найбольшему элементу
}
}
return 0; // если элемент не найдент, то возвращаем 0
}
Большое спасибо за урок, вот бы еще реализацию увидеть)))
В фотошопе 😀
Очень подробно и доходчиво, спасибо!
Отличное объяснение. Спасибо.
Отличное видео , именно у вас всегда всё понятно. Очень жаль что видео больше не появляются,я бы поддержал канал финансово если б мог (
Удаление узла из бинарного дерева поиска. Не благодарите
Нерекурсивная реализация
Для удаления узла из бинарного дерева поиска нужно рассмотреть три возможные ситуации. Если у узла нет дочерних узлов, то у его родителя нужно просто заменить указатель на null. Если у узла есть только один дочерний узел, то нужно создать новую связь между родителем удаляемого узла и его дочерним узлом. Наконец, если у узла два дочерних узла, то нужно найти следующий за ним элемент (у этого элемента не будет левого потомка), его правого потомка подвесить на место найденного элемента, а удаляемый узел заменить найденным узлом. Таким образом, свойство бинарного дерева поиска не будет нарушено. Данная реализация удаления не увеличивает высоту дерева.
Рекурсивная реализация
При рекурсивном удалении узла из бинарного дерева нужно рассмотреть три случая: удаляемый элемент находится в левом поддереве текущего поддерева, удаляемый элемент находится в правом поддереве или удаляемый элемент находится в корне. В двух первых случаях нужно рекурсивно удалить элемент из нужного поддерева. Если удаляемый элемент находится в корне текущего поддерева и имеет два дочерних узла, то нужно заменить его минимальным элементом из правого поддерева и рекурсивно удалить этот минимальный элемент из правого поддерева. Иначе, если удаляемый элемент имеет один дочерний узел, нужно заменить его потомком
Это самая интересная часть)
Спасибо за урок
Настолько подробно объяснил , что мне аж интересно стало откуда ты брал инфу били же сам составлял текст для объяснений ?
Очень круто!
6:23 На самом деле очень даже можем . если создадим в двусвязном списке ссылку на средний элемент тогда то сможем отталкиваться от него и двигаться либо в сторону начала , или в сторону конца(как вариант))
можно еще , используя размер и индекс .
Спасибо большое!
Cпасибо!
Просто и понятно😄
Огромное спасибо!
спасибо!
Благодарю!
7:00 вот тут было бы неплохо, может быть, забежать вперед и рассказать, как в такое дерево добавлялось бы, например, число 2. Когда есть узел со значением 1 и из него уже выходит дочерний узел со значением 30. Это можно сделать, не переписывая дерево?
так двойка просто запишется с левой части от 30
bratan ogromnoe spasibo ))
огрооооомное спасибо
Спасибо.
А что если на вход подается ряд значений, уже отсортированный по возрастанию/убыванию, все элементы будут уходить каждый раз в правую/левую ветку? Как тогда быть с идеально сбалансированными бинарными деревьями?
Можно сделать проверку на количество символов, разделить на 2 и брать корнем элемент под данным индексом
Сижу я такой смотрю про двусвязные списки и димаю , а почему бы не организовать структуру .. ( и такой в голове придумываю нечто похожее на бинарное дерево) . Открываю следующее видео и .. а ну да , точно)) Кстати эти все структуры данных описаны в книге Дональда Кнута 1 том, но как хорошо описаны я не знаю так как без математической подготовки я просто пока - что открываю книгу и просто нюхаю))) Но там описание не привязано к конкретному языку программирования , так что очень полезно
Доброго времени суток! Спасибо за качественные уроки! В одном из первых ваших видео Вы говорили, что также планируете делать уроки по C#. Хотелось бы узнать когда их ждать?
Пора
рора
Бро, 3 года начались уроки по c#, бужу тебя, вдруг ты пропустил
крутая вещь, это бинарное дерево
Еще круто что слева находиться минимальное число, а справа максимальное
6:15 >> Поиск по индексу будет проходить очень медленно, и нам никак не обойти ...
Можно обойти - нужно хранить в узле дерева количество всех дочерних узлов.
Спасибо !
Для того, чтобы формально была понятна разница м/у связанными списками и бин. деревьями надо бы указывать сложности для тех и других. А так, это "лучше и быстрее" плохо осязаемо же.
Все и так понятно..
Продвигаем в топы
Спасибо :)
великолепно!
Спасибо
Продолжайте C++ и его теорию
Разве мапы и ассоциативные массивы не используют хэш-таблицы и хэш-сеты?
Нужно уточнение, что это бинарное дерево поиска :D
Это вы объясняете про бинарное дерево поиска, в просто бинарном дереве данные не упорядочены
Это точно так? Уверены?
Насколько я понял по механике бинарного дерева, оно просто не может быть неупорядоченным, т.к. упорядочение происходит прямо в процессе создания бинарного дерева
@@Dungeon_masster228 Бинарное дерево может быть не упорядоченным. Более того, в дереве могут быть не только числа, но и объекты любого типа.
Главное условие бинарного дерева - каждый узел содержит не более двух потомков. Не более. А упорядочивание, балансирование(см. красно-черные деревья) это разновидность обычного бинарного дерева
@@bogotoff Тимур прав
смотри, ты можешь делать его неупорядоченным, если будешь рандомно класть элементы в дерево, но если ты создашь какой либо принцип вставки элемента в дерево(ну в основном как в видео), то ты сможешь быстро складывать элементы в дерево и быстро вынимать, что по должно быть само собой разумеющееся , иначе это трата ресурсов (ну рандомно кидать элементы) , которое ни к чему не приводит( брать элементы хз как)
Спасибо)
Спасибо, а будет урок по реализации дерева?)
public class BinaryTree
{
public int Value;
public BinaryTree Left;
public BinaryTree Right;
public BinaryTree(int value)
{
Value = value;
}
public void Add(int value)
{
if (value < Value)
{
if (Left == null)
Left = new BinaryTree(value);
else Left.Add(value);
}
else
{
if (Right == null)
Right = new BinaryTree(value);
else Right.Add(value);
}
}
}
// Как-то так, дальше сам додумывай
@@mishalavik4595 Спасибо!!!))
Вроде же рассказали
@@mishalavik4595 Рекурсивная реализация?
Сергей, спасибо за урок! Есть в планах делать уроки по формам и оконным приложениям в Visual Studio?
есть winforms и wpf
Winforms)
Сделайте такое же видео по "Би-дерево".
это конечно замечательно, но жаль не рассказано как добавлять, если это какое то промежуточное значение (47 например)
оно будет с правой стороны 46, нет никаких промежуточных значений
СПАСИБО)) Можно реализацию на с++?
крутое видео
А как происходит построение дерева?
Вопрос: на работе программисту обязательно знать наизусть что и как писать код , чтобы решить ту или иную задачу ? Ну допустим он понимает как это работает и у него есть под рукой готовый для решения данной задачи код ... его же работодатель за это никак занижать не будет ?
GameStudio Вы искренно верите, что работодатель будет ковыряются в вашем коде? ))) А в общем, для этого и существуют либы, паттерны, ну и копипаст ). Просто без понимания вы не сможете их применить и будете изобретать велосипед. А изобретательство велосипедов оно такое. Часто даже затягивает, как правило во вред результату. )
Здравствуйте а для python бинарное дерево также создается?
А можно реализацию на c#?
было бы хорошо если б вы привели пример ипользования бинарного дерева, так как к примеру если добавлять данные по мере роста или убыванию их значения, тогда получится тот же односвязный список
Примет скоро будет в уроках по STL.
Все правильно. И скорость поиска в таком случае будет одинаковая (по сравнению с односвязанным списком). К сожалению не раскрыта тема балансировки и удаления.
чел помог
Дикшенери в шарпе - не дерево, а хэш таблица, если не ошибаюсью
угу
Верно.
Какие минусы бинарного дерева?
для чего оно нужно?
Что делать если список начинается с единицы ?
А как быть с удалением данных из дерева? Надеюсь будет дополнение к видео
Дерево будет сортироваться заново
А как происходит удаление элементов?
Спасибо за урок! Но есть вопрос) А как дерево поведет себя при вставке одинаковых чисел (дубликатов)?
В таком случае можно сделать счетчик повторяющихся элементов, но вообще со стандартной реализацией повторяющиеся элементы в большинстве случаев будут попадать правее от себе подобного числа (но в теории могут быть и под ними, то есть изначально зайти в правую ветку от него, но потом свернуть влево), которое добавлялось раньше
Понятное о непонятном.
А если в примере к головному числу 50 добавить 50, то что??
Зависит от реализации. В эталоне - элемент не вставляется как в множестве (сете).
Либо вставляется слева как в мультисете.
@@KiberDoktoR а что на счет добавления в места, которые уже заняты (к примеру, если попробовать добавить число 52 на моменте 7:25 , то что-то не складывается)
9:33 Бинарный поиск в связном списке? Это возможно?
Это возможно в любой отсортированной коллекции.
@@aznaurataev9497 только если возможно получить элемент по индексу за время O(1)
@@Mike-hp3fh в плюсах бинарный поиск - это функция работающая с итераторами, ей все равно за сколько есть возможность получить Эл-т, если она есть. Другое дело если мы говорим о её скорости работы. Но факт есть факт и бин поиск на листе запустить можно.
Like!
Т.е. это аналогия дерева решений в машинном обучении.
Жаль ничего не сказано о ситуации, когда место для значения, которое хотелось бы хранить в дереве - занято
у меня вопрос : мы же можем под 49 слева указать 30 также
нет не можем 30 меньше 45
Привет от учеников 21й школы !
А почему 50
Ничего не сказано о минусах. Вначале заявили, а потом ничего не сказали.
и когда юзать бинарное дерево, а когда список?
а если добавить номер 50, к примеру, с которого уже началось дерево?... а с удалением как дела обстоят?
Сам думал на эту тему. Оказалось просто, при реализации дерева можно прописывать условия типа >= или = число 50 попадет вправо, а если
@@axentfly8945 я видал делали так:
< в левую часть
> в правую часть
== игнорировали число
11:05
А если в корне - 50, а оба последующих числа - меньше 50ти?
Будет перекос в одну сторону
А если число повторяется?
В бинарном дереве все числа-ключи уникальны
який же кайф коли музики на фоні нема, не відволікає увагу, дякую!