Структура данных 101: глубокое погружение в деревья с помощью Java

Структуры данных — важная часть собеседований по программированию и кодированию. Эти навыки показывают вашу способность комплексно мыслить, решать неоднозначные проблемы и распознавать шаблоны кодирования.

Программисты используют структуры данных для организации данных, поэтому чем эффективнее будут ваши структуры данных, тем лучше будут ваши программы. .

Сегодня мы углубимся в одну из самых популярных структур данных: деревья .

Сегодня мы рассмотрим:

  • Что такое дерево?
  • Типы деревьев
  • Введение в обход дерева и поиск
  • Следующие шаги и завершение

Успейте на следующем собеседовании

Освойте структуры данных для кодирования интервью с практической практикой

Структуры данных для кодирования интервью в Java

Что такое дерево?

Структуры данных используются для хранения и организации данных. Мы можем использовать алгоритмы для управления и использования наших структур данных. Различные типы данных организованы более эффективно за счет использования разных структур данных.

Деревья — это нелинейные структуры данных. Они часто используются для представления иерархических данных. В качестве реального примера иерархическая структура компании использует дерево для организации.

Компоненты дерева

Деревья представляют собой набор узлы (вершины), и они связаны ребрами (указателями), представляя иерархические связи между узлами. Узел содержит данные любого типа, но все узлы должны быть одного типа данных. Деревья похожи на графы, но цикл не может существовать в дереве. Каковы различные компоненты дерева?

Корень: Корень дерева — это узел, у которого нет входящей ссылки (т.е. нет родительского узла). Думайте об этом как об отправной точке вашего дерева.

Дочерние: Дочерний элемент дерева — это узел с одной входящей ссылкой от узла над ним (т. Е. родительский узел). Если два дочерних узла имеют одного и того же родителя, они называются братьями и сестрами.

Родитель: родительский узел имеет исходящую ссылку, соединяющую его с одним или несколькими дочерними узлами.

Leaf: Лист имеет родительский узел, но не имеет исходящей ссылки на дочерний узел. Думайте об этом как о конечной точке вашего дерева.

Поддерево: Поддерево — это меньшее дерево, содержащееся в большом дереве. Корнем этого дерева может быть любой узел большего дерева..

Глубина: глубина узла — это количество ребер между этим узлом и корнем. Думайте об этом как о том, сколько шагов между вашим узлом и начальной точкой дерева.

Высота: Высота узла — это количество ребер в самый длинный путь от узла до листового узла. Думайте об этом как о количестве шагов между вашим узлом и конечной точкой дерева. Высота дерева — это высота его корневого узла.

Степень: Степень узла относится к количеству поддеревьев.

Почему мы используем деревья?

Деревья можно применять ко многим вещам. Иерархическая структура дает дереву уникальные свойства для хранения, управления и доступа к данным. Деревья образуют одну из самых основных структур компьютеров. Мы можем использовать дерево для следующих целей:

  • Хранение как иерархия. Хранение информации, которая естественным образом встречается в иерархии. Файловые системы на компьютере и PDF используют древовидную структуру.
  • Поиск. Хранение информации, которую мы хотим быстро найти. По деревьям легче искать, чем по связному списку. Некоторые типы деревьев (например, AVL и красно-черные деревья) предназначены для быстрого поиска.
  • Наследование. Деревья используются для наследования, парсера XML, машинного обучения , и DNS, среди прочего.
  • Индексирование. Для индексирования базы данных можно использовать расширенные типы деревьев, такие как B-деревья и B + деревья.
  • Сеть. Деревья идеально подходят для таких вещей, как социальные сети и компьютерные шахматы.
  • Кратчайший путь. Spanning Tree можно использовать для поиска кратчайших путей в маршрутизаторах для работы в сети.
  • и многое другое

Как сделать дерево

Но как это сделать? все смотрят в коде? Например, чтобы построить дерево в Java, мы начинаем с корневого узла.

  Node  root = new Node  ("root");  

Когда у нас есть корень, мы можем добавить наш первый дочерний узел с помощью addChild , который добавляет дочерний узел и назначает его родительскому узлу. Мы называем этот процесс вставкой (добавлением узлов) и удалением (удалением узлов).

   Узел  node1 = root.addChild (new Node  ("node 1"));  

Мы продолжаем добавлять узлы, используя тот же процесс, пока не получим сложную иерархическую состав. В следующем разделе мы рассмотрим различные виды деревьев, которые мы можем использовать..

Типы деревьев

Есть много типов деревьев, которые мы можем использовать для различной организации данных в иерархической структуре. Дерево, которое мы используем, зависит от проблемы, которую мы пытаемся решить. Давайте посмотрим на деревья, которые мы можем использовать в Java. Мы рассмотрим:

  • N-арные деревья
  • Сбалансированные деревья
  • Бинарные деревья
  • Деревья двоичного поиска
  • Деревья AVL
  • Красно-черные деревья
  • 2-3 дерева
  • 2-3-4 дерева

N-арное дерево

В N-арном дереве узел может иметь дочерние узлы от 0 до N. Например, если у нас есть 2-арное дерево (также называемое двоичным деревом), оно будет иметь максимум 0–2 дочерних узла.

xml version = «1.0» encoding = «UTF-8» standalone = «no»?> % 0 node_1 1 node_22 node_2 -> node_1-> node_2 node_3 3 node_3 -> node_1-> node_3 node_4 4 node_4 -> node_1-> node_4 node_1590533034786 6 node_1590533034786 -> node_1-> node_1590533034786 node_1590532991864 3 node_1590532991864 -> node_3-> node_1590532991864 путь> node_1590533016536 7 node_1590533016536 -> node_3-> node_1590533016536 node_1590533042802 8 node_1590533042802 -> node_4-> node_1590533042802
N-арное дерево

Примечание: коэффициент баланса узла разница в высоте между левым и правым поддеревьями.

Сбалансированное дерево

Сбалансированное дерево — это дерево с почти всеми листовыми узлами в того же уровня, и это чаще всего применяется к поддеревьям, что означает, что все поддеревья должны быть сбалансированы. Другими словами, мы должны сбалансировать высоту дерева, чтобы разница между высотой правого и левого поддеревьев не превышала единицы . Вот визуальное представление сбалансированного дерева.

xml version = «1.0» encoding = «UTF-8» standalone = «no»?> % 0 node_1 1 node_22 node_2 -> node_1-> node_2 node_3 3 node_3 -> node_1-> node_3 node_1590533142882 4 node_1590533142882 -> node_2-> node_1590533142882 node_1590533206785 5 node_1590533206785 -> node_2-> node_1590533206785 node_1590533167771 6 node_1590533167771 -> node_3-> node_1590533167771 node_1590533214146 7 node_1590533214146 -> node_3-> node_1590533214146
Двоичное дерево

Существует три основных типа двоичных деревья в зависимости от их структуры.

1. Полное двоичное дерево

Полное двоичное дерево существует, когда каждый уровень, за исключением последнего, заполнен, и все узлы на последнем уровне расположены настолько далеко, насколько это возможно. Вот визуальное представление полного двоичного дерева.

xml version = «1.0» encoding = «UTF-8» standalone = «no»?> % 0 node_1 1 node_22 node_2 -> node_1-> node_2 node_3 5 node_3 -> node_1-> node_3 node_1590533385622 3 node_1590533385622 -> node_2-> node_1590533385622 node_1590533363021 4 node_1590533363021 -> node_2-> node_1590533363021 node_1590533419778 6 node_1590533419778 -> node_3-> node_1590533419778 node_1590533356664 node_1590533356664 -> node_3-> node_1590533356664
Полное двоичное дерево (левая часть полностью заполнена)

2. Полное двоичное дерево

Полное двоичное дерево (иногда называемое правильным двоичным деревом) завершается, когда каждый узел, за исключением листьев, имеет двух дочерних элементов. Каждый уровень должен быть заполнен, а узлы расположены как можно дальше слева. Посмотрите на эту диаграмму, чтобы понять, как выглядит полное двоичное дерево.

