KZhead

КАК РАБОТАЮТ ДЕРЕВЬЯ | СТРУКТУРЫ ДАННЫХ

Alek OS
2024 ж. 22 Мам.
147 590 Рет қаралды
Жүктеу

clck.ru/33qcFE - развивайте навыки в работе с данными на курсах от Яндекс Практикума
Создавай будущее вместе с Тинькофф - l.tinkoff.ru/alekosmarch/?Ldt...
КАК РАБОТАЮТ ДЕРЕВЬЯ | СТРУКТУРЫ ДАННЫХ
Подписывайся в соц. сетях:
Телеграм - t.me/Alek_OS
ВК - vk.com/alekos1
❤️ Поддержка канала:
Бусти - boosty.to/alekos
Юмани - yoomoney.ru/to/410011179144828
✔️ Полезные ссылки:
Основы программирования - • КАК РАБОТАЕТ ПАМЯТЬ КО...
Полезно знать - • ЯЗЫКИ ПРОГРАММИРОВАНИЯ...
Алгоритмы и структуры данных - • УСКОРЬ СВОЙ КОД В МИЛЛ...
Мысли Алека - • КАК ИЗУЧАТЬ ПРОГРАММИР...
00:00 Введение
01:37 Яндекс Практикум
03:18 Двоичное дерево поиска
03:58 Двоичное дерево - вставка, поиск
05:45 Двоичное дерево - удаление
07:14 Обходы дерева
08:15 Работа в Тинькофф
09:49 АВЛ-дерево - вставка
16:08 АВЛ-дерево - удаление
16:44 Красно-чёрное дерево - вставка
20:34 Красно-чёрное дерево - удаление

