<commit_before>---
title: Binary Search Trees
localeTitle: Деревья двоичного поиска
---
## Деревья двоичного поиска

![Двоичное дерево поиска](https://cdn-images-1.medium.com/max/1320/0*x5o1G1UpM1RfLpyx.png)

Дерево представляет собой структуру данных, состоящую из узлов, которые имеют следующие характеристики:

1.  Каждое дерево имеет корневой узел (вверху), имеющий некоторое значение.
2.  Корневой узел имеет ноль или более дочерних узлов.
3.  Каждый дочерний узел имеет ноль или более дочерних узлов и т. Д. Это создает поддерево в дереве. Каждый узел имеет свое собственное поддерево, состоящее из его детей и их детей и т. Д. Это означает, что каждый узел сам по себе может быть деревом.

Двоичное дерево поиска (BST) добавляет эти две характеристики:

1.  Каждый узел имеет максимум до двух детей.
2.  Для каждого узла значения его левых узлов-потомков меньше, чем у текущего узла, который, в свою очередь, меньше, чем правые узлы-потомки (если они есть).

BST построен на идее алгоритма [бинарного поиска](https://guide.freecodecamp.org/algorithms/search-algorithms/binary-search) , который позволяет быстро находить, вставлять и удалять узлы. Способ их настройки означает, что в среднем каждое сравнение позволяет операциям пропускать около половины дерева, так что каждый поиск, вставка или удаление занимает время, пропорциональное логарифму количества элементов, хранящихся в дереве, `O(log n)` . Однако иногда может произойти худший случай, когда дерево не сбалансировано, а временная сложность `O(n)` для всех трех этих функций. Вот почему самобалансирующиеся деревья (AVL, red-black и т. Д.) Намного эффективнее базового BST.

**Пример худшего сценария:** это может произойти, когда вы добавляете узлы, которые _всегда_ больше, чем узел (родительский), то же самое может произойти, когда вы всегда добавляете узлы со значениями ниже своих родителей.

### Основные операции на BST

*   Create: создает пустое дерево.
*   Вставить: вставить узел в дерево.
*   Поиск: поиск узла в дереве.
*   Удалить: удаляет узел из дерева.

#### Создайте

Сначала создается пустое дерево без каких-либо узлов. Переменная / идентификатор, который должен указывать на корневой узел, инициализируется значением `NULL` .

#### Поиск

Вы всегда начинаете искать дерево в корневом узле и спускаетесь оттуда. Вы сравниваете данные в каждом узле с тем, который вы ищете. Если сравниваемый узел не совпадает, вы либо переходите к правильному ребенку, либо к левому ребенку, что зависит от результата следующего сравнения: если узел, который вы ищете, меньше, чем тот, с которым вы сравнивали его, вы переходите к левому ребенку, иначе (если он больше) вы переходите к правильному ребенку. Зачем? Поскольку BST структурирован (согласно его определению), что правильный ребенок всегда больше родителя, а левый ребенок всегда меньше.

#### Вставить

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

#### делеция

Есть три случая, которые могут произойти, когда вы пытаетесь удалить узел. Если это так,

1.  Нет поддерева (без детей): этот самый простой. Вы можете просто удалить узел без каких-либо дополнительных действий.
2.  Одно поддерево (один ребенок): вы должны убедиться, что после удаления узла его дочерний элемент затем подключается к родительскому элементу удаленного узла.
3.  Два поддерева (двое детей): вы должны найти и заменить узел, который хотите удалить, с его преемником (letfmost node в правом поддереве).

Сложность времени для создания дерева - `O(1)` . Сложность времени для поиска, вставки или удаления узла зависит от высоты дерева `h` , поэтому худшим случаем является `O(h)` .

#### Предшественник узла

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

#### Преемник узла

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

### Специальные типы BT

*   отвал
*   Красно-черное дерево
*   В-дерево
*   Splay tree
*   N-арное дерево
*   Trie (дерево Radix)

### время выполнения
<commit_msg>Correction of the translation (#30648)<commit_after>---
title: Binary Search Trees
localeTitle: Деревья двоичного поиска
---
## Деревья двоичного поиска

![Двоичное дерево поиска](https://cdn-images-1.medium.com/max/1320/0*x5o1G1UpM1RfLpyx.png)

Дерево представляет собой структуру данных, состоящую из узлов, которые имеют следующие характеристики:

1.  Каждое дерево имеет корневой узел (вверху), имеющий некоторое значение.
2.  Корневой узел имеет ноль или более дочерних узлов.
3.  Каждый дочерний узел имеет ноль или более дочерних узлов и т. Д. Это создает поддерево в дереве. Каждый узел имеет свое собственное поддерево, состоящее из его детей и их детей и т. Д. Это означает, что каждый узел сам по себе может быть деревом.

Двоичное дерево поиска (BST) добавляет эти две характеристики:

1.  Каждый узел имеет максимум до двух детей.
2.  Для каждого узла значения его левых узлов-потомков меньше, чем у текущего узла, который, в свою очередь, меньше, чем правые узлы-потомки (если они есть).

BST построен на идее алгоритма [бинарного поиска](https://guide.freecodecamp.org/algorithms/search-algorithms/binary-search) , который позволяет быстро находить, вставлять и удалять узлы. Способ их настройки означает, что в среднем каждое сравнение позволяет операциям пропускать около половины дерева, так что каждый поиск, вставка или удаление занимает время, пропорциональное логарифму количества элементов, хранящихся в дереве, `O(log n)` . Однако иногда может произойти худший случай, когда дерево не сбалансировано, а временная сложность `O(n)` для всех трех этих функций. Вот почему самобалансирующиеся деревья (AVL, red-black и т. Д.) Намного эффективнее базового BST.

**Пример худшего сценария:** это может произойти, когда вы добавляете узлы, которые _всегда_ больше, чем узел (родительский), то же самое может произойти, когда вы всегда добавляете узлы со значениями ниже своих родителей.

### Основные операции на BST

*   Create: создает пустое дерево.
*   Вставить: вставить узел в дерево.
*   Поиск: поиск узла в дереве.
*   Удалить: удаляет узел из дерева.

#### Создайте

Сначала создается пустое дерево без каких-либо узлов. Переменная / идентификатор, который должен указывать на корневой узел, инициализируется значением `NULL` .

#### Поиск

Вы всегда начинаете искать дерево в корневом узле и спускаетесь оттуда. Вы сравниваете данные в каждом узле с тем, который вы ищете. Если сравниваемый узел не совпадает, вы либо переходите к правильному ребенку, либо к левому ребенку, что зависит от результата следующего сравнения: если узел, который вы ищете, меньше, чем тот, с которым вы сравнивали его, вы переходите к левому ребенку, иначе (если он больше) вы переходите к правильному ребенку. Зачем? Поскольку BST структурирован (согласно его определению), что правильный ребенок всегда больше родителя, а левый ребенок всегда меньше.

#### Вставить

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

#### Удаление

Есть три случая, которые могут произойти, когда вы пытаетесь удалить узел. Если это так,

1.  Нет поддерева (без детей): этот самый простой. Вы можете просто удалить узел без каких-либо дополнительных действий.
2.  Одно поддерево (один ребенок): вы должны убедиться, что после удаления узла его дочерний элемент затем подключается к родительскому элементу удаленного узла.
3.  Два поддерева (двое детей): вы должны найти и заменить узел, который хотите удалить, с его преемником (letfmost node в правом поддереве).

Сложность времени для создания дерева - `O(1)` . Сложность времени для поиска, вставки или удаления узла зависит от высоты дерева `h` , поэтому худшим случаем является `O(h)` .

#### Предшественник узла

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

#### Преемник узла

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

### Специальные типы BT

*   отвал
*   Красно-черное дерево
*   В-дерево
*   Splay tree
*   N-арное дерево
*   Trie (дерево Radix)

### время выполнения

{'fraction_non_alphanumeric': 0.05858782759367555, 'fraction_numerical': 0.004656703487112844, 'mean_word_length': 4.841239721695129, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 4, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3744967', 'n_tokens_mistral': 3761, 'n_tokens_neox': 4607, 'n_words': 1234}