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

Как правило, первый узел называется родительским узлом, а дети — левым и правым наследниками.

Пример структуры дерева в котором кажды узел имеет 0, 1 и 2 детей. Элементы структуры: root — корень, узел расположенные в верхней части дерева, левые и правые ветки дерева — узлы (nodes), если узел не имеет дочерних элементов он называется конченым (leaf).

Один из способов представления узла является использование класса (пример):

class Node {
  var value: T
  var leftChild: Node?
  var rightChild: Node?

  init(value: T) {
    self.value = value
  }
}

Каждый узел содержит некоторые данные (value) и имеет левого и правого ребенка (leftChild, rightChild).

Одной из основных идей Swift является использование типов значений struct и enum вместо ссылочных типов (например, class). Вариант для создания структуры двоичного дерева это использовать тип enum.

enum — перечисление (enumeration) в Swift определяет общий тип для группы связанных значений. Сами объединённые в перечисление значения могут представлять любой тип — число, строку и так далее. Каждое отдельное значение в перечислении указывается после оператора case.

Структура дерева поиска

enum BinaryTree {
  case empty
  indirect case node(BinaryTree, T, BinaryTree)
}

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

Пример моделирования серии вычислений с использованием бинарного дерева (5 * (a — 10)) + (-4 * (3 / b)).

// leaf nodes
let node5 = BinaryTree.node(.empty, "5", .empty)
let nodeA = BinaryTree.node(.empty, "a", .empty)
let node10 = BinaryTree.node(.empty, "10", .empty)
let node4 = BinaryTree.node(.empty, "4", .empty)
let node3 = BinaryTree.node(.empty, "3", .empty)
let nodeB = BinaryTree.node(.empty, "b", .empty)

// intermediate nodes on the left
let aminus10 = BinaryTree.node(nodeA, "-", node10)
let timesLeft = BinaryTree.node(node5, "*", aminus10)

// intermediate nodes on the right
let minus4 = BinaryTree.node(.empty, "-", node4)
let divide3andB = BinaryTree.node(node3, "/", nodeB)
let timesRight = BinaryTree.node(minus4, "*", divide3andB)

// root node
let tree = BinaryTree.node(timesLeft, "+", timesRight)

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

CustomStringConvertible — это протокол в Swift, который позволяет пользовательскому типу представлять себя в виде строки. Этот протокол требует реализации вычисленного свойства под названием «description», которое возвращает строку, представляющую объект.

extension BinaryTree: CustomStringConvertible {
  var description: String {
    switch self {
    case let .node(left, value, right):
      return "value: \(value), left = [" + left.description + "], right = [" + right.description + "]"
    case .empty:
      return ""
    }
  }
}

//print the tree
print(tree)

// Вывод в консоли:
// value: +, left = [value: *, left = [value: 5, left = [], right = []], right = [value: -, left = [value: a, left = [], right = []], right = [value: 10, left = [], right = []]]], right = [value: *, left = [value: -, left = [], right = [value: 4, left = [], right = []]], right = [value: /, left = [value: 3, left = [], right = []], right = [value: b, left = [], right = []]]]

Еще одной полезной функцией является возможность получить количество узлов (node counter) в дереве:

enum BinaryTree { // enum declarartion
    // states
    case empty
    indirect case node(BinaryTree, T, BinaryTree) //the parameter types inside the brackets correspond to the left child, value, and the right child, respectively
    
    // node counter
    var count: Int {
        switch self {
        case let .node(left, _, right):
            return left.count + 1 + right.count
        case .empty:
            return 0
        }
    }

// node counter
print(tree.count, "узлов в дереве")

Вставка

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

Пример допустимого дерева бинарного поиска

Вставка выполняется с корневого узла (root) в качестве текущего. Правила вставки значений:

• Если текущий узел пуст, создается новый узел (значение вставляется в новый узел)
• Если новое значение меньше выполняется переход вниз по левой ветке дерева
• Если новое значение больше выполняется переход вниз по правой ветке

Всегда существует только одно возможное место, куда можно вставить новый элемент в дереве. Поиск этого места обычно происходит довольно быстро. Это занимает O(n) времени, где n — количество узлов в дереве.

Реализация вставки:

// Добавляем метод вставки нового значения в дерево. Типы значений по умолчанию неизменяемы. Если вы создаете метод, который пытается изменить что-либо в типе значения, вам нужно явно указать это, добавив ключевое слово mutating перед вашим методом. 
mutating func naiveInsert(newValue: T) {
  // Используется инструкция guard для отображения левого дочернего элемента, текущего значения и правого дочернего элемента текущего узла. Если этот узел пуст, то функция guard завершится.
  guard case .node(var left, let value, var right) = self else {
    // В этом блоке поле self пусто. Здесь выполняется вставтка нового значения.
    self = .node(.empty, newValue, .empty)
    return 
  }
 
  // Алгоритм вставки
  if newValue < value {
   left.naiveInsert(newValue: newValue)
  } else {
   right.naiveInsert(newValue: newValue)
 }
}

Для реализации алгоритма вставки необходимо внести изменения в структуру дерева поиска:

enum MyNewBinaryTree(T: Comparable) { // Вместо () используютcя < > !!! 
  // Код внутри не меняется
}

Comparable protocol в Swift используется для определения порядка сортировки экземпляров типа. Для реализации этого протокола требуется реализовать одну операторную функцию под названием <, которая возвращает Bool, указывающую на то, следует ли считать первое значение меньшим второго. Благодаря реализации Comparable тип может использоваться в качестве ключа в словаре или элемента в отсортированном массиве. Протокол также предоставляет реализации по умолчанию для операторов ==, >, >=, <= и !=, которые основаны на реализации оператора <.

Метод, который возвращает новое дерево со вставленным элементом, выглядит так:

enum MyNewBinaryTree(T: Comparable) { // enum declarartion (Вместо () используютcя < > !!!)
    // states
    case empty
    indirect case node(MyNewBinaryTree, T, MyNewBinaryTree) //the parameter types inside the brackets correspond to the left child, value, and the right child, respectively
    