Пікірлер

  • Подписывайся в телеграм-канал: t.me/Alek_OS

    @AlekOS@AlekOS Жыл бұрын

    • Начался список с 1, не с 0

      @dmbabaycev123@dmbabaycev123 Жыл бұрын

    • За это лайк)

      @dmbabaycev123@dmbabaycev123 Жыл бұрын

  • - Что делаешь? - Перекрашиваю чёрных детей. - Расист?! - Программист.

    @Cheeckoff@Cheeckoff Жыл бұрын

    • 🤣🤣🤣 Это за гранью добра и зла

      @bartbelrigvardo5216@bartbelrigvardo5216 Жыл бұрын

    • - Что делаешь? - Делаю деда красным и совершаю левый поворот. - Коммунист?! - Программист.

      @abuser-je3gl4vc1c@abuser-je3gl4vc1c5 ай бұрын

  • Не расстраивайтесь если не поняли ролик. Никто никогда его не поймет с первого раза. Такие ролики лучше воспринимать не как обучающие а как справочные.

    @user-jx8pe4yz6q@user-jx8pe4yz6q Жыл бұрын

    • я с первого раза все понял, а ты лох ))))))))))))

      @user-eb9cv3wx8b@user-eb9cv3wx8b8 ай бұрын

    • По фактам

      @user-ud1fw5zc8i@user-ud1fw5zc8i5 ай бұрын

    • Я понял с первого раза ролик. Даже слишком простой, сеньор ios, магистк комтерных наук

      @user-yd9xy3rb4x@user-yd9xy3rb4xАй бұрын

    • @@user-yd9xy3rb4x держи в курсе

      @user-yj2cq4fm7z@user-yj2cq4fm7z15 күн бұрын

  • Недавно наткнулся на ваш канал. Это просто супер. На фоне всего остального шлака по теме it, который существует на ютубе, ваш канал прям выделяется. Мне очень нравится ваш фундаментальный подход. Не тупо освоить синтаксис какого нибудь языка программирования, а дать именно теоретические основы программной инженерии. Да еще и в интерактивном и наглядном формате, с анимациями, графиками. Желаю развития каналу.

    @xagent@xagent Жыл бұрын

    • Точно, канал просто супер!!!

      @DemetriuszStrykowski@DemetriuszStrykowski Жыл бұрын

  • Вот так если задуматься, какую же титаническую работу автор воплотил, написать грамотно текст, визуализировать все сказанное…лайк!

    @user-ot5iy5es4l@user-ot5iy5es4l Жыл бұрын

  • Сложно, ничего непонятно, но очень интересно

    @viska_tru@viska_tru Жыл бұрын

  • Алекс, спасибо тебе! Мне безумно заходить этот контент, я под него стараюсь расслабляться и при этом продолжать вникать во все тонкости программирования, с такой визуализацией и музыкальным сопровождением уносит в транс порой..

    @BigRock379@BigRock3798 ай бұрын

  • Недавно сам писал реализацию красно-черного дерева, столько статей пересмотрел и видосов,эх,где ты был пару недель назад( Все очень классно и понятно!

    @user-ov1xr1ip7i@user-ov1xr1ip7i Жыл бұрын

  • Лучший из всех каналов на рунете по IT тематике. Спасибо за контент, за качественную информацию и высокий уровень подготовки ролика 👍

    @p.al.trofimov@p.al.trofimov Жыл бұрын

  • Alek, благодарю!! 👍 Инфографика великолепна! 🔥

    @Dmitrii-Zhinzhilov@Dmitrii-Zhinzhilov7 ай бұрын

  • Какой же годный контент… Большое спасибо!!!

    @alekseykhromov259@alekseykhromov259 Жыл бұрын

  • Как всегда кратко и информативно. Спасибо за пищу для мозга )

    @pashkiewich@pashkiewich Жыл бұрын

  • Спасибо за видео!!!

    @sashakuznechkin@sashakuznechkin Жыл бұрын

  • Братан, хорош, давай, давай, вперёд! Контент в кайф, можно ещё? Вообще красавчик! Можно вот этого вот почаще?

    @Leviafunny_@Leviafunny_ Жыл бұрын

  • Отличный контент! Спасибо!

    @matweyrybakovskiy2952@matweyrybakovskiy2952 Жыл бұрын

  • Спасибо за видеоролик!

    @andarworld8985@andarworld8985 Жыл бұрын

  • 7:10 - если при удалении узла, с двумя детьми, мы используем максимальный элемент слева(maxInLeft), то и удалять надо слева : node.left = delete(node.left, maxInLeft.key). На слайдах : node.right = delete(node.right, maxInLeft.key). Аналогичная неточность в коде для AVL Tree

    @MicP8@MicP8 Жыл бұрын

    • Верно. Хорошее замечание

      @user-ul9hq7xm2q@user-ul9hq7xm2q2 ай бұрын

    • а я сижу не понимаю что не так

      @Andreypochemu@Andreypochemu7 күн бұрын

  • Очень качественный контент, спасибо

    @user-jg7ly1ib2z@user-jg7ly1ib2z Жыл бұрын

  • круто, так быстро и подробно про деревья я еще не видел материала

    @arswarog@arswarog Жыл бұрын

  • Спасибо за видео. Лайк👍

    @user-fy3iv9dp7g@user-fy3iv9dp7g Жыл бұрын

  • как вовремя! как раз разбирался с ними! спасибо!

    @rechw769@rechw769 Жыл бұрын

  • Спасибо за очередное годное видео

    @user-ll7mx9mn8z@user-ll7mx9mn8z Жыл бұрын

  • Спасибо за видео Очень круто и фундаментально

    @leomysky@leomysky11 ай бұрын

  • огромное спасибо за видео

    @aidamur@aidamur Жыл бұрын

  • Прекрасно!!!

    @nikolaiandrianov1856@nikolaiandrianov1856 Жыл бұрын

  • Не стоило ли указать, что видео исключительно про бинарные деревья? А то складывается ощущение, что других и не существует. Я, к примеру, всё ждал, каким будет разбор B+Tree, чтобы в очередной итерации попробовать снова обуздать принцип работы InnoDB. Но видео очень залипательное, спасибо! Очень низкоуровнево, прям как я люблю.

    @cepmadbrozzer4448@cepmadbrozzer4448 Жыл бұрын

    • согласен, эту структуру данных как-то обходят стороной, иногда даже BTree расшифровывают как Binary Tree(

      @alexshturmovik3037@alexshturmovik3037 Жыл бұрын

    • Очень низкоуровнево, прям как я не люблю :) Но было интересно

      @DenysHolovin@DenysHolovin10 ай бұрын

  • Сними ролик про B-trees плз) Нормального ролика найти не могу, а они чаще используются для баз данных....

    @zadrot64@zadrot64 Жыл бұрын

  • Автор ты просто МегаМен. 👌👍 спасибо

    @vladimirzabaro6795@vladimirzabaro6795 Жыл бұрын

  • видео с удовольствием .... посмотрел.

    @BeketChan@BeketChan Жыл бұрын

  • О. Новенький видосик. Усваиваем

    @ghjklfghk@ghjklfghk Жыл бұрын

  • Лучший просто!

    @djorjegolmud517@djorjegolmud5175 ай бұрын

  • Алекс, привет. Мне кажется, что на 7:05 также нужно и слева искать значение ключа заменяющего узла, чтобы его удалить. Т.е. просто нужно добавить node.left = delete(node.left, maxInLeft.key); . Переписал твой код и попробовал на датасете от 5 до 11 удалить вершину 8, то с кодом из примера 7 станет вершиной и также останется лепестком, поэтому нужно и для левой части делать проверку (удаление).

    @laranMQR@laranMQR Жыл бұрын

  • Спасибо тебе за помощь

    @ron8897@ron88975 ай бұрын

  • Кончаю от твоего "Окей" 😁😁😁

    @ruslandad365@ruslandad365 Жыл бұрын

  • Отличный разбор! В коде copyTree (8:00)на экране есть ошибка, должно быть, как и сказано в звуковом комментарии: void copyTree(Node node) { If(node==null) return; print(node.value); copyTree(node.left); copyTree(node.right); }

    @MicP8@MicP8 Жыл бұрын

    • In English: pre-order, in-order, post-order

      @yuriykachanov2212@yuriykachanov22127 ай бұрын

  • Cпасибо, посмотрим

    @user-bw1fh9pd3i@user-bw1fh9pd3i Жыл бұрын

  • Мозг расплавится понять это с первого раза. Автору респект, что не только вник и разобрался, но и иллюстрировал и разжевал. Но осознать это всё очень сложно. Только базовые идеи

    @prokaza97@prokaza977 ай бұрын

  • Спасибо конечно огромное, но контрольная по этой теме была на прошлой неделе

    @jamessmit9738@jamessmit9738 Жыл бұрын

  • Благодарю за разбор красно-черного дерева Давно когда-то видел его разбор текстовый - не стал вьезжать и забил. STL на красно-черных - но кодировать их явно сложнее АВЛ и высота дерева в среднем на 25+% выше чем у АВЛ Так что друг друга они заменить и вправду не могут.

    @vadimmatskevich8439@vadimmatskevich8439 Жыл бұрын

  • Лайк не глядя, а потом уже просматриваем в высоком качестве и без перемотки 🌚

    @bOOOOkash@bOOOOkash Жыл бұрын

  • Это класс, это здорово! Ну а компиляторы, теперь, как работают?

    @user-lp3ke5bg2u@user-lp3ke5bg2u Жыл бұрын

  • Капитальный красавчик !

    @d1merz@d1merz Жыл бұрын

  • Интересно, круто рассказываешь, но пока тяжело. Вернусь через месяц

    @user-ij9vb6wn1z@user-ij9vb6wn1z Жыл бұрын

  • Спасибо 👍

    @Mercowod@Mercowod9 ай бұрын

  • Жёсткий контент. Примеров только бы побольше

    @user-gv9dg4ni5g@user-gv9dg4ni5g5 ай бұрын

  • 23:51 если я правильно понял, то это второй кейс из момента 22:08. Тогда получается ошибочка: чёрные дети красного брата не должны быть нулями. Потому, что их чёрные высоты в момент до удаления равны 1, а не нулю.

    @user-pl6hu6si1u@user-pl6hu6si1u Жыл бұрын

  • Подсказка, по поводу того, чтобы понять почему КЧД балансируется, узнайте что такое 2-3 дерево, частный случай n-дерева. Когда вы поймете, 2-3 дерево, тогда вы поймет что кчд - это и есть 2-3 дерево, просто для обозначения левого и правого элемента, нам понадобилось красить узлы бинарного дерева.

    @user-sf5zv4jc5v@user-sf5zv4jc5v Жыл бұрын

  • Деревья придумали для обычных процессоров, которые способны выполнять одно сравнение за одну команду. Ускорители для ИИ работают иначе - там вся память ассоциативная, и поиск заключается в нахождении самого близкого значения от запроса, в идеале равным запросу. Но так как от двоичной логики далеко уйти не получилось - то поиск выполняется параллельным приближением, прямо в памяти. Берётся блок памяти допустим 4к цифр, и каждую цифру сравнивают с запросом, все разом, параллельно. Результатом имеем новый слой данных x>y?x-y:y-x. Если на этом слое где-то получился ноль - поиск заканчивается. Иначе выполняется операция сравнения между двумя соседями, и образуется новый слой - куда помещаются только малые числа. Потом ещё и ещё слои, до самого минимального числа. Адрес минимального числа считается результатом поиска, и он может быть не точным. И ещё пока нижний слой выполняется - верхний может принять новую страницу памяти и новый поиск. Для всего этого требуется огромное количество транзисторов - но зато скорость поиска приближается к реализациям квантовых компов. Которые кстати работают примерно так-же.

    @avi-crakhome2524@avi-crakhome2524 Жыл бұрын

    • Интересная инфа, что за тема? Хотел почитать статьи

      @asjvchnvh9313@asjvchnvh93133 ай бұрын

  • Очень интересно

    @iliyalaz6132@iliyalaz6132 Жыл бұрын

  • Real good stuff

    @where631@where631 Жыл бұрын

  • Посмотрев данный ролик, я понимаю - какой же я тупой... Спасибо за ролик.

    @bOOOOkash@bOOOOkash Жыл бұрын

  • да ладно, чувакккк, обожаю

    @atmiccmx@atmiccmx Жыл бұрын

  • Alek OS скажите пожалуйста в какой программе вы делаете слайды?

    @user-bw1fh9pd3i@user-bw1fh9pd3i Жыл бұрын

  • Годнота

    @alexeyfladarov5200@alexeyfladarov5200 Жыл бұрын

  • на 8:03 у вас опечатка. Вы говорите что сначала выводим родителя потом левого и правого, но в коде у вас наоборот сначала левый и правый и потом родитель.

    @xagent@xagent Жыл бұрын

  • Спасибо за видео. Что-то код "Прямого обхода" совпадает с кодом "Обратно подхода". Или я чего-то непонял?

    @glebbondarenko67@glebbondarenko67 Жыл бұрын

  • Хорош комменты сыпать) лайки ставьте)

    @aleksandrk.5818@aleksandrk.5818 Жыл бұрын

    • Да поставили уже ))))

      @senkamatic8448@senkamatic8448 Жыл бұрын

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

    @user-eo3xn8sz7d@user-eo3xn8sz7d6 ай бұрын

  • Здесь представлен довольно запутанный способ поворота дерева, хотя он эффективен. Есть более простой способ, для начала лучше его освоить. выглядит это примерно так: private Node rotateLeft(Node oldParent) { Node newParent = oldParent.right; Node newParentLeft = newParent.left; newParent.left = oldParent; oldParent.right = newParentLeft; oldParent.computeHeight(); newParent.computeHeight(); return newParent; } Данный метод поворачивает поддерево и возвращает новый корень,. Чтобы его корректно использовать, нужно чтобы методы добавления и удаления возвращали Node, и предрекурсионном методе вызов должен быть таким root = add(key, root);, где root - это корень дерева.

    @user-ip2fg9up8u@user-ip2fg9up8u6 ай бұрын

  • на 8:13 функции deleteTree и copyTree совершенно идентичные, хотя вроде разные обходы.......

    @vitaly_markov@vitaly_markov Жыл бұрын

  • Самое крутое объяснение работы деревьев

    @eugenevolohonsky1469@eugenevolohonsky1469 Жыл бұрын

  • Неалохо было бы посмотреть настолько подробное видео года два назад, когда была такая дисциплина. Было бы гораздо легче.

    @sweetarteko@sweetarteko Жыл бұрын

  • 1. 7:39, 7:56 print(node.value) разве нам не нужно вывести ключи, т.е. print(node.key) ? 2. 14:22 фукция leftRoatet строка node.right_.left_ = node.right_.right_; не лишняя? 3. После вставки в узла АВЛ в дерево его нужно балансировать? P.s. очень крутое видео, спасибо.

    @KIR_Engineer@KIR_Engineer2 ай бұрын

  • еще было б очень интересно посмотреть ролик про файловые системы. К примеру фат32. Как оно все устроено, где хранятся данные, что такое размер клстера и тд

    @OpenFrimeTVcom@OpenFrimeTVcom Жыл бұрын

    • у него есть поищите на канале!

      @MsAlexandr76@MsAlexandr76 Жыл бұрын

    • @@MsAlexandr76 вы меня дурите. нету такого

      @OpenFrimeTVcom@OpenFrimeTVcom Жыл бұрын

    • Теперь точно есть) kzhead.info/sun/ebWYqMmRZ5d5o3k/bejne.html

      @user-pd8vg1gd5z@user-pd8vg1gd5z Жыл бұрын

  • Персистентное AVL- дерево по неявному ключу с групповыми модификациями - кайф

    @daniilivanik5021@daniilivanik502111 ай бұрын

  • Как можно было жить и не знать этого, спасибо P.S. Серьёзно, без шуток

    @china6714@china6714 Жыл бұрын

  • Монтаж топ, но умение объяснять это искусство. Нашёл видео по этой же теме 9летней давности и сразу всё понял. А тут от ролика только перегрузка лишняя. Но лайк за труды

    @MgsMen@MgsMen5 ай бұрын

    • Скинь ролик плз

      @gabibli@gabibli4 ай бұрын

  • Пушкааааа

    @call_nick@call_nick Жыл бұрын

  • Ничего не понятно, но очень интересно!

    @alekseybiryukov7497@alekseybiryukov7497 Жыл бұрын

  • Разбор структур различных файловых систем не ожидается ли в ближайшем будущем?

    @cepmadbrozzer4448@cepmadbrozzer4448 Жыл бұрын

  • Забавно что я сейчас как раз делала домашку з бинарньім деревом, и єто видео просто бьіло у меня в реках Судьба походу

    @user-eb1qm7ho8h@user-eb1qm7ho8h Жыл бұрын

    • це відео ще й тілки но вийшло, у тебе там мабудь кайф лютий?

      @sospeedwagon9289@sospeedwagon9289 Жыл бұрын

    • Я не понимаю

      @user-zt8zo5sd5c@user-zt8zo5sd5c Жыл бұрын

    • @@user-zt8zo5sd5c пон

      @sospeedwagon9289@sospeedwagon9289 Жыл бұрын

    • даааа, я тоже

      @user-ke7su7zc9l@user-ke7su7zc9l Жыл бұрын

  • Круто. Но жестко)

    @ceo-s@ceo-s Жыл бұрын

  • Интересная тема, а какое практическое применение, где это можно встретить?

    @user-nm8fu9fh7j@user-nm8fu9fh7j Жыл бұрын

  • Хорошие видео, по кормену цикл идет?

    @wensietland5169@wensietland5169 Жыл бұрын

  • А где найти код из видео? И, кажется, на видео не попал метод Rotate, необходимый для реализации балансировки после удаления в КЧ дереве.

    @alanturing487@alanturing4875 ай бұрын

  • Подскажите, чем наибольший элемент дерева отличается от самого наибольшего?

    @mikemerinoff@mikemerinoff11 ай бұрын

  • Тинькофф ищет только Middle(+) . а видео про Junior(стажер) 😅

    @Ahmedhkad@Ahmedhkad Жыл бұрын

  • Ее новое видео!

    @borshch334@borshch334 Жыл бұрын

  • По-моему на 7:05 рекурсивно удалять дубль 6ки нужно в левом потомке node.left = delete(node.left, maxInLeft.key) , а не в правом как на видео.

    @markbondarchuk7043@markbondarchuk7043 Жыл бұрын

    • Мне кажется, что нужно и там, и там. Т.е. нужно просто добавить node.left = delete(node.left, maxInLeft.key), а остальное также оставить.

      @laranMQR@laranMQR Жыл бұрын

    • ​@@laranMQRзачем и там, и там, если мы берём 6ку именно из левого дерева, значит ее оттуда и нужно удалить. Справа может отказаться другая 6ка, которую мы удалим "просто так"

      @vsevolodkasatchikov6730@vsevolodkasatchikov6730 Жыл бұрын

  • Объясните пожалуйста, а как черно-красные деревья связаны со значениями в них? Та выполняется правило, что левая ветвь меньше корня, а правая больше или равна?

    @danitkriper4114@danitkriper4114 Жыл бұрын

  • Не глядя лайк ❤

    @geekdev0@geekdev0 Жыл бұрын

    • Не слушая, тоже затычковал

      @user-ow6dr9ok6c@user-ow6dr9ok6c Жыл бұрын

  • В двоичном дереве поиска для метода insert забыли условие для проверки равности ключей (для того чтобы заменить значение по уже существующему ключу).

    @user-mt6wt9vc1x@user-mt6wt9vc1x17 күн бұрын

  • the best ever

    @web-writer4769@web-writer4769 Жыл бұрын

  • Мне кажется, когда рассказывали про удаление из красно-чёрного дерева, брата по ошибке назвали дядей

    @user-ze3ez3iy6c@user-ze3ez3iy6c11 ай бұрын

  • Братан что за музон в начале до рекламы ?

    @memyselfi9155@memyselfi9155 Жыл бұрын

  • Смотрю про красно-черное дерево в голове играют Rolling Stones😅

    @anolegych@anolegych Жыл бұрын

    • Paint it black, понимаю)

      @user-pl6hu6si1u@user-pl6hu6si1u Жыл бұрын

  • 6:55 то есть я могу в качестве корня взять либо 7 либо 6?

    @artroden3746@artroden3746 Жыл бұрын

  • Хм, а если я пишу последовательность [0:💯] - это у меня будет одна ветка справа от начала до конца, или я что-то неправильно понял? P.S. Только написал коммент, тут же начался блок про АВЛ 🙂

    @user-uu8jv2ki3h@user-uu8jv2ki3h9 ай бұрын

  • Омг тут про красно-чёрное дерево... Жэээсть

    @andromeda_vesna@andromeda_vesna Жыл бұрын

  • Классно чёрное дерево это конечно хорошо, но пока сам такую структуру не напишешь, то что-то полностью понять сложновато.

    @Secvad@Secvad Жыл бұрын

  • Thanks m8

    @where631@where631 Жыл бұрын

  • Комент для продвижения ролика*

    @An_entertaining_story@An_entertaining_story Жыл бұрын

  • Год назад, будучи на первом курсе, сломал себе голову реализацией Fibonacci Heap, тоже тема годная и непонятная)

    @user-ho9hy2oc9c@user-ho9hy2oc9c Жыл бұрын

  • Объясните, пожалуйста, почему на 17:33 в правой ветке дерева узел черный, а не красный, если у него двое детей и оба черные листы? По объяснению, он должен быть красный и тогда все красно-черное древо несбалансированно... или нет?

    @mianaviatte@mianaviatte Жыл бұрын

    • Черный узел может иметь два черных ребенка, а вот красный узел не просто может, а обязан. В этом вся логика

      @dimondsafkage4620@dimondsafkage46209 ай бұрын

  • Что-то я совсем запутался... 7, 5, 8 в узлах - это пример ключей или значений? 4:20

    @something-like-that@something-like-that9 ай бұрын

  • Как сойти с ума за 25 минут

    @antik_tm2272@antik_tm22726 ай бұрын

  • кайф

    @nerusnotfound@nerusnotfound Жыл бұрын

  • я правильно понял, в видео код писался на java?(я python'ист, +немного знаю как выглядит C)

    @p8wowyt121@p8wowyt121 Жыл бұрын

  • 👍

    @Didar.Kussain@Didar.Kussain Жыл бұрын

  • Ох, что-то мне не хорошо 😁

    @Tim-Slim@Tim-Slim Жыл бұрын
KZhead