Реализуйте бинарное дерево поиска Fast AF

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

Чтобы реализовать BST в Swift, нам сначала нужно создать класс узла, который будет представлять каждый элемент в дереве. Каждый узел должен иметь значение и ссылку на его левый и правый потомки. Мы можем сделать это, создав класс Node с тремя свойствами:

class Node {
  var value: Int
  var left: Node?
  var right: Node?

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

Далее нам нужно создать класс BST, который будет хранить корневой узел дерева и предоставлять методы для вставки и поиска элементов. Мы можем сделать это, создав класс под названием «BinarySearchTree» с двумя методами: «insert» и «search».

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

class BinarySearchTree {
  var root: Node?

  func insert(value: Int) {
    let newNode = Node(value: value)

    if root == nil {
      root = newNode
      return
    }

    var currentNode = root
    while currentNode != nil {
      if value < currentNode!.value {
        if currentNode?.left == nil {
          currentNode?.left = newNode
          return
        }
        currentNode = currentNode?.left
      } else {
        if currentNode?.right == nil {
          currentNode?.right = newNode
          return
        }
        currentNode = currentNode?.right
      }
    }
  }

Метод «поиск» примет значение и вернет логическое значение, указывающее, присутствует ли значение в дереве. Мы можем сделать это, пройдя по дереву аналогично методу вставки. Если значение найдено, мы возвращаем «true». Если мы достигаем конечного узла и значение не найдено, мы возвращаем «false».

func search(value: Int) -> Bool {
    var currentNode = root
    while currentNode != nil {
      if value < currentNode!.value {
        currentNode = currentNode?.left
      } else if value > currentNode!.value {
        currentNode = currentNode?.right
      } else {
        return true
      }
    }
    return false
  }
}

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

let bst = BinarySearchTree()
bst.insert(value: 5)
bst.insert(value: 3)
bst.insert(value: 7)
bst.insert(value: 2)