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

Определение:

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

Оценка:

Поиск элемента (search)
- Время - O(log n)
- Память - O(log n)
Вставка элемента (insert)
- Время - O(log n)
- Память - O(log n)
Обновление значения элемента (update)
- Время - O(log n)
- Память - O(log n)
Удаление элемента (remove)
- Время - O(log n)
- Память - O(log n)

Код:

В следующем коде определены методы для работы с двоичным деревом поиска (Binary Search Tree, BST).

Основные публичные методы, определенные в extension для Dictionary[A], включают:

insert(key: String, value: A): Dictionary[A] - Вставляет новую пару ключ-значение в дерево.
searchKey(key: String): Option[A] - Ищет значение по ключу. Если ключ найден, возвращает Some(value), иначе - None.
updateValue(key: String, value: A): Dictionary[A] - Обновляет значение по ключу. Если ключ не найден, он вставляет новую пару ключ-значение.
remove(key: String): Dictionary[A] - Удаляет пару ключ-значение по ключу. Если ключ не найден, дерево остается неизменным.

object BinarySearchTree:
  opaque type Dictionary[A] = BinaryTree[(String, A)]

  def empty[A]: Dictionary[A] = Leaf

  extension [A](dict: Dictionary[A])
    def insert(key: String, value: A): Dictionary[A] =
      dict match
        case Leaf =>
          Branch((key, value), Leaf, Leaf)
        case Branch((k, v), lb, rb) if key < k =>
          Branch((k, v), lb.insert(key, value), rb)
        case Branch((k, v), lb, rb) if key > k =>
          Branch((k, v), lb, rb.insert(key, value))
        case _ => dict

    def searchKey(key: String): Option[A] =
      dict match
        case Leaf                             => None
        case Branch((k, _), lb, _) if key < k => lb.searchKey(key)
        case Branch((k, _), _, rb) if key > k => rb.searchKey(key)
        case Branch((_, v), _, _)             => Some(v)

    def updateValue(key: String, value: A): Dictionary[A] =
      dict match
        case Leaf => Branch((key, value), Leaf, Leaf)
        case Branch((k, v), lb, rb) if key < k =>
          Branch((k, v), lb.updateValue(key, value), rb)
        case Branch((k, v), lb, rb) if key > k =>
          Branch((k, v), lb, rb.updateValue(key, value))
        case Branch((_, _), lb, rb) =>
          Branch((key, value), lb, rb)

    def remove(key: String): Dictionary[A] =
      dict match
        case Leaf => Leaf
        case Branch((k, v), lb, rb) if key < k =>
          Branch((k, v), lb.remove(key), rb)
        case Branch((k, v), lb, rb) if key > k =>
          Branch((k, v), lb, rb.remove(key))
        case Branch((_, _), lb, rb) =>
          if lb.size >= rb.size then
            lb.popMax.map { case (item, dict) =>
              Branch(item, dict, rb)
            }.getOrElse(Leaf)
          else
            rb.popMin.map { case (item, dict) =>
              Branch(item, lb, dict)
            }.getOrElse(Leaf)

    private def popMax: Option[((String, A), Dictionary[A])] = dict match
      case Leaf                     => None
      case Branch((k, v), lb, Leaf) => Some(((k, v), lb))
      case Branch((k, v), lb, rb) =>
        rb.popMax.map { case (item, dict) =>
          (item, Branch((k, v), lb, dict))
        }

    private def popMin: Option[((String, A), Dictionary[A])] = dict match
      case Leaf                     => None
      case Branch((k, v), Leaf, rb) => Some(((k, v), rb))
      case Branch((k, v), lb, rb) =>
        lb.popMin.map { case (item, dict) =>
          (item, Branch((k, v), dict, rb))
        }
  end extension
end BinarySearchTree

Методы двоичного дерева

Код:

В следующем коде есть несколько методов, которые "наследуются" от двоичного дерева.

object BinarySearchTree:  
  extension [A](dict: Dictionary[A])    
    def isEmpty: Boolean = dict.isEmpty

    def size: Int = dict.size

    def height: Int = dict.height

end BinarySearchTree

Параметры дерева поиска

Код:

В следующем коде есть несколько методов, которые работают с бинарными деревьями и словарями, основанными на этих деревьях.

isValid - метод проверяет, является ли Dictionary валидным двоичным деревом поиска. Он проверяет, что для каждого узла все ключи в левом поддереве меньше ключа узла, а все ключи в правом поддереве больше ключа узла.
isBalanced - Этот метод проверяет, является ли Dictionary сбалансированным двоичным деревом. Он проверяет, что для каждого узла разница высот левого и правого поддеревьев не более 1, и рекурсивно проверяет левое и правое поддеревья.

object BinarySearchTree:  
  extension [A](dict: Dictionary[A])    
    def isValid: Boolean = dict match
      case Leaf                       => true
      case Branch((_, _), Leaf, Leaf) => true
      case Branch((key, _), Leaf, rb @ Branch((keyR, _), _, _)) =>
        key <= keyR && rb.isValid
      case Branch((key, _), lb @ Branch((keyL, _), _, _), Leaf) =>
        key >= keyL && lb.isValid
      case Branch(
            (key, _),
            lb @ Branch((keyL, _), _, _),
            rb @ Branch((keyR, _), _, _)
          ) =>
        key >= keyL && key <= keyR && lb.isValid && rb.isValid

    def isBalanced: Boolean = dict match
      case Leaf => true
      case Branch((_, _), lb, rb) =>
        math.abs(lb.height - rb.height) <= 1 && lb.isBalanced && rb.isBalanced
  end extension
end BinarySearchTree

Ссылки: