Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Структура данных в виде дерева, отсортированная для быстрого поиска.
Data structure in tree form sorted for fast lookup
В информатике дерево поиска — это древовидная структура данных, используемая для поиска определенных ключей в наборе. Чтобы дерево функционировало как дерево поиска, ключ каждого узла должен быть больше любого ключа в левых поддеревьях и меньше любого ключа в правых поддеревьях. Преимущество деревьев поиска заключается в их эффективном времени поиска, при условии, что дерево достаточно сбалансировано, то есть листья на обоих концах находятся на сопоставимой глубине. Существуют различные структуры данных деревьев поиска, некоторые из которых также обеспечивают эффективную вставку и удаление элементов, что требует поддержания баланса дерева. Деревья поиска часто используются для реализации ассоциативных массивов. Алгоритм поиска использует ключ из пары «ключ-значение» для определения местоположения, а затем приложение сохраняет всю пару «ключ-значение» в этом месте.
In computer science, a search tree is a tree data structure used for locating specific keys from within a set. In order for a tree to function as a search tree, the key for each node must be greater than any keys in subtrees on the left, and less than any keys in subtrees on the right. The advantage of search trees is their efficient search time given the tree is reasonably balanced, which is to say the leaves at either end are of comparable depths. Various search tree data structures exist, several of which also allow efficient insertion and deletion of elements, which operations then have to maintain tree balance. Search trees are often used to implement an associative array. The search tree algorithm uses the key from the key–value pair to find a location, and then the application stores the entire key–value pair at that particular location.
Двойное дерево поиска
Двоичное дерево поиска — это структура данных, основанная на узлах, где каждый узел содержит ключ и два поддерева: левое и правое. Для всех узлов ключ левого поддерева должен быть меньше ключа узла, а ключ правого поддерева — больше ключа узла. Все эти поддеревья также должны являться двоичными деревьями поиска. В худшем случае временная сложность поиска в двоичном дереве поиска равна высоте дерева, которая может быть не более O(log n) для дерева с n элементами.
A Binary Search Tree is a node based data structure where each node contains a key and two subtrees, the left and right. For all nodes, the left subtree's key must be less than the node's key, and the right subtree's key must be greater than the node's key. These subtrees must all qualify as binary search trees. The worst case time complexity for searching a binary search tree is the height of the tree, which can be as small as O(log n) for a tree with n elements.
Древо B
B-деревья являются обобщением двоичных деревьев поиска, поскольку каждый узел может иметь переменное количество поддеревьев. Хотя дочерние узлы имеют предопределенный диапазон, они не обязательно заполняются данными, что может приводить к неэффективному использованию памяти в B-деревьях. Преимущество заключается в том, что B-деревья реже нуждаются в перебалансировке, чем другие самобалансирующиеся деревья. Благодаря переменной длине узлов, B-деревья оптимизированы для систем, работающих с большими блоками данных, и широко используются в базах данных. Временная сложность поиска в B-дереве составляет O(log n).
B trees are generalizations of binary search trees in that they can have a variable number of subtrees at each node. While child nodes have a pre defined range, they will not necessarily be filled with data, meaning B trees can potentially waste some space. The advantage is that B trees do not need to be re balanced as frequently as other self balancing trees. Due to the variable range of their node length, B trees are optimized for systems that read large blocks of data, they are also commonly used in databases. The time complexity for searching a B tree is O(log n).
Трехмерное дерево поиска
Троичное дерево поиска — это тип дерева, которое может иметь 3 дочерних узла: узел для значений меньше, узел для равных значений и узел для значений больше. Каждый узел хранит один символ, и само дерево упорядочено аналогично двоичному дереву поиска, за исключением возможного третьего дочернего узла. Поиск в троичном дереве поиска включает в себя передачу строки для проверки, существует ли путь, содержащий эту строку. Временная сложность поиска в сбалансированном троичном дереве поиска составляет O(log n).
A ternary search tree is a type of tree that can have 3 nodes: a low child, an equal child, and a high child. Each node stores a single character and the tree itself is ordered the same way a binary search tree is, with the exception of a possible third node. Searching a ternary search tree involves passing in a string to test whether any path contains it. The time complexity for searching a balanced ternary search tree is O(log n).
Поиск конкретного ключа
Предполагая, что дерево упорядочено, мы можем выбрать ключ и попытаться найти его в дереве. Приведенные ниже алгоритмы обобщены для двоичных деревьев поиска, но та же идея может быть применена и к деревьям других форматов.
Assuming the tree is ordered, we can take a key and attempt to locate it within the tree. The following algorithms are generalized for binary search trees, but the same idea can be applied to trees of other formats.
Поиск минимума и максимума
В отсортированном дереве минимальное значение находится в самом левом узле, а максимальное – в самом правом узле.
In a sorted tree, the minimum is located at the node farthest left, while the maximum is located at the node farthest right.