[Перевод] Структуры данных Golang: деревья

Go Программа перевода самородков

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

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

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

маленькая теория

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

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

Для вашего удовольствия, вот определение древовидной структуры из Википедии:

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

Это определение означает, что дерево — это просто набор узлов (или вершин) и ребер (или соединений между узлами), и оно не содержит циклов.

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

Если мы разорвем ребро между узлами F и E и добавим узел G, соединяющий G и F ребром, мы получим такую ​​структуру:

Теперь, поскольку мы устранили циклы в графе, мы можем сказать, что теперь у нас есть правильная древовидная структура. У него есть буква А, называемаякорневой узел, всего 7узел. Узел А имеет 3дочерний узел(B, D и F) и узлы на один слой ниже этих узлов (C, E и G соответственно). Следовательно, узел А имеет 6потомок узла. Кроме того, это дерево имеет 3 листовых узла (C, E и G), или они называются узлами без потомков.

Что общего у узлов B, D и F? Поскольку у них один и тот же родительский узел (узел A), ониродственный узел. Все они находятся на первом уровне, потому что каждому из них требуется только один шаг, чтобы достичь корневого узла. Например, узел G находится на втором уровне, потому что путь от G до AдорожкаДля: G -> F -> A нам нужно пройти два ребра, чтобы достичь узла A.

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

Моделирование HTML-документов

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

Серьезно, иди проверь, я буду ждать здесь. . .

Браузеры имеют нечто встроенное, называемое DOM — кросс-платформенный, независимый от языка интерфейс прикладного программирования, который обрабатывает эти веб-документы как древовидную структуру, где каждый узел представляет собой объект, представляющий часть документа. Это означает, что когда браузер читает код HTML в вашем документе, он загружает документ и создает на его основе модель DOM.

Итак, давайте на мгновение представим, что мы разработчики браузеров Chrome или Firefox и нам нужно смоделировать DOM. Что ж, чтобы немного облегчить это упражнение, давайте посмотрим на небольшой HTML-документ:

<html>
  <h1>Hello, World!</h1>
  <p>This is a simple HTML document.</p>
</html>

Итак, если бы мы смоделировали этот документ как древовидную структуру, он выглядел бы так:

Теперь мы можем рассматривать текстовые узлы как отдельныеNode, но для простоты можно предположить, что любой элемент HTML может содержать текст.

htmlУ узла будет два дочерних узла,h1иpузлы, которые содержат поляtag,textиchildren. Давайте поместим это в код:

type Node struct {
    tag      string
    text     string
    children []*Node
}

ОдинNodeНеобязательными будут только имя метки и дочерние узлы. Давайте пройдемся по тому, что мы видим вышеNodetree, чтобы попробовать создать этот HTML-документ самостоятельно:

func main() {
        p := Node{
                tag:  "p",
                text: "This is a simple HTML document.",
                id:   "foo",
        }

        h1 := Node{
                tag:  "h1",
                text: "Hello, World!",
        }

        html := Node{
                tag:      "html",
                children: []*Node{&p, &h1},
        }
}

Это выглядит нормально, у нас есть базовая древовидная структура и она работает.

Build MyDOM - простая замена DOM 😂

Теперь, когда у нас есть древовидная структура, давайте вернемся назад и посмотрим, что делает DOM. Например, если бы MyDOM(TM) использовался вместо DOM в реальной среде, мы должны были бы иметь доступ к его узлам и модифицировать их с помощью JavaScript.

Самый простой способ сделать это с помощью JavaScript — использовать следующий код

document.getElementById('foo')

Эта функция будет вdocumentНайдите в дереве сfooУзел как идентификатор. Давайте обновим нашNodeструктуру для большей функциональности, затем напишите функцию запроса для нашей древовидной структуры:

type Node struct {
  tag      string
  id       string
  class    string
  children []*Node
}

Теперь каждый из нашихNodeструктура будет иметьtag,children, что указывает наNodeсрез указателей на дочерние узлы,idпредставляет идентификатор в этом узле DOM,classОтносится к классу, который можно применить к этому узлу DOM.

Теперь вернемся к нашему предыдущемуgetElementByIdфункция запроса. как это сделать. Во-первых, давайте построим древовидную структуру, которую можно использовать для проверки нашего алгоритма запроса:

<html>
  <body>
    <h1>This is a H1</h1>
    <p>
      And this is some text in a paragraph. And next to it there's an image.
      <img src="http://example.com/logo.svg" alt="Example's Logo"/>
    </p>
    <div class='footer'>
      This is the footer of the page.
      <span id='copyright'>2019 &copy; Ilija Eftimov</span>
    </div>
  </body>
</html>

Это очень сложный HTML-документ. давайте использоватьNodeПредставьте его структуру в виде структуры на языке Go:

image := Node{
        tag: "img",
        src: "http://example.com/logo.svg",
        alt: "Example's Logo",
}

p := Node{
        tag:      "p",
        text:     "And this is some text in a paragraph. And next to it there's an image.",
        children: []*Node{&image},
}

span := Node{
        tag:  "span",
        id:   "copyright",
        text: "2019 &copy; Ilija Eftimov",
}

div := Node{
        tag:      "div",
        class:    "footer",
        text:     "This is the footer of the page.",
        children: []*Node{&span},
}

h1 := Node{
        tag:  "h1",
        text: "This is a H1",
}

body := Node{
        tag:      "body",
        children: []*Node{&h1, &p, &div},
}

html := Node{
        tag:      "html",
        children: []*Node{&body},
}

Мы начинаем строить эту древовидную структуру снизу вверх. Это означает построение структуры от самой глубоко вложенной структуры доbodyиhtmlузел. Давайте посмотрим на график этой древовидной структуры:

Реализовать запрос узла 🔎

Давайте перейдем к нашей цели сделать JavaScript доступным в нашемdocumentвызыватьgetElementByIdи найти то, что он хочет найтиNode.

Для этого нам нужно реализовать алгоритм запроса дерева. Наиболее популярными методами поиска (или обхода) графовых и древовидных структур являются поиск в ширину (BFS) и поиск в глубину (DFS).

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

Как следует из названия, метод обхода, принятый BFS, сначала будет учитывать «ширину» исследовательского узла, а затем «глубину». Ниже приведена визуальная диаграмма алгоритма BFS, проходящего через всю древовидную структуру:

Как видите, сначала алгоритм выполняет два шага в глубину (черезhtmlиbodyузел), затем он проходитbodyВсе детские узлы, наконец, перейдите к следующему слою для доступаspanиimgузел.

Если вам нужны пошаговые инструкции, это будет:

  1. мы начинаем с корняhtmlУзел начинается
  2. мы подталкиваем его кqueue
  3. Мы начинаем входить в цикл, еслиqueueНе пустой, этот цикл будет работать вечно
  4. мы проверяемqueueСоответствует ли следующий элемент запросу. Если есть совпадение, мы возвращаемся к узлу, и все кончено.
  5. Когда совпадений не найдено, мы помещаем всех дочерних элементов проверяемого узла в очередь, чтобы их можно было проверить позже.
  6. GOTOчетвертый шаг

Давайте взглянем на простую реализацию этого алгоритма в Go, и я поделюсь некоторыми советами о том, как легко запомнить алгоритм.

func findById(root *Node, id string) *Node {
        queue := make([]*Node, 0)
        queue = append(queue, root)
        for len(queue) > 0 {
                nextUp := queue[0]
                queue = queue[1:]
                if nextUp.id == id {
                        return nextUp
                }
                if len(nextUp.children) > 0 {
                        for _, child := range nextUp.children {
                                queue = append(queue, child)
                        }
                }
        }
        return nil
}

Этот алгоритм имеет 3 ключевых момента:

  1. queue- он будет содержать все узлы, посещенные алгоритмом
  2. Получатьqueueпервый элемент в , проверьте, соответствует ли он, если узел не соответствует, перейдите к следующему узлу
  3. viewingqueueпоместите все дочерние элементы узла перед следующим элементомпоставить в очередь.

По сути, весь алгоритм реализован вокруг добавления дочерних узлов в очередь и обнаружения узлов, которые уже находятся в очереди. Конечно, если мы все еще не находим совпадения в конце очереди, мы возвращаемсяnilвместо того, чтобы указывать наNodeуказатель.

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

Для полноты картины давайте посмотрим, как работает DFS.

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

Давайте посмотрим, как это выглядит:

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

Алгоритм начинается точно так же, как BFS — он начинается сhtmlприбытьbodyсноваdivузел. Тогда, напротив, алгоритм не продолжает обход до тех пор, покаh1узел, он переходит к листовому узлуspanОдин шаг вперед. как только он найдетspanявляется листовым узлом, он вернетdivузел, чтобы найти другие ветки для изучения. Так какdivтоже не может быть найден, поэтому он возвращаетсяbodyузел, в этом узле он находит новую ветку, он посетит ветку вh1узел. Затем он продолжит те же шаги, что и раньше — возвратbodyЗатем узел обнаруживает, что есть еще одна ветвь для изучения — в конечном итоге посещаяpиimgузел.

Если вам интересно, "как мы вернемся к родителю без указателя на родителя", то вы забыли один из старейших приемов в книге - рекурсию. Давайте посмотрим на простую рекурсивную реализацию этого алгоритма в Go:

func findByIdDFS(node *Node, id string) *Node {
        if node.id == id {
                return node
        }

        if len(node.children) > 0 {
                for _, child := range node.children {
                        findByIdDFS(child, id)
                }
        }
        return nil
}

Поиск по названию класса 🔎

Еще одна функция, которой должен обладать MyDOM™, — это поиск узлов по имени класса. По сути, когда скрипт JavaScript выполняетсяgetElementsByClassName, MyDOM должен уметь собирать все узлы с определенным именем класса.

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

Для простоты давайте сначала реализуемNodeметод построения, называемыйhasClass:

func (n *Node) hasClass(className string) bool {
        classes := strings.Fields(n.classes)
        for _, class := range classes {
                if class == className {
                        return true
                }
        }
        return false
}

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

type testcase struct {
        className      string
        node           Node
        expectedResult bool
}

func TestHasClass(t *testing.T) {
        cases := []testcase{
                testcase{
                        className:      "foo",
                        node:           Node{classes: "foo bar"},
                        expectedResult: true,
                },
                testcase{
                        className:      "foo",
                        node:           Node{classes: "bar baz qux"},
                        expectedResult: false,
                },
                testcase{
                        className:      "bar",
                        node:           Node{classes: ""},
                        expectedResult: false,
                },
        }

        for _, case := range cases {
                result := case.node.hasClass(test.className)
                if result != case.expectedResult {
                        t.Error(
                                "For node", case.node,
                                "and class", case.className,
                                "expected", case.expectedResult,
                                "got", result,
                        )
                }
        }
}

Как вы видете,hasClassфункция проверитNodeНаходится ли имя класса в списке имен классов. Теперь давайте перейдем к завершению реализации MyDOM, найдя все совпадения по имени класса.Node.

func findAllByClassName(root *Node, className string) []*Node {
        result := make([]*Node, 0)
        queue := make([]*Node, 0)
        queue = append(queue, root)
        for len(queue) > 0 {
                nextUp := queue[0]
                queue = queue[1:]
                if nextUp.hasClass(className) {
                        result = append(result, nextUp)
                }
                if len(nextUp.children) > 0 {
                        for _, child := range nextUp.children {
                                queue = append(queue, child)
                        }
                }
        }
        return result
}

Алгоритм кажется знакомым? Это потому, что вы смотрите на модифицированныйfindByIdфункция.findAllByClassNameкак это работает иfindByIdАналогично, но вместо возврата сразу после того, как совпадение найдено, он возвращает совпавшееNodeдобавить вresultв ломтиках. Это будет продолжаться до тех пор, пока всеNode.

Если совпадений не найдено, тоresultСрез будет пуст. Если какие-либо из них совпадают, они будут использоваться какresultЧасть возвращенной.

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

удалить узел 🗑

Еще одна функция, которая часто используется в Dom, — это удаление узлов. Точно так же, как это может сделать DOM, наша MyDOM(TM) тоже должна это делать.

Самый простой способ сделать это в Javascript:

var el = document.getElementById('foo');
el.remove();

Хотя нашdocumentзнать, как с этим боротьсяgetElementById(позднее по телефонуfindById), но нашNodeне знаю, как обращаться сremoveфункция. Удалено из MyDOM(TM)NodeПотребуются два шага:

  1. мы нашлиNodeродительский узел, а затем удалить его из набора дочерних узлов родительского узла;
  2. Если вы хотите удалитьNodeЕсть дочерние узлы, и мы должны удалить эти дочерние узлы из DOM. Это означает, что мы должны удалить все указатели на эти дочерние узлы и их родительские узлы (то есть удаляемый узел), чтобы сборщик мусора в Go мог освободить занятую память.

Вот простой способ добиться вышеизложенного:

func (node *Node) remove() {
        // Remove the node from it's parents children collection
        for idx, sibling := range n.parent.children {
                if sibling == node {
                        node.parent.children = append(
                                node.parent.children[:idx],
                                node.parent.children[idx+1:]...,
                        )
                }
        }

        // If the node has any children, set their parent to nil and set the node's children collection to nil
        if len(node.children) != 0 {
                for _, child := range node.children {
                        child.parent = nil
                }
                node.children = nil
        }
}

Один*Nodeбудет иметьremoveфункция, которая выполняет два шага, описанных выше, для достиженияNodeудалить операцию.

На первом этапе мы преобразуем этот узел изparentУзел вынимается из списка дочерних узлов узла, и узел удаляется путем обхода этих дочерних узлов, слияния элементов до и после узла для формирования нового списка.

На втором шаге, проверив, есть ли у этого узла дети, мыparentЦитата удалена, тогда ставьте этуNodeПоле дочернего узла имеет значениеnil.

что дальше?

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

Если вы хотите использовать нашу древовидную структуру и написать для нее дополнительные функции, вы можете посетить JavaScript HTML DOM WC3.ДокументацияЗатем рассмотрите возможность добавления дополнительных функций в MyDOM.

Очевидно, что цель этой статьи — дать вам больше узнать о древовидной (графовой) структуре и понять современные популярные алгоритмы поиска/обхода. Тем не менее, пожалуйста, продолжайте изучать и практиковаться в любом случае, и оставьте комментарий под статьей, если есть какие-либо улучшения в вашей реализации MyDOM.

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

Программа перевода самородковэто сообщество, которое переводит высококачественные технические статьи из ИнтернетаНаггетсДелитесь статьями на английском языке на . Охват контентаAndroid,iOS,внешний интерфейс,задняя часть,блокчейн,продукт,дизайн,искусственный интеллектЕсли вы хотите видеть более качественные переводы, пожалуйста, продолжайте обращать вниманиеПрограмма перевода самородков,официальный Вейбо,Знай колонку.

Категории