    private func newTreeWithInsertedValue(newValue: T) -> MyNewBinaryTree {
      switch self {
      // Если дерево пусто, вставка значения выполняется в root
      case .empty:
        return .node(.empty, newValue, .empty)
      // Если дерево не пустое, вставка значения выполняется или в левый или правый дочерний элемент
      case let .node(left, value, right):
        if newValue < value {
          return .node(left.newTreeWithInsertedValue(newValue: newValue), value, right)
        } else {
          return .node(left, value, right.newTreeWithInsertedValue(newValue: newValue))
        }
      }
    }
    
    mutating func insert(newValue: T) {
        self = newTreeWithInsertedValue(newValue: newValue)
    }
}

extension MyNewBinaryTree: CustomStringConvertible {
    var description: String {
        switch self {
        case let .node(left, value, right):
            return "value: \(value), left = [" + left.description + "], right = [" + right.description + "]"
        case .empty:
            return ""
        }
    }
}

var binaryTree: MyNewBinaryTree = .empty
binaryTree.insert(newValue: 5) // Первое значение в дереве (root)
binaryTree.insert(newValue: 7)
binaryTree.insert(newValue: 9)

print(binaryTree)

Каждый раз, когда выполняется вставка, необходимо создание новой копии дерева. Новая копия требует просмотр всех узлов предыдущего дерева, что приводит к временной сложности метода вставки O(n).

Средняя временная сложность реализации бинарного дерева поиска с использованием классов составляет O(log n). Использование классов (ссылок) не приводит к копированию дерева при записи новых значений (вставка выполняется без создания полной копии дерева).

Алгоритм обхода (Traversal algorithms)

Способы обхода бинарного дерева:

• Обход по порядку (In-order Traversal) Алгоритм прохождения по узлам в порядке возрастания.
  

enum MyNewBinaryTree(T: Comparable) { // enum declarartion (Вместо () используютcя < > !!!)
    // states
    case empty
    indirect case node(MyNewBinaryTree, T, MyNewBinaryTree) //the parameter types inside the brackets correspond to the left child, value, and the right child, respectively
    
    private func newTreeWithInsertedValue(newValue: T) -> MyNewBinaryTree {
      switch self {
      // Если дерево пусто, новое значение в root
      case .empty:
        return .node(.empty, newValue, .empty)
      // Если дерево не пустое, вставка значения выполняется или в левый или правый дочерний элемент
      case let .node(left, value, right):
        if newValue < value {
          return .node(left.newTreeWithInsertedValue(newValue: newValue), value, right)
        } else {
          return .node(left, value, right.newTreeWithInsertedValue(newValue: newValue))
        }
      }
    }
    
    mutating func insert(newValue: T) {
        self = newTreeWithInsertedValue(newValue: newValue)
    }
    
    // In-order Traversal
    func traverseInOrder(process: (T) -> ()) {
      switch self {
      // Если текущий узел пуст, то дальше спуститься невозможно
      case .empty:
        return
      // Обход по порядку заключается в том, чтобы спуститься по левой стороне, посетить узел, а затем по правой стороне
      case let .node(left, value, right):
        left.traverseInOrder(process: process)
        process(value)
        right.traverseInOrder(process: process)
      }
    }

}

extension MyNewBinaryTree: CustomStringConvertible {
    var description: String {
        switch self {
        case let .node(left, value, right):
            return "value: \(value), left = [" + left.description + "], right = [" + right.description + "]"
        case .empty:
            return ""
        }
    }
}

// Создание бинарного дерева поиска c использованием метода insert. Выполняется обход через все узлы в порядке возрастания, передавая значение в каждом узле в конечное замыкание. Внутри конечного замыкания выводится в консоль значение, которое было передано методом обхода. $0 - это сокращенный синтаксис, который ссылается на параметр, передаваемый в замыкание
var tree: MyNewBinaryTree = .empty
tree.insert(newValue: 7)
tree.insert(newValue: 10)
tree.insert(newValue: 2)
tree.insert(newValue: 1)
tree.insert(newValue: 5)
tree.insert(newValue: 9)

tree.traverseInOrder { print($0) }

// Вывод в консоли: 
// 1
// 2
// 5
// 7
// 9
// 10

• Предварительный обход (Pre-order Traversal) Алгоритм обхода деревьев, при котором сначала посещается корень дерева (root), затем левые узлы, и затем правые узлы.

// Post-order Traversal
    func traversePostOrder(process: (T) -> ()) {
        switch self {
        case .empty:
            return
        case let .node(left, value, right):
            left.traverseInOrder(process: process)
            right.traverseInOrder(process: process)
            process(value)
        }
    }

// Post-order Traversal result
print("Post-order Traversal result")
tree.traversePostOrder { print($0) }

// Вывод в консоль:
// Post-order Traversal result
// 1
// 2
// 5
// 9
// 10
// 7

Поиск

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

// Searching
    func search(searchValue: T) -> MyNewBinaryTree? {
        switch self {
        case .empty:
            return nil
        case let .node(left, value, right):
            // Если текущее значение совпадает с искомым, поиск завершен (возвращается текущий узел)
            if searchValue == value {
                return self
            }
            // Выполняется переход влево или вправо
            if searchValue < value {
                return left.search(searchValue: searchValue)
            } else {
                return right.search(searchValue: searchValue)
            }
        }
    }