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

B-trees

  • Links: habr.com, https://levelup.building-a-b-tree-in-javascript, structies

  • Отлично применяется для индексов в СУБД. Идея в том, что данные разделяются на сегменты в виде дерева. В каждом сегменте находится определенное кол-во отсортированных данных.

    • Задается размер для всех сегментов (обычно от 50-2000)

    • Каждый сегмент насыщается данными, когда данных становится больше - происходит разделение на новые сегменты и часть данных уходит в родителя и так рекурсивно

    • Удобство в том, что мы задаем размер сегмента под кол-во оперативной памяти, соотв. в память загружается сегмент данных. Если в нем нет нужных данных - считывается следующий сегмент с диска, прелесть в том, что кол-во обращений к диску сводится к минимуму

  • B-дерево может применяться для структурирования (индексирования) информации на жёстком диске (как правило, метаданных).

Trie

A trie, also called digital tree or prefix tree, is a type of k-ary search tree, a tree data structure used for locating specific keys from within a set (Wiki). Usage: Sorting (Lexicographic sorting), 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 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

PreviousBinary search (BST)NextTypeScript

Last updated

Was this helpful?