День 13 Сегодня поговорим про бинарные деревья поиска. BINARY SEARCH TREE Бинарные деревья поиска (Binary Search Trees, BST) — это структура данных, в которой каждый узел имеет значение (ключ) и максимум два потомка: левого и правого. Важным свойством бинарного дерева поиска является то, что все ключи в левом поддереве меньше ключа корня и родительского узла, а ключи в правом поддереве больше ключа корня и и родительского узла. Это свойство позволяет быстро и эффективно искать, добавлять и удалять элементы из дерева. Узел (Node) — это каждый элемент бинарного дерева поиска, содержащий значение (ключ) и ссылки на левого и правого потомков (если они существуют). Корень (Root) — это верхний узел бинарного дерева, от которого начинается поиск и проход по дереву. У корня нет родителя. Левый и правый потомок (Left Child, Right Child) — это узлы, которые непосредственно связаны с другим узлом в дереве. Левый потомок содержит значение, меньшее, чем значение текущего узла, а правый потомок содержит значение, большее, чем значение текущего узла. Лист (Leaf) — это узел дерева, не имеющий потомков (левого и правого). Высота дерева (Height) — это максимальная глубина узла в дереве, то есть максимальное количество уровней от корня до любого листового узла. Глубина дерева (Depth) — это количество родительских узлов от корня до данного узла в дереве. Префиксный, инфиксный и постфиксный обходы (Pre-order, In-order, Post-order traversals) — это три основных метода обхода бинарного дерева. Префиксный обход производит операции над текущим узлом перед рекурсивным обходом его потомков. Инфиксный обход обрабатывает текущий узел между рекурсивным обходом его левого и правого потомков. Постфиксный обход обрабатывает текущий узел после рекурсивного обхода его потомков. ------- ВИДЕО ЛЕКЦИЯ Вот тут как я считаю довольно понятно и доступно разобрали BST. https://www.youtube.com/watch?v=9o_i0zzxk1s&ab_channel=%23SimpleCode ------- ЗАДАЧА 1 Validate Binary Search Tree (Medium $ BST $ Попытка номер 1). Решена со сложностью Time - O(n), Space O(1) за 18 минут при помощи рекурсии. Задача была легкой. Правда потом я понял что я не учитывал все свойства BST и проверял только ближайшие узло. А оказывается надо было точно убедиться что все значения узлов левой части дерева должны быть точно меньше чем значения их родительского и головного узла. А все значения узлов правой части дерево должны быть точно больше значения головного и родительского узла. ------- ЗАДАЧА 2 Kth Smallest Element in a BST (Medium $ BST $ Попытка номер 1). Решена со сложностью Time - O(n), Space O(n), где n - количество узлов дерева, за 32 минуты при помощи рекурсии и списка. Задача была нетрививальной. ------- ВЕСЬ ПРОГРЕСС НА ТЕКУЩИЙ МОМЕНТ: Neetcode Всего 20/75 . easy 12/19. medium 8/49. AlgoExpert Всего 13/200. easy 5/31 medium 8/73. ------- Если вы хотите посмотреть решения данных алгоритм задач или поделится своим мнением, тогда переходите в чат сообщества ▶️ https://t.me/zufarexplainedit Серия постов по подготовке Зуфара к FAANG #Zufar_Faang_Preparation_Notes

День 14 Сегодня продолжим говорить про бинарные деревья поиска BST. А именно я предлагаю построить бинарное дерево в коде вам самим. То есть написать все методы работы с деревом. Внизу же, я предлагаю свой вариант реализации этих основных методов. ОСНОВНЫЕ ОПЕРАЦИИ BST • Добавление нового узла (insert); ``` public BST insert(int value) { BST currentNode = this; while (true) { if (currentNode.value > value) { if (currentNode.left == null) { currentNode.left = new BST(value); return this; } else { currentNode = currentNode.left; } } else { if (currentNode.right == null) { currentNode.right = new BST(value); return this; } else { currentNode = currentNode.right; } } } return this; } ``` • Удаление узла по его значению (remove); Добавил в чат, тут не помещается. • Поиск узла по значению (contains); public boolean contains(int value) { BST currentNode = this; while (currentNode != null) { if (value < currentNode.value) { currentNode = currentNode.left; } else if (value > currentNode.value) { currentNode = currentNode.right; } else { return true; } } return false; } Допустим, что так выглядит наше дерево class class BST { public int value; public BST left; public BST right; public BST(int value) { this.value = value; } } ------- ВИДЕО ЛЕКЦИЯ Вот тут как я считаю довольно понятно и доступно разобрали BST. https://www.youtube.com/watch?v=0BUX_PotA4c&ab_channel=AlekOS ------- ЗАДАЧА 1 Lowest Common Ancestor of a Binary Search Tree (Medium $ BST $ Попытка номер 1). Решена со сложностью Time - O(n), Space O(1) за 26 минут при помощи цикла while. Задача была легкой. ------- ЗАДАЧА 2 Binary Tree Level Order Traversal (Medium $ BST $ Попытка номер 1). Решена со сложностью Time - O(n), Space O(n), где n - количество узлов дерева, за 31 минуты при помощи Bread First Search подхода (BFS я рассмотрел вот тут). В целом если знаете этот подход, то задача изи. ------- ВЕСЬ ПРОГРЕСС НА ТЕКУЩИЙ МОМЕНТ: Neetcode Всего 22/75 . easy 12/19. medium 10/49. AlgoExpert Всего 13/200. easy 5/31 medium 8/73. ------- Если вы хотите посмотреть решения данных алгоритм задач или поделится своим мнением, тогда переходите в чат сообщества ▶️ https://t.me/zufarexplainedit Серия постов по подготовке Зуфара к FAANG #Zufar_Faang_Preparation_Notes