xml version = «1.0» encoding = «UTF-8» standalone = «no»?> % 0 node_1 1 node_22 node_2 -> node_1-> node_2 node_3 3 node_3 -> node_1-> node_3 node_1590533548929 4 node_1590533548929 -> node_2-> node_1590533548929 node_1590533535474 5 node_1590533535474 -> node_2-> node_1590533535474 node_1590533516286 6 node_1590533516286 -> node_1590533548929-> node_1590533516286 node_1590533546340 7 node_1590533546340 -> node_1590533548929-> node_1590533546340
полное двоичное дерево

3. Совершенное двоичное дерево

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

xml version = «1.0» encoding = «UTF-8» standalone = «no»?> % 0 node_1 1 node_22 node_2 -> node_1-> node_2 node_3 3 node_3 -> node_1-> node_3 node_1590533623272 4 node_1590533623272 -> node_2-> node_1590533623272 node_1590533678037 5 node_1590533678037 -> node_2-> node_1590533678037 node_1590533664121 6 node_1590533664121 -> node_3-> node_1590533664121 node_1590533701406 7 node_1590533701406 -> node_3-> node_1590533701406
идеальное двоичное дерево

Примечание. У вас также может быть перекошенное двоичное дерево, в котором все узлы смещены влево или вправо, но рекомендуется избегать этого типа дерева в Java, поскольку оно далеко сложнее искать узел.

Деревья двоичного поиска

Двоичное дерево поиска — это двоичное дерево, в котором каждый узел имеет ключ и соответствующее значение. Это позволяет быстро искать и редактировать (добавлять или удалять), отсюда и название «поиск». Дерево двоичного поиска имеет строгие условия, основанные на его значении node . Важно отметить, что каждое двоичное дерево поиска является двоичным деревом, но не каждое двоичное дерево является двоичным деревом поиска.

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

xml version = «1. 0 «encoding =» UTF-8 «standalone =» no «?> % 0 node_1 Узел X node_2 Узел Y node_2 -> node_1-> node_2 node_3 путь> Поддерево 3 node_3 -> node_1-> node_3 node_1590533734546 Поддерево 1 node_1590533734546 -> node_2-> node_1590533734546 node_1590533739826 Поддерево 2 node_1590533739826 -> node_2-> node_1590533739826

В этом примере узел Y является родительским узлом с двумя дочерние узлы. Все узлы в поддереве 1 должны иметь значение меньше узла Y, а поддерево 2 должно иметь значение больше, чем узел Y.

Деревья AVL

Деревья AVL — это особый тип дерева двоичного поиска, который самобалансируется путем проверки коэффициент баланса каждого узла. Коэффициент баланса должен быть +1 , 0 или -1 . Максимальная разница в высоте между левым и правым поддеревьями может быть только .

Если эта разница становится больше единицы, мы должны повторно сбалансировать наше дерево чтобы сделать его действительным, используя техники вращения. Чаще всего они используются в приложениях, в которых поиск является наиболее важной операцией. Посмотрите на это изображение, чтобы увидеть действительное дерево AVL.

xml version = «1.0» encoding = «UTF-8» standalone = «no»?> % 0 node_1 6 node_24 node_2 -> node_1-> node_2 node_3 8 node_3 -> node_1-> node_3 node_1590533866628 3 node_1590533866628 -> node_2-> node_1590533866628 node_1590533925799 5 node_1590533925799 -> node_2-> node_1590533925799 node_1590533942548 2 node_1590533942548 -> node_1590533866628-> node_1590533942548 node_1590533884803 0 node_1590533884803 -> node_1590533866628-> node_1590533884803 node_1590533924562 7 node_1590533924562 -> node_3->node_1590533924562 node_1590533932806 node_1590533932806 -> node_3->node_1590533932806

Красно-черные деревья

Красно-черное дерево — это еще один тип самобалансирующегося двоичного дерева поиска, но оно имеет некоторые дополнительные свойства по сравнению с деревьями AVL. Узлы окрашены в красный или черный цвет, чтобы помочь сбалансировать дерево после вставки или удаления. Они экономят ваше время благодаря балансировке. Итак, как мы раскрашиваем наши узлы?

  • Корень всегда черный
  • Два красных узла не могут быть смежными (т.е. красный родитель не может иметь красный дочерний элемент)
  • Путь от корня до листа должен содержать такое же количество черных узлов.
  • Нулевой узел черный
действительное красно-черное дерево

2-3 дерева

2-3 дерева сильно отличается от того, что мы узнали до сих пор. В отличие от двоичного Дерево поиска, дерево 2-3 — это самобалансирующееся, упорядоченное, многостороннее дерево поиска. Оно всегда идеально сбалансировано, поэтому каждый конечный узел находится на равном расстоянии от корня. Каждый узел, кроме конечных узлов, может быть двухуровневым. Узел (узел с одним элементом данных и двумя дочерними элементами) или 3 узла (узел с двумя элементами данных и тремя дочерними элементами). 2-3 дерева останутся сбалансированными независимо от того, сколько операций вставок или удалений происходит.

2-3-4 дерева

Дерево 2-3-4 — это дерево поиска, которое может вмещает больше ключей, чем 2-3 дерева. Он охватывает те же основные s как дерево 2-3, но добавляет следующие свойства:

  • 2-узел имеет два дочерних узла и один элемент данных.
  • 3- Узел имеет три дочерних узла и два элемента данных.
  • 4-узел имеет четыре дочерних узла и три элемента данных.
  • Каждый внутренний узел имеет не более 4 дочерних узлов
  • Для трех ключей во внутреннем узле все ключи в узле LeftChild меньше, чем левая клавиша
  • Все ключи в LeftMidChild меньше, чем средняя клавиша
  • Все ключи в RightMidChild меньше, чем правая клавиша
  • Все ключи в RightChild больше, чем правая клавиша

Сохранить обучение продолжается.

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

Алгоритмы для собеседований по программированию на Java

Введение в обход дерева и поиск

Чтобы использовать деревья, мы можем обходить их, посещая/проверяя каждый узел дерева. Если дерево «пройдено», это означает, что каждый узел был посещен. Есть четыре способа пересечь дерево. Эти четыре процесса делятся на две категории: обход в ширину или обход в глубину.

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

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

  • Postorder: Начните с левого поддерева и двигайтесь вправо поддерево. Затем перейдите к корневому узлу. Это обход в глубину.

  • Levelorder: Считайте это своего рода зигзагообразным узором. Это будет проходить по узлам по их уровням, а не по поддеревьям. Сначала мы посещаем корень и посещаем всех дочерних элементов этого корня слева направо. Затем мы переходим на следующий уровень, пока не дойдем до узла, у которого нет дочерних элементов. Это левый узел. Это обход в ширину.

Итак, в чем разница между в ширину и обход в глубину ? Давайте взглянем на алгоритмы поиска в глубину (DFS) и поиска на вдохе (BFS), чтобы лучше понять это.

Примечание: Алгоритмы — это последовательность инструкций для выполнения определенных задач. Мы используем алгоритмы со структурами данных для манипулирования нашими данными, в данном случае для просмотра наших данных.

Поиск в глубину

Обзор: Мы идем по пути с самого начала узел к конечному узлу, а затем начните другой путь, пока не будут посещены все узлы. Обычно это реализуется с использованием стеков и требует меньше памяти, чем BFS. Он лучше всего подходит для топографической сортировки, такой как отслеживание графика с возвратом или обнаружение цикла.

Шаги для алгоритма DFS следующие:

  1. Выберите узел. Вставьте все соседние узлы в стек.
  2. Извлеките узел из этого стека и вставьте соседние узлы в другой стек.
  3. Повторяйте, пока стек не станет пустым или вы не достигнете ваша цель. Посещая узлы, вы должны пометить их как посещенные , прежде чем продолжить, иначе вы застрянете в бесконечном цикле.

Поиск в ширину

Обзор: Мы проходим уровень за уровнем, чтобы посетить все узлы на одном уровне, прежде чем перейти к следующему. Алгоритм BFS обычно реализуется с использованием очередей и требует больше памяти, чем алгоритм DFS. Лучше всего найти кратчайший путь между двумя узлами.

Шаги для алгоритма BFS следующие:

  1. Выберите узел. Поместить все соседние узлы в очередь. Вывести узел из очереди и пометить его как посещенный. Поместите все соседние узлы в другую очередь.
  2. Повторяйте, пока очередь не станет пустой, так что вы не достигли своей цели.
  3. При посещении узлов вы должны пометить их как посещено перед продолжением, иначе вы застрянете в бесконечном цикле.

Поиск в деревьях двоичного поиска

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

  1. Начать с корня.
  2. Если значение меньше значения текущего узла, мы проходим через левое поддерево. Если больше, мы проходим правое поддерево.
  3. Продолжайте этот процесс, пока не достигнете node с этим значением или не дойдете до листа node , что означает, что значение не существует.

В приведенном ниже примере мы ищем значение 3 в нашем дереве. Взгляните.

xml version = «1.0» encoding = «UTF-8» standalone = «no»?> % 0 node_1 5 node_2 2 node_2 -> node_1-> node_2 node_3 16 node_3 -> node_1-> node_3 node_1590535054185 -4 node_1590535054185 -> node_2-> node_1590535054185 node_1590534997460 3 node_1590534997460 -> node_2-> node_1590534997460
Вот наше дерево. Поскольку 3 меньше 5, мы обходим левое поддерево.
xml version = «1.0» encoding = «UTF-8» standalone = «no»?> % 0 node_1 5 node_22 node_2 -> node_1-> node_2 node_3 16 node_3 -> node_1-> node_3 node_1590535054185 -4 node_1590535054185 -> node_2-> node_1590535054185 node_1590534997460 3 node_1590534997460 -> node_2->node_1590534997460
Поскольку 3 больше 2, мы переходим к правому дочернему элементу.
xml version = «1.0» encoding = «UTF-8» standalone = «no»?> % 0 node_1 5 node_2 2 node_2 -> node_1-> node_2 node_3 16 node_3 -> node_1- > node_3 node_1590535054185 -4 node_1590535054185 -> node_2-> node_1590535054185 node_1590534997460 3 node_1590534997460 -> node_2-> node_1590534997460
Искомое значение найдено.

Давайте теперь посмотрим на это в коде Java!

 публичный класс BinarySearchTree {… публичный логический поиск (значение int) {if (root ==  null) вернуть false;  иначе вернуть root.search (значение);  }} открытый класс BSTNode {… открытый логический поиск (значение типа int) {if (value == this.value) return true;  иначе, если (значение  this.value) {if (right == null) return false;  иначе return right.search (значение);  } return false;  }} 

Заключение и следующие шаги

Поздравляем, вы сделали следующий шаг в мир Java и структур данных. Тем не менее, есть еще много вопросов для собеседований и структур данных, которые нужно практиковать.

Вот некоторые из распространенных проблем со структурами данных, на которые следует обратить внимание, чтобы лучше понять, как использовать деревья:

  • Найти минимальное значение дерева двоичного поиска
  • Найти предков данного узла в дереве двоичного поиска
  • Найдите высоту двоичного дерева.
  • Найдите узлы на расстоянии «k» от корня
  • и т.д.

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

Этот курс познакомит вас со всеми основами информатики доступным и персонализированным способом.

Продолжить чтение о структурах данных

  • 8 структур данных, которые должен знать каждый программист Python
  • Основные структуры данных и A алгоритмы, которые должен знать каждый разработчик.
  • Подготовка к собеседованию по Java: 15 вопросов к собеседованию по Java
Оцените статью
nanomode.ru
Добавить комментарий