Описание тега binary-search-tree

Описание тега Вопросы с тегом
Бинарное дерево поиска - это структура данных, которая состоит из корневого узла с левым и правым дочерними узлами. Левый узел и все его потомки имеют меньшие значения, чем корневой узел, тогда как правый узел и все его потомки имеют большие значения, чем корневой узел. Потомки корневого узла следуют этому же шаблону. Это дает нам дерево, состоящее из упорядоченных элементов.

В информатике двоичное дерево поиска (BST), иногда также называемое упорядоченным или отсортированным двоичным деревом, представляет собой структуру данных двоичного дерева на основе узлов, в которой каждый узел имеет сопоставимый ключ (и соответствующее значение) и удовлетворяет ограничению, согласно которому key в любом узле больше, чем ключи во всех узлах в левом поддереве этого узла, и меньше, чем ключи во всех узлах в правом поддереве этого узла. У каждого узла не более двух дочерних узлов. Каждый дочерний элемент должен быть либо листовым узлом, либо корнем другого двоичного дерева поиска. Левое поддерево содержит только узлы с ключами меньше, чем у родительского узла; правое поддерево содержит только узлы с ключами больше, чем у родительского узла. BST также являются динамическими структурами данных, и размер BST ограничен только объемом свободной памяти в операционной системе.Главное преимущество двоичных деревьев поиска заключается в том, что они остаются упорядоченными, что обеспечивает более быстрое время поиска, чем многие другие структуры данных. Общие свойства деревьев двоичного поиска следующие:

  1. Левое поддерево узла содержит только узлы с ключами меньше ключа узла.

  2. Правое поддерево узла содержит только узлы с ключами больше ключа узла.

  3. Левое и правое поддерево также должны быть двоичным деревом поиска.

  4. У каждого узла может быть до двух узлов-преемников.

  5. Не должно быть повторяющихся узлов.

  6. От корня к каждому другому узлу существует уникальный путь.

Как правило, информация, представленная каждым узлом, представляет собой запись, а не отдельный элемент данных. Однако в целях упорядочения узлы сравниваются по их ключам, а не по какой-либо части связанных с ними записей.