Сборник Олпрогера

Самое сбалансированное дерево(но со своими приколами)

Админ продолжает рубрику "веселые приколы алгоритмов и структур данных". Cегодня я хочу познакомить вас с B-деревьями. В отличие от некоторых прошлых тем, эта структура используется в продуктвой практике, например, в базах данных и файловых системах. А вот в олимпиадном программировании(как отдельная задача) оно встречается редко, хотя выполняет те же задачи, что и декартово дерево по явному ключу. Написать его не так сложно, но с удалениями придется попотеть.

Если обратиться к определению, то B-дерево — это идеально сбалансированное дерево поиска, где каждый узел содержит упорядоченный список ключей, а его дочерние узлы делят диапазоны этих ключей. Сбалансированность достигается автоматически благодаря строгим правилам разбиения узлов. Вам не нужно думать о поддержании высоты дерева, как в AVL или красно-черных деревьях.Ключи внутри узлов отсортированы, а у каждого узла (если у него t ключей) ровно t + 1 дочерних узлов. Популярные вариации - 2-3 дерево(каждый узел содержит от 1 до 2 ключей) и 2-3-4 дерево(узел содержит от 1 до 3 ключей). Узлы могут содержать больше ключей, но тогда время поиска внутри одного узла увеличивается.

Материалы на почитать:
- https://neerc.ifmo.ru/wiki/index.php?title=B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE (neerc это вообще библия алгоритмов)
- https://ru.wikipedia.org/wiki/B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE
- https://medium.com/@nomannayeem/the-power-of-b-trees-optimizing-data-storage-and-retrieval-a20f0fa05846 - это просто интересно
- https://www.cs.usfca.edu/~galles/visualization/BTree.html - визуализация

Wikipedia

B-дерево

B-дерево — структура данных, дерево поиска. С точки зрения внешнего логического представления — сбалансированное, сильно ветвистое дерево. Часто используется для хранения данных во внешней памяти.

👍14🎄3👎1

www.tgoop.com/sbornik_olprog/249

3.32K viewsNikolay Khadzakos, Dec 16, 2024 at 16:02

Самое сбалансированное дерево(но со своими приколами)

Админ продолжает рубрику "веселые приколы алгоритмов и структур данных". Cегодня я хочу познакомить вас с B-деревьями. В отличие от некоторых прошлых тем, эта структура используется в продуктвой практике, например, в базах данных и файловых системах. А вот в олимпиадном программировании(как отдельная задача) оно встречается редко, хотя выполняет те же задачи, что и декартово дерево по явному ключу. Написать его не так сложно, но с удалениями придется попотеть.

Если обратиться к определению, то B-дерево — это идеально сбалансированное дерево поиска, где каждый узел содержит упорядоченный список ключей, а его дочерние узлы делят диапазоны этих ключей. Сбалансированность достигается автоматически благодаря строгим правилам разбиения узлов. Вам не нужно думать о поддержании высоты дерева, как в AVL или красно-черных деревьях.Ключи внутри узлов отсортированы, а у каждого узла (если у него t ключей) ровно t + 1 дочерних узлов. Популярные вариации - 2-3 дерево(каждый узел содержит от 1 до 2 ключей) и 2-3-4 дерево(узел содержит от 1 до 3 ключей). Узлы могут содержать больше ключей, но тогда время поиска внутри одного узла увеличивается.

Материалы на почитать:
- https://neerc.ifmo.ru/wiki/index.php?title=B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE (neerc это вообще библия алгоритмов)
- https://ru.wikipedia.org/wiki/B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE
- https://medium.com/@nomannayeem/the-power-of-b-trees-optimizing-data-storage-and-retrieval-a20f0fa05846 - это просто интересно
- https://www.cs.usfca.edu/~galles/visualization/BTree.html - визуализация

BY Сборник Олпрогера