Деревья поиска
Дерево — одна из наиболее распространенных структур данных в программировании.
Деревья состоят из набора вершин (узлов, нод) и ориентированных рёбер (ссылок) между ними. Вершины связаны таким образом, что от какой-то одной вершины, называемой корневой (вершина 8 на рисунке), можно дойти до всех остальных единственным способом.
- Родитель вершины $v$ — вершина, из которой есть прямая ссылка в $v$.
- Дети (дочерние элементы, сын, дочь) вершины $v$ — вершины, в которые из $v$ есть прямая ссылка.
- Предки — родители родителей, их родители, и так далее.
- Потомки — дети детей, их дети, и так далее.
- Лист (терминальная вершина) — вершина, не имеющая детей.
- Поддерево — вершина дерева вместе со всеми её потомками.
- Степень вершины — количество её детей.
- Глубина вершины — расстояние от корня до неё.
- Высота дерева — максимальная из глубин всех вершин.
Деревья чаще всего представляются в памяти как динамически создаваемые структуры с явными указателями на своих детей, либо как элементы массива связанные отношениями, неявно определёнными их позициями в массиве.
Деревья также используются в контексте графов.
Бинарные деревья поиска
Бинарное дерево поиска (англ. binary search tree, BST) — дерево, для которого выполняются следующие свойства:
- У каждой вершины не более двух детей.
- Все вершины обладают ключами, на которых определена операция сравнения (например, целые числа или строки).
- У всех вершин левого поддерева вершины $v$ ключи не больше, чем ключ $v$.
- У всех вершин правого поддерева вершины $v$ ключи больше, чем ключ $v$.
- Оба поддерева — левое и правое — являются двоичными деревьями поиска.
Более общим понятием являются обычные (не бинарные) деревья поиска — в них количество детей может быть больше двух, и при этом в «более левых» поддеревьях ключи должны быть меньше, чем «более правых». Пока что мы сконцентрируемся только на двоичных, потому что они проще.
Чаще всего бинарные деревья поиска хранят в виде структур — по одной на каждую вершину — в которых записаны ссылки (возможно, пустые) на правого и левого сына, ключ и, возможно, какие-то дополнительные данные.
Как можно понять по названию, основное преимущество бинарных деревьев поиска в том, что в них можно легко производить поиск элементов:
Эта функция — как и многие другие основные, например, вставка или удаление элементов — работает в худшем случае за высоту дерева. Высота бинарного дерева в худшем случае может быть $O(n)$ («бамбук»), поэтому в эффективных реализациях поддерживаются некоторые инварианты, гарантирующую среднюю глубину вершины $O(\log n)$ и соответствующую стоимость основных операций. Такие деревья называются сбалансированными.
Источник
Нахождение глубины бинарного дерева
У меня возникли проблемы с пониманием этого maxdepth-кода. Любая помощь будет оценена по достоинству. Вот пример, который я привел.
int maxDepth(Node *&temp) < if(temp == NULL) return 0; else < int lchild = maxDepth(temp->left); int rchild = maxDepth(temp->right); if(lchild
> В основном, я понимаю, что функция рекурсивно вызывает себя (для каждого левого и правого случаев), пока не достигнет последнего узла. как только он это делает, он возвращает 0, затем 0 +1. то предыдущий узел равен 1 +1. затем следующий — 2 +1. если есть bst с 3 левыми дочерними элементами, int lchild вернет 3. а дополнительный + 1 — корень. Поэтому мой вопрос заключается в том, откуда все эти +1. он возвращает 0 на последнем узле, но почему он возвращает 0 +1 и т.д., когда он идет вверх по левым/правым дочерним узлам? Я не понимаю, почему. Я знаю, что это так, но почему?
8 ответов
Помните, что в бинарных деревьях узел имеет не более 2-х детей (слева и справа)
Это рекурсивный алгоритм, поэтому он называет себя снова и снова.
Если temp (рассматриваемый узел) имеет значение null, он возвращает 0, поскольку этот узел ничего не должен и не должен учитываться. это основной случай.
Если рассматриваемый узел не является нулевым, у него могут быть дети. поэтому он получает максимальную глубину левого под дерева (и добавляет 1, для уровня текущего узла) и правого поддерева (и добавляет 1 для уровня текущего узла). он затем сравнивает два и возвращает большее из двух.
Он погружается в два поддерева (temp-> влево и temp-> вправо) и повторяет операцию до тех пор, пока не достигнет узлов без детей. в этот момент он будет вызывать maxDepth слева и справа, который будет null и возвращает 0, а затем начнет возвращать цепочку вызовов.
Поэтому, если у вас есть цепочка из трех узлов (скажем, root-left1-left2), она перейдет влево2 и вызовет maxDepth (слева) и maxDepth (справа). каждый из них возвращает 0 (они равны нулю). то он возвращается влево2. он сравнивается, оба равны 0, поэтому больший из них, конечно, равен 0. он возвращает 0 + 1. то мы находимся налево1 — повторяет, обнаруживает, что 1 является большим из его правых справа (возможно, они одинаковы или не имеют права ребенка), поэтому он возвращает 1 + 1. теперь мы находимся у корня, то же самое, он возвращает 2 + 1 = 3, что является глубиной.
Рассмотрим эту часть (большего дерева):
Теперь мы хотим рассчитать глубину этой части дерева, поэтому мы передаем указатель на A как свой параметр.
Очевидно, указатель на A не является NULL , поэтому код должен:
- call maxDepth для каждого из детей A (левая и правая ветки). A->right — B , но A->left явно NULL (поскольку A не имеет левой ветки)
- сравните их, выберите наибольшее значение
- вернуть это выбранное значение + 1 (поскольку сам A берет уровень, не так ли?)
Теперь мы рассмотрим, как maxDepth(NULL) и maxDepth(B) .
Первое довольно легко: первая проверка сделает maxDepth возвращение 0. Если другой ребенок были NULL тоже, как глубина будет равна (0), и мы должны возвращать 0 + 1 для A сам.
Но B не пуст; он не имеет ветвей, хотя, поэтому (как мы заметили) его глубина равна 1 (наибольшая из 0 для NULL на обеих частях + 1 для самого B ).
Теперь вернитесь к A maxDepth его левой ветки ( NULL ) равен 0, maxDepth его правой ветки равно 1. Максимум из них равен 1, и мы должны добавить 1 для самого A , поэтому он 2.
Дело в том, что те же самые шаги должны быть выполнены, когда A является лишь частью большего дерева; результат этого вычисления (2) будет использоваться на более высоких уровнях вызовов maxDepth .
Источник
Русские Блоги
Алгоритм летакода — максимальная глубина бинарного дерева
Это первый из Юэл164Второе обновление,166Оригинал
01 Предметы и препараты
Сегодня я представил 23-й выпуск легкого уровня в алгоритме LetCode (номер 104 названия). Дайте бинарное дерево, чтобы найти его максимальную глубину. Максимальная глубина — количество узлов на максимальном пути от корневого узла до максимального узера листьев. Листья являются узлами без дочерних узлов.
Например: учитывая бинарное дерево [3, 9, 20, NULL, NULL, 15, 7],
Возвращает его глубину = 3.
Инструмент разработки, используемый в этом контексте, является Eclipse. Версия, используемая JDK, является 1.8, среда представляет собой Win7 64-битную систему, написанную и тестируйте с помощью языка Java.
02 Первое решение
Максимальная глубина — это количество узлов, содержащихся на корневом узле к траектору самого дальнеготельного листового узла. Возьмите два вилочных дерева выше, самый длинный путь имеет два: 3-> 20-> 15, 3-> 20-> 7, эти Два номера узлов на пути линии 3, поэтому, наконец, его глубина 3 выводы.
Особые обстоятельства: Когда входящее двоичное дерево пустое, у него нет узлов, его глубина 0.
Особые обстоятельства: Когда только корневой узел, его глубина 1, только его собственный узел.
Нормальная ситуация: мы можем попробовать шаг за шагом, простой процессом расчета глубины двоичного дерева, или вышеуказанное двоичное дерево в качестве примера.
Начиная с корневого узла, количество узлов составляет 1, потому что он имеет только один узел.
Введите узел дочернего узела корневого узла, в это время самый длинный путь должен рассчитать максимальный путь этого левого субпода и 20 этого правого ребенка. Очевидно, что 9 является узлом листьев, только один узел сама; и 20 имеет свой собственный Узел ребенка, на данный момент, вам нужно будет рассчитать самый длинный путь от 20.
20 Существует левый суб-узел 15, правый узел 7, а затем продолжают вычислять самый длительный путь 15 и 7, а 15 и 7 — это узлы листьев, поэтому количество узлов составляет всего 1, плюс 20 узлов Это относится к корневому узлу узел для детей, самый длинный путь в 20 узле 2.
Два подмазера 9, 20, максимальный путь узера 9 ребенка составляет 1, максимальное количество узлов равно 2, а максимальное значение принимается, а сам корневой узел добавляется. Количество узлов, 1 + 2 = 3, 3 — количество узлов на самом длинном пути, то есть глубина бинарного дерева.
Анализ здесь, мы знаем, чтобы рассчитать количество узлов из корневого узла в самый дальний узел листьев, вам необходимо рассчитать максимальный путь левого и правого дочерних узлов, и рассчитать максимальный путь левого и правого дочерних узлов, Он будет рассчитан. Они имеют самый длинный путь левого и правого дочерних узлов ниже, и мы можем использовать рекурсивный, после количества узлов нижнего листа, замечательный слой придумает максимум.
public int maxDepth(TreeNode root) < if (root == null) < return 0; >int left = maxDepth(root.left); int right = maxDepth(root.right); return 1 + Math.max(left, right); > 03 Второе решение
Поскольку рекурсия можно использовать, мы также можем попробовать способ использовать обход. Начиная с корневого узла, верхняя часть дочернего узла автоматически сохраняется, а подсуд прохождения хранится при прохождении, и он проходит на все подмазки.
public int maxDepth2(TreeNode root) < if (root == null) < return 0; >int depth = 0; Queue q = new LinkedList<>(); q.offer(root); while (!q.isEmpty()) < Queuetem = new LinkedList<>(); while(!q.isEmpty()) < TreeNode node = q.poll(); if (node.left != null) < tem.offer(node.left); >if (node.right != null) < tem.offer(node.right); >> q = tem; depth++; > return depth; > Особые обстоятельства или первое решение, цикл внутреннего слоя является дочерним узлом каждого слоя.
04 Третье решение
Второй метод решения имеет новую очередь для получения следующего слоя данных узла для ввода каждого цикла, может ли его изменять, сделать его более лаконичным? Здесь мы используем размер очереди, чтобы контролировать его, начиная с корневого узла, после ввода очереди размер очереди 1, начиная входить в цикл внутреннего слоя, после ходьбы один раз, очередь имеет два детских узла, в это время Размер 2, а затем продолжает запускать контур внутреннего слоя, пока все детские узлы не будут пройдены.
public int maxDepth3(TreeNode root) < if (root == null) < return 0; >int depth = 0; Queue q = new LinkedList<>(); q.offer(root); while (!q.isEmpty()) < int n = q.size(); while(n-- >0) < TreeNode node = q.poll(); if (node.left != null) < q.offer(node.left); >if (node.right != null) < q.offer(node.right); >> depth++; > return depth; > 05 Проверка и тест
Для приведенных выше двух решений простая бинарное дерево провело тест на данные.
public static void main(String[] args) < Easy_104_MaximumDepthOfBinaryTree instance = new Easy_104_MaximumDepthOfBinaryTree(); TreeNode t = new TreeNode(1); TreeNode t2 = new TreeNode(2); TreeNode t3 = new TreeNode(3); TreeNode t4 = new TreeNode(4); TreeNode t5 = new TreeNode(5); TreeNode t6 = new TreeNode(6); TreeNode t7 = new TreeNode(7); TreeNode t8 = new TreeNode(8); t.left = t2; t.right = t3; t2.left = t4; t2.right = t5; t3.left = t6; t3.right = t7; t7.left = t8; long start = System.nanoTime(); int result = instance.maxDepth(t); long end = System.nanoTime(); System.out.Println («MaxDepth --- Выход:» + Результат + ", при использовании:" + (конец-стартуе) / 1000 + "микросекунды"); long start2 = System.nanoTime(); int result2 = instance.maxDepth2(t); long end2 = System.nanoTime(); System.out.Println («MaxDepth2 --- Выход:» + Realse2 + ", при использовании:" + (end2-start2) / 1000 + "микросекунды"); long start3 = System.nanoTime(); int result3 = instance.maxDepth3(t); long end3 = System.nanoTime(); System.out.Println («MaxDepth3 --- Выход:» + Realse3 + ", при использовании:" + (end3-start3) / 1000 + "микросекунды"); >Результаты теста следующие:
MaxDepth --- Выход: 4, время: 23 микросекунда Maxdepth2 --- Выход: 4, используемый: 586 микросекунд Maxdepth3 --- Выход: 4, используемый: 16 микросекунд Из результатов теста можно увидеть, что обход и рекурсивность могут решать проблемы, второе решение, поскольку каждый цикл должен создавать новые объекты, это не мало для памяти и времени работы, после оптимизации третьего решения больше подходит для обхода использовать.
06 Маленький узел
Вышеупомянутое содержимое, если у вас есть какие-либо хорошие идеи решения, предложения или другие вопросы, вы можете отправить сообщение ниже, похвалы, оставьте сообщение, вперед — это самое большое возвращение и поддержка для меня!
Источник