Двоичные деревья — действительно английский термин. Бинарное дерево — это тип структуры данных, используемый в информатике и математике. Он состоит из узлов, где каждый узел может иметь не более двух дочерних элементов, называемых левым дочерним элементом и правым дочерним элементом. Самый верхний узел двоичного дерева называется корнем.
Вот несколько методов, связанных с двоичными деревьями:
-
Обход дерева:
- Обход по предварительному заказу: посетите корневой узел, затем рекурсивно посетите левое и правое поддеревья.
- Обход по порядку: рекурсивно посетите левое поддерево, посетите корневой узел, а затем рекурсивно посетите правое поддерево.
- Обход после порядка: рекурсивно посещайте левое и правое поддеревья, а затем посещайте корневой узел.
-
Двоичное дерево поиска (BST):
- Двоичное дерево поиска — это особый тип двоичного дерева, в котором значения узлов в левом поддереве меньше или равны значению корня, а значения узлов в правом поддереве больше, чем значение корня. ценить. Это свойство позволяет эффективно выполнять операции поиска, вставки и удаления.
-
Сбалансированные двоичные деревья:
- Деревья AVL: самобалансирующееся двоичное дерево поиска, в котором высоты левого и правого поддеревьев отличаются не более чем на единицу.
- Красно-черные деревья: еще одно самобалансирующееся двоичное дерево поиска, в котором для обеспечения баланса сохраняются дополнительные свойства.
-
Двоичная куча:
- Полное двоичное дерево, удовлетворяющее свойству кучи. Это может быть минимальная куча, где родительский узел имеет меньшее значение, чем его дочерние элементы, или максимальная куча, где родительский узел имеет большее значение, чем его дочерние элементы. Кучи обычно используются для реализации очередей с приоритетом.
-
Операции с двоичным деревом:
- Вставка: добавление нового узла в двоичное дерево в подходящем месте.
- Удаление: удаление определенного узла из двоичного дерева с сохранением структуры дерева.
- Поиск: поиск определенного значения или узла в двоичном дереве.