# Balanced Search Trees

## 2−3 Search Trees

* Могут иметь 2 ветки как в BST
* Могут иметь 3 ветки: меньше, больше и между, соотв. в ноде будет не одно значение, а 2 (от и до)
* Добавление происходит путем добавление нод и реструктуризацией кт. приводит к балансировке дерева
* Интересно само по себе как академическое понятие ибо на практике сложно реализовать, зато реализация в виде Red-Black Tree на основе BST гораздо проще, понятнее и в целом, кажется, что "2−3 Search Trees" это обобщение способа балансировки (т.е. оно важно как понятие, а не практическая модель), после которой вернулись обратно к BST c балансировкой по принципу Red-Black Tree.

## Red-Black BST

* Практическая реализация 2−3 Search Tree
* Построенная на BST с окрашиванием связей. Могут быть красные и черные
* На основе цвета и осуществляется балансировка BST
* Есть принцип left-leaning Red-Black Tree, что означает, что красным должна быть либо связь с родителем либо с левой нодой. Если это не так - то путем вращения нужно приводить дерево к ситуации left-leaning, что в свою очередь просто балансирует само BST
* Добавление ноды производится по принципу BST, с последующей балансировкой (вращением) относительно красной связи
* Удаление...

![\* коэф. стремится к 1](https://4251836425-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lnd5skvXnyJUQsGuNMc%2F-MkKvpuOXdL-behmngNn%2F-MkKwXm9wkwtAJwH5tA1%2Fimage.png?alt=media\&token=7ffc6a6a-00ef-401f-beea-9e885a47f908)

## B-trees

* Links: [habr.com](https://habr.com/ru/post/114154/), [https://levelup.building-a-b-tree-in-javascript, structies](https://structies.firebaseapp.com/#/structure/tree/b-tree)
* Отлично применяется для индексов в СУБД. Идея в том, что данные разделяются на сегменты в виде дерева. В каждом сегменте находится определенное кол-во отсортированных данных.&#x20;
  * Задается размер для всех сегментов (обычно от 50-2000)
  * Каждый сегмент насыщается данными, когда данных становится больше - происходит разделение на новые сегменты и часть данных уходит в родителя и так рекурсивно
  * Удобство в том, что мы задаем размер сегмента под кол-во оперативной памяти, соотв. в память загружается сегмент данных. Если в нем нет нужных данных - считывается следующий сегмент с диска, прелесть в том, что кол-во обращений к диску сводится к минимуму
* B-дерево может применяться для структурирования (индексирования) информации на жёстком диске (как правило, метаданных).

## Trie

A **trie**, also called **digital tree** or **prefix tree**, is a type of [k-ary](https://en.wikipedia.org/wiki/M-ary_tree) [search tree](https://en.wikipedia.org/wiki/Search_tree), a [tree](https://en.wikipedia.org/wiki/Tree_\(data_structure\)) [data structure](https://en.wikipedia.org/wiki/Data_structure) used for locating specific keys from within a set ([Wiki](https://en.wikipedia.org/wiki/Trie)). Usage: Sorting ([Lexicographic sorting](https://en.wikipedia.org/wiki/Lexicographic_order)), Full-text search, Web search engines, etc.

## Практическое применение

There are two popular Balanced Binary Search Tree: AVL Tree and Red-Black Tree. Both offers O(lg n) search time. But the hidden constant behind Big O makes AVL Tree more suitable for search and Red-Black Tree for insertion-deletion. Insertion-deletion takes less time in Red-Black Tree than AVL Tree. That's Red-Black Tree are more popular than AVL Tree although implementing Red-Black is very complicated task.

Red Black trees are used in:

* [Completely Fair Scheduler](http://en.wikipedia.org/wiki/Completely_Fair_Scheduler) in Linux Kernel
* Computational Geometry Data structures
* In various implementations of Associative Data structures (for e.g C++ STL uses RB tree internally to implement Set and Map)
* HashMap in java 8 uses RB tree instead of linked list to store key value pair in the bucket corresponding to hash of key
