Реализуем бинарное дерево на JavaScript; обход в глубину и в ширину
Вставка
- Опубліковано 16 тра 2024
- Вместе разберём понятие бинарного дерева, создадим класс на JavaScript, добавим метод добавления элементов, обход в глубину (pre + in + post order) и обход в ширину.
🍀 Поддержать канал: www.donationalerts.com/r/webe...
☕️ Купить кофе: buy.stripe.com/5kA7sL9574SG7x...
🎨 Купить набор кистей Procreate: webelart.com/illustration.
✍️ Мой telegram channel: t.me/webelart
🏰 Английский UA-cam: @webelart_en
💁🏼♀️ Инстаграм: / webelart
🦄 LinkedIn: / webelart
Рекомендую посмотреть:
--------------------------------------------
Рекурсия в JavaScript: • Рекурсия и стек в Java...
Стек и очередь в JavaScript: • Учимся использовать ст...
20 методов массивов, которые нужно знать: • 20 методов массивов в ...
Рекомендую почитать:
---------------------------------------
towardsdatascience.com/4-type...
blog.benoitvallon.com/data-str...
00:00 введение.
01:00 что такое бинарное дерево.
02:10 class Node
03:43 бинарное дерево в js
05:10 class BinaryTree
06:12 реализуем метод добавления узла
14:59 определения обхода дерева
16:49 методы обхода дерева в глубину
18:44 реализуем методы preOrder, inOrder и postOrder
35:38 реализуем обход дерева в ширину
На канале я рассматриваю различные темы веб-разработки, на текущий момент: веб-основы, веб-анимации, веб-дизайн.
Ребята, добавлю сюда опечатки монтажа, т.к. видео не хочется перезаливать из-за полученных просмотров:
1. На 15-21 минуте я руками показываю depth first search и breadth first search, текст перепутан местами.
2. В видео я не учла рефлект камеры: показываю лево, при этом руками уводя направо. Эту особенность я учла только в самом начале видео. При объяснении кода - не учла.
Большое спасибо за прекрасную подачу материала!
Спасибо за такое простое и понятное объяснение! Лучшие уроки в сети!!!
Здравствуйте Елена. очень полезный видеоурок. Ясно объяснения, позитивна подход к урока.
Наверное, это лучший разбор бинарных деревьев, который видел! Хоть и с джавой не особо дружу, но почти все было понятно, интересная подача, Спасибо!
спасибо! очень доходчиво изложено.
Вот то что давно искал. спасибо!
Огромное спасибо! Качественно и полезно)
спасибо за уроки, классно!!!!
Спасибо Елена!
Круто!!! Спасибо большое!!!
Отличное видео! Благодаря ему наткнулся на канал 👍🏼
Отличный канал, спасибо за видео
Большое спасибо за видео! Действительно очень доходчиво объяснили.
Хотелось бы продолжения!
В частности, интересуют такие вопросы:
- применение алгоритмов и структур данных в вашей практике. В решении каких задач они помогли сделать код производительнее или понятнее? Живые случаи сами собой иллюстрируют актуальность. А то задумается какой-нибудь неуч вроде меня на тему: "ну и зачем мне это дерево, если есть массивы с функциями сортировки и поиска? Для чего нужны стек и очередь, если их опять же, можно реализовать через массив? На каких объемах данных O(n) начинает значительно отличаться от O(log n)?".
- Я так до конца и не понял для чего нужны разные методы обхода в глубину. Из других источников узнал, что inOrder вернет элементы в порядке возрастания. А остальные?
- Очень надеюсь однажды найти настолько же понятное объяснение тем, связанных с балансировкой дерева (сама балансировка. правые и левые повороты и т.д), а так же тонкости перестройки дерева при удалении узлов.
- Хотелось бы посмотреть настолько же качественное видео о кучах.
для идеала не хватило графики-дерева с первой минуты - для визуализации перехода по узлам при последующем объяснении. А вообще круто, недавно открыл этот канал для себя, чему очень рад, спасибо ))
Привет, очень хороший стиль подачи.
Первый раз за 7 месяцев изучения Front end искусства решил подобраться к бинарным деревья, пожалуй начну с вашего формата знакомство с этой преисподнией.
Всё супер супер супер круто😀😀
Спасибо огромное , смог написать лабу только по одному твоему видео, помимо хорошей оценки и знания про бинарное дерево будут :)
❤️
очень крутое видео спасибо
Спасибо!
Найс! Коммент в помощь продвижению 😍
Ого!!! Виктор, спасибо!! 😍
Умничка, еще бы удаление ноды рассказать :) Ждём еще видосов по структурам данных
Розумна та вродлива ,найкраща в ютубi
просто не смог не поставить лайк. Видео супер 👍👍👍. Но есть вопрос - для того чтобы найти нужное значение нужно просто ориентироваться из условия больше/меньше и спускаться по ветке вглубь пока не дойдем но нужного значения - типа метода get?
Спасибо! ❤️ Да, спускаться по веткам, в бинарном дереве все значения упорядочены и правильно разложены, поэтому поиск здесь бинарный и очень быстрый.
👏
То что надо
Отлично! 🔥
Такой к Вам вопрос, могли бы вы порекомендовать какую то литературу по JS, каких нибудь хороших авторов, по которым можно с нуля подтянуть все до уровня хотя бы джуна и получения навыков реальной работы, какие есть варианты?
Мне больше всего нравился learn.javascript.ru Лучший учебник. Там же можно либо читать на сайте либо купить 3 книги.
Елена! спасибо большое за видео! Материал для меня оказался непростым, просто повторяла в VC. Как работали в Sources тоже не совсем понятно для меня. Возможно у Вас уже есть видео как работать с DevTools, надо глянуть. Если нет, то может будет актуально. В любом случае, огромное спасибо за видео, буду повторять пока не пойму.
Здравствуйте, Светлана. Нет, по dev tools нет пока видео. Что конкретно хотелось бы по ним узнать?
@@webelart Елена, спасибо, что ответили. Хотелось бы узнать процесс использования, как дебажить код. Может быть какой-то интересный пример VS Code. Может быть пример из жизни, если Вы работали со старым кодом, legacy Ваш опыт, чем Вам помогал Dev Tools. Может просто обзор этого инструмента, фишки какие-то. Вы часто работаете и применяете console.log - в каких случаях и в какие куски кода вставлять, а потом проверяете баг, как отслеживаете ошибки по строчкам. Простите, если плохо донесла мысль. Сейчас каждый день смотрю Ваши видео и повторяю за Вами🙌
Небольшая поправочка: в бинарном дереве условие "потомок слева меньше, чем потомок справа" не обязательно. Это требования для бинарного дерева поиска (binary search tree), подвид, получается.
т.е. может быть и наоборот? Не встречала кстати на оборот. Можете ссылку на документацию или источник скинуть?
@@webelart источник... Да любой по структурам данных, наверное. Тот же "Структуры данных и алгоритмы Java" Лафоре, там им глава посвящена. И там в качестве примера рассматривается именно BST, все оговорки и пояснения даны.
Суть в том, что BST упрощает работу с коллекцией данных, если нужно часто именно искать элементы, как раз за счёт логарифмической сложности. Поэтому ставится такое дополнительное условие. Сравнили значение корня с тем, что ищем. Если искомое больше, отбросили, условно, половину дерева (всю левую часть), и так далее. Правда, нюанс - такое дерево должно быть сбалансированным. А если напихивать в него значения строго в порядке возрастания (или убывания), то такое дерево фактически выродится в связный список, с линейной сложностью поиска.
@@dimeliora обычно для работы с бинарными деревьями здорово предусматривать методы, в том числе и по балансировке.
Спасибо, что поделились, интересно!
@@webelart да, есть самобалансирующиеся деревья (AVL). Как один из вариантов - Red-Black Tree, вот посмотреть на его реализацию действительно интересно)
Вам спасибо 🙏
Мужика тебе надо конечно...
Предложение руки и сердца? 😁я вам по чесноку скажу, код и программирование куда стабильнее и надёжнее, любого мужика! 🤪
@@webelart а пошли в дискорде поболтаем
Доброго времени суток! Объясните кто-нибудь, пожалуйста, зачем тут используется return без значения ?
Напишите, какая минута видео. Я тогда смогу точно понять о каком return идёт речь. Сейчас напишу ответ относительно 11:38 минуты, где в if есть return. Я использую такую технику, чтобы не писать else. Т.е. по факту если нет this.root, то нам нужно его присвоить и больше ничего делать в этой функции не нужно, поэтому выходим. Можно писать else, но тогда будет нагромождение скобочек.
@@webelart if(...) return .... еще короче, слишком много лишних символов.
@@vadimburavlev4773 Кошмар, как жить с символами теперь...
Пришел сюда, чтобы войти сеньором в МЯСО (русский FAANG), и не пожалел)
Еще раз хочу поблагодарить за видео. Именно с него началось мое изучение структур данных сложнее массива.
Хочу, в свою очередь, поделиться другим способом организации хранения бинарного дерева.
В видео представлен подход, в котором дерево хранится в виде структуры, где каждый узел - это объект, в котором хранится значение и ссылки на правого и левого потомка.
Есть альтернативный подход. Бинарное дерево можно хранить в простом массиве! Подробнее сам подход описан в этом видео ua-cam.com/video/h755jk0HIko/v-deo.html
Это приводит как к уменьшению потребляемой памяти, так и к упрощению некоторых методов. Например, обход в ширину (traverse BFS) сокращается до простого прохода по массиву!
Я сам был ошарашен, но действительно метод обхода в ширину сократился до:
traverseBFS(callback){
if(!callback || typeof callback !== 'function'){
console.warn('Неправильный тип callback');
return;
}
this.nodes.forEach(callback);
}
Кроме того, я уверен, что несколько ускоряется операции вставки, потому как нам надо ходить не по ссылкам между объектами, а работать в пределах индекса одного массива.
10 секунд видео пропустил, подумал что за волос на экране
Что за волос?
@@webelart Когда с телефона смотрел, не понял сначала что за кадром стебель и принял за волос
@@arnoldinwhite8267 🤣🤣🤣 Я поняла о чём вы, да цветок у меня там супер странный.
Мне не очень зашло, всё быстро и поверхностно... Если будете продолжать делать контент, то пожалуйста делайте более медленно и с комментариями, а то у вас так, здесь пишем это, здесь это... Тема довольно тяжёлая, и по данному видео её даже поверхносто понять тяжело
А мне ваш комментарий не очень зашёл. Всё скомкано, не понятно, что не понятно и поверхностно. И я не шучу. Вы не задали ни единого вопроса, где именно не понятно. А просто разозлились на мой труд, ещё и обесценить попытались. К себе также относитесь? Злитесь, что мозг не сразу воспринял информацию?
Программирование в целом не простая система и преподать любую его часть, чтобы каждой живой душе было понятно - уже заранее невозможно. А многие знания требуют дополнительных наслоений, таких чтобы сам мозг был готов воспринять новое. Я разобрала те вещи, которые важны и которые мне самой здорово помогли в своё время.
Хотите, чтобы я к вам проявила эмпатию и помогла, то учитесь писать комментарии по существу с вопросами и с взаимным уважением, конечно.
тема не для новичков парень. требует пауз и обдумываний
Кек, ответ автора порадовал!) Мощно и по существу) 🫡