[Перевод] GopherCon 2018: демистификация алгоритмов бинарного дерева поиска

• Оригинальный адрес:GopherCon 2018 - Demystifying Binary Search Tree Algorithms
• Оригинальный автор:Kaylyn Gibilterra
• Перевод с:Программа перевода самородков
• Постоянная ссылка на эту статью:GitHub.com/rare earth/gold-no…
• Переводчик:Changkun Ou
• Корректор:razertory

By Geoffrey Gilmore for the GopherCon Liveblog on August 30, 2018

Presenter: Kaylyn Gibilterra

Liveblogger: Geoffrey Gilmore

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

---

вводить

Кейлин провела последний год, пытаясь развлечься, внедряя различные алгоритмы. Может быть, эта штука для вас странная, но алгоритм для нее особенно странный. Особенно она ненавидела алгоритмы на уроках в колледже. Ее преподаватели часто преподают в сложных терминах и отказываются объяснять «очевидные» концепции. В результате она узнала только основы, которые помогли бы ей найти работу.

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

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

Алгоритмы обучения пугают

Этот снимок экрана взят из раздела «Двоичное дерево поиска» статьи «Введение в алгоритмы». Введение в алгоритмы считается библией книг по алгоритмам. По словам авторов, до 1989 года не было хорошего учебника по алгоритмам. Тем не менее, любой, кто читает «Введение в алгоритмы», может сказать, что оно было написано академически настроенными профессорами, чья основная аудитория и есть.

Приведу несколько примеров:

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

  • Что такое спутниковые данные
  • Что такое связанный список
  • Что такое предварительный и постпорядковый обход дерева?

  У вас нет возможности узнать, что это такое, если вы не будете делать заметки на каждой странице книги.

• Если вы похожи на Кейлин, первое, что вы увидите на этой странице, — посмотрите на код. Однако единственный код на странице объясняет только способ обхода бинарного дерева поиска, а не то, чем на самом деле является бинарное дерево поиска.

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

• У них есть область из двух предложений (выделенная зеленым прямоугольником), объясняющая, что такое алгоритм бинарного дерева поиска. Но оно скрыто в почти невидимом предложении и называется «свойством» бинарного дерева поиска, что очень сбивает с толку новичков.

в заключении:

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

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

угадайку

Это единственное, что вам нужно знать для остальной части разговора.

Это «игра в угадайку», в которую многие играли в детстве. Вы приглашаете своих друзей сыграть в угадывание определенного числа в определенном диапазоне (скажем, от 1 до 100). Тогда ваш друг может сказать «57». При нормальных обстоятельствах первая догадка будет неверной, но вы скажете им, слишком велика она или слишком мала. Затем он может продолжать угадывать, пока, наконец, не угадает правильно.

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

Правила для бинарных деревьев поиска

1. Каждый узел содержит уникальный ключ, который используется для сравнения различных размеров узлов. Ключ может быть любого типа: строковый, целочисленный и т.д.
2. Каждый узел имеет не более двух дочерних узлов
3. Значение узла меньше значения узла в правом поддереве
4. Значение узла больше значения узла левого поддерева
5. нет дубликатов ключей

Бинарное дерево поиска содержит три основные операции:

• найти
• вставлять
• Удалить

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

найти

GIF-изображение выше дает представление о породах деревьев.39пример.

Очень важным свойством бинарного дерева поиска является то, что значение узла в правом поддереве узла всегда больше значения самого узла, а значение узла в левом поддереве всегда меньше значения самого узла. как на картинке57Число справа всегда больше57, а левая часть всегда меньше57.

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

Что ж, мы знаем основы и можем приступать к написанию кода.

type Node struct {
    Key   int
    Left  *Node
    Right *Node
}

Базовая структура представляет собойstuct, если вы не использовалиstuct,structВ основном это можно интерпретировать как набор некоторых полей. Все, что вам нужно для этой структуры, этоKey(для сравнения других узлов),LeftиRightдочерний узел.

При определении узла вы можете использовать такие литералы, вы можете использовать такие литералы:

tree := &Node{Key: 6}

это создаетKeyза6изNode. вам может быть любопытноLeftиRightкуда оно делось. На самом деле все они инициализируются нулевым значением.

tree := &Node{
    Key:   6,
    Left:  nil,
    Right: nil,
}

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

Или укажите значение поля без имени поля:

tree := &Node{6, nil, nil}

В этом случае первым параметром являетсяKey, второйLeft, третий этоRight.

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

tree := &Node{6, nil, nil}
fmt.Println(tree.Key)

Теперь давайте реализуем алгоритм поискаSearch:

func (n *Node) Search(key int) bool {
    // 这是我们的基本情况。如果 n == nil，则 `key`
    // 在二叉查找树种不存在
    if n == nil {
        return false
    }
    if n.Key < key { // 向右走
        return n.Right.Search(key)
    }
    if n.Key > key { // 向左走
        return n.Left.Search(key)
    }
    // 如果 n.Key == key，就说明找到了
    return true
}

вставлять

На приведенном выше GIF-изображении показана вставка числа.81Например, вставка очень похожа на поиск. Мы хотим найти, где мы должны вставить81, поэтому начните поиск, а затем вставьте в нужное место.

func (n *Node) Insert(key int) {
    if n.Key < key {
        if n.Right == nil { // 我们找到了一个空位，结束！
            n.Right = &Node{Key: key}
            return
        }
        // 向右边找
        n.Right.Insert(key)
       	return
    } 
    if n.Key > key {
        if n.Left == nil { // 我们找到了一个空位，结束
            n.Left = &Node{Key: key}
            return
        } 
        // 向左边找
        n.Left.Insert(key)
    }
    // 如果 n.Key == key，则什么也不做
}

если ты не видел(n *Node)Синтаксис см. в описании приемников указателей здесь.

Удалить

GIF выше показывает удаление 78 видов деревьев.78Процесс поиска аналогичен предыдущему. В этом случае нужно только правильно78«Отрезать» нужного ребенка от дерева57Подключен к85Вот и все.

func (n *Node) Delete(key int) *Node {
    // 按 `key` 查找
    if n.Key < key {
        n.Right = n.Right.Delete(key)
        return n
    }
    if n.Key > key {
        n.Left = n.Left.Delete(key)   
        return n
    }

    // n.Key == `key`
    if n.Left == nil { // 只指向反向的节点
        return n.Right
    }
    if n.Right == nil { // 只指向反向的节点
        return n.Left
    }

    // 如果 `n` 有两个子节点，则需要确定下一个放在位置 n 的最大值
    // 使得二叉查找树保持正确的性质
    min := n.Right.Min()

    // 我们只使用最小节点来更新 `n` 的 key
    // 因此 n 的直接子节点不再为空
    n.Key = min
    n.Right = n.Right.Delete(min)
    return n
}

минимум

Если вы продолжите движение влево, вы найдете минимальное значение (на рисунке24)

func (n *Node) Min() int {
    if n.Left == nil {
        return n.Key
    }
    return n.Left.Min()
}

максимальное значение

func (n *Node) Max() int {
    if n.Right == nil {
        return n.Key
    }
    return n.Right.Max()
}

Если вы продвинетесь до упора вправо, то найдете максимальное значение (на рис.96).

модульный тест

Теперь, когда мы написали код для каждой из основных функций бинарного дерева поиска, давайте на самом деле протестируем наш код! Самая интересная часть практики тестирования: тестирование в Go проще, чем во многих других языках, таких как Python и C.

// 必须导入标准库
import "testing"

// 这个称之为测试表。它能够简单的指定测试用例来避免写出重复代码。
// 见 https://github.com/golang/go/wiki/TableDrivenTests
var tests = []struct {
    input  int
    output bool
}{
    {6, true},
    {16, false},
    {3, true},
}

func TestSearch(t *testing.T) {
    //     6
    //    /
    //   3
    tree := &Node{Key: 6, Left: &Node{Key: 3}}
    
    for i, test := range tests { 
        if res := tree.Search(test.input); res != test.output {
            t.Errorf("%d: got %v, expected %v", i, res, test.output)
        }
    }

}

Затем просто запустите:

> go test

Go запустит ваши тесты и выведет стандартный отформатированный результат, который сообщает вам, прошел ли тест, сообщение о том, что тест не пройден, и сколько времени занял тест.

Тестирование производительности

Подождите, все еще впереди! Go может сделать тестирование производительности очень кратким, все, что вам нужно, это:

import "testing"

func BenchmarkSearch(b *testing.B) {
    tree := &Node{Key: 6}

    for i := 0; i < b.N; i++ {
        tree.Search(6)
    }
}

b.Nбудет запускаться неоднократноtree.Search()получитьtree.Search()стабильные результаты работы.

Запустите тест с помощью следующей команды:

> go test -bench=

Вывод аналогичен:

goos: darwin
goarch: amd64
pkg: github.com/kgibilterra/alGOrithms/bst
BenchmarkSearch-4       1000000000               2.84 ns/op
PASS
ok      github.com/kgibilterra/alGOrithms/bst   3.141s

Все, на чем вам нужно сосредоточиться, это следующая строка:

BenchmarkSearch-4       1000000000               2.84 ns/op

Он показывает, насколько быстро выполняется ваша функция. В этой ситуации,test.Search()Время выполнения составляет около 2,84 наносекунд.

Теперь, когда вы можете просто запустить тесты производительности, пришло время приступить к некоторым экспериментам, таким как:

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

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

Примечание переводчика: временная сложность вставки, удаления и поиска в двоичном дереве поиска составляет O(log(n)), а в худшем случае — O(n); карта Go — это хеш-таблица, и мы знаем, что хеш-таблица Средняя временная сложность вставки, удаления и поиска составляет O (1), а в худшем случае — O (n); в то время как поиск среза в Go требует обхода среза, сложность — O (n), вставка и удаление необходимы, когда это необходимо. перераспределить память, что является худшим случаем O (n).

Терминология двоичного дерева поиска

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

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

Высота дерева на рисунке5.

Глубина узла: количество ребер от корневого узла до узла.

48глубина2.

полное бинарное дерево: Каждый нелистовой узел содержит два дочерних узла.

полное бинарное дерево: Каждый слой узлов полностью заполнен.Если последний слой не заполнен, отсутствуют только несколько узлов справа.

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

Представьте, что вы смотрите на это дерево47, вы можете видеть, что поиск занимает семь шагов, а поиск24Это занимает всего три шага, и эта проблема становится более серьезной по мере увеличения «дисбаланса». Решение состоит в том, чтобы сделать дерево сбалансированным:

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

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

Контакты

Twitter: @kgibilterra Email: kgibilterra@gmail.com

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

---

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