About Teletype
Join
Duplicate Article
@duplicatearticle
September 11

BST - Построение бинарного дерева поиска

Блок-схема BST: Операции вставки, поиска, удаления и обхода

  • Вставка (insertNode):
    1. Если корень пуст (nullptr), создать новый узел и вернуть его.
    2. Иначе, если значение меньше данных корня – рекурсивно вставить в левое поддерево.
    3. Если больше – рекурсивно вправо.
    4. Возвратить обновлённый корень.
  • Поиск (searchNode):
    1. Если корень пуст или совпадает с искомым значением – вернуть корень.
    2. Если искомое больше – рекурсивно ищем в правом поддереве.
    3. Если меньше – в левом.
  • Удаление (deleteNode):
    1. Рекурсивно пройти по дереву, найти узел.
    2. Если узел имеет одного или нет детей – возвратить ребёнка (или nullptr).
    3. Если два ребёнка – найти минимальный в правом поддереве, скопировать его значение и рекурсивно удалить.
  • Обход (inorderTraversal):
    1. Рекурсивно обойти левое поддерево.
    2. Вывести значение корня.
    3. Рекурсивно обойти правое.

Как строится схема

  • Строится по принципу: старт → логический выбор → рекурсия → выход.
  • Любая операция вызывает себя для дочерних узлов, пока не встретит базовый случай (nullptr).
  • Все ветки дерева формируются сравнением значения вставляемого, искомого или удаляемого с текущим узлом.

Пример реализации на c++

#include <iostream>

// Структура узла бинарного дерева поиска (BST)
struct Node {
    int data;         // Значение узла
    Node* left;       // Указатель на левое поддерево (меньшие значения)
    Node* right;      // Указатель на правое поддерево (большие значения)
    // Конструктор для инициализации узла с заданным значением, указатели пустые
    Node(int d) : data(d), left(nullptr), right(nullptr) {}
};

// Функция вставки нового значения в BST
Node* insert(Node* root, int data) {
    // Если дерево пустое, создаём новый узел и возвращаем его как новый корень
    if (!root) return new Node(data);
    
    // Если значение меньше текущего узла, вставляем рекурсивно в левое поддерево
    if (data < root->data) root->left = insert(root->left, data);
    // Если значение больше – в правое поддерево
    else if (data > root->data) root->right = insert(root->right, data);
    // Возвращаем текущий корень изменённого (возможно) поддерева
    return root;
}

// Симметричный (inorder) обход дерева — вывод элементов в отсортированном порядке
void inorder(Node* r) {
    if (!r) return;                 // Базовый случай: если узла нет, выйти
    inorder(r->left);               // Сначала рекурсивно обойти левое поддерево
    std::cout << r->data << " ";   // Вывести значение текущего узла
    inorder(r->right);              // Затем обойти правое поддерево
}

// Функция поиска узла с заданным значением в BST
Node* search(Node* r, int k) {
    // Если достигнут конец пути или найден узел с ключом, вернуть его
    if (!r || r->data == k) return r;
    
    // Рекурсивно искать в левом или правом поддереве в зависимости от сравнения
    return (k < r->data) ? search(r->left, k) : search(r->right, k);
}

// Функция удаления узла с заданным значением из BST
Node* del(Node* r, int d) {
    if (!r) return nullptr; // Если дерево пустое, просто вернуть nullptr
    
    // Если значение меньше корня, удалить в левом поддереве
    if (d < r->data) r->left = del(r->left, d);
    // Если больше, удалить в правом поддереве
    else if (d > r->data) r->right = del(r->right, d);
    else {
        // Найден узел для удаления
        
        // Если у узла нет левого ребёнка, вернуть его правого ребёнка
        // (возможно nullptr), удаляя текущий узел
        if (!r->left) {
            Node* t = r->right;
            delete r;
            return t;
        }
        // Аналогично если нет правого ребёнка, вернуть левого
        if (!r->right) {
            Node* t = r->left;
            delete r;
            return t;
        }
        // Если есть оба ребёнка
        
        // Найти минимальный узел в правом поддереве (inorder successor)
        Node* t = r->right;
        while (t->left) t = t->left;
        
        // Скопировать значение этого минимального узла в текущий
        r->data = t->data;
        
        // Удалить этот минимальный узел из правого поддерева рекурсивно
        r->right = del(r->right, t->data);
    }
    // Вернуть (возможно обновлённый) корень поддерева
    return r;
}

int main() {
    Node* root = nullptr; // Изначально дерево пустое
    
    // Вставляем несколько значений, формируя BST
    for (int n : {50,30,20,40,70,60,80})
        root = insert(root, n);
    
    // Выводим дерево симметричным обходом (значения по возрастанию)
    inorder(root);
    std::cout << "\n";
    
    // Удаляем узел со значением 20
    root = del(root, 20);
    inorder(root);
    std::cout << "\n";
    
    // Вставляем узел со значением 25
    root = insert(root, 25);
    inorder(root);
    std::cout << "\n";
    
    // Пытаемся найти узел со значением 25 и выводим результат поиска
    std::cout << (search(root, 25) ? "Есть 25\n" : "Нет 25\n");
    
    return 0;
}

Пример реализации на Python

class Node:
    def __init__(self, d):
        self.data = d          # Значение узла
        self.left = self.right = None  # Левый и правый потомки (изначально пусты)

def insert(root, d):
    # Вставка значения d в дерево с корнем root
    if not root:              # Если текущий узел пуст, создаём новый
        return Node(d)
    if d < root.data:         # Если значение меньше, идём в левое поддерево
        root.left = insert(root.left, d)
    elif d > root.data:       # Если больше, идём в правое поддерево
        root.right = insert(root.right, d)
    return root               # Возвращаем (возможно обновлённый) корень

def inorder(root):
    # Симметричный обход для вывода значений по возрастанию
    if root:
        inorder(root.left)             # Сначала левое поддерево
        print(root.data, end=' ')     # Потом текущий узел
        inorder(root.right)            # Потом правое поддерево

def search(root, k):
    # Поиск узла с ключом k в дереве с корнем root
    if not root or root.data == k:   # Если найден узел или достигнут лист
        return root
    # Идем в левое или правое поддерево в зависимости от сравнения
    return search(root.left, k) if k < root.data else search(root.right, k)

def minNode(n):
    # Поиск узла с минимальным значением в дереве с корнем n
    while n.left:    # Идём как можно левее
        n = n.left
    return n

def delete(root, d):
    # Удаление узла с значением d из дерева с корнем root
    if not root:    # Если дерево пустое, ничего не делать
        return None
    if d < root.data:          # Если значение меньше текущего, удалить из левого поддерева
        root.left = delete(root.left, d)
    elif d > root.data:        # Если больше, удалить из правого поддерева
        root.right = delete(root.right, d)
    else:                      # Найдён удаляемый узел
        if not root.left:      # Если нет левого потомка, вернуть правого (может быть None)
            return root.right
        if not root.right:     # Если нет правого потомка, вернуть левого
            return root.left
        # Если есть оба потомка, найти минимальный узел в правом поддереве (inorder successor)
        temp = minNode(root.right)
        root.data = temp.data         # Копируем значение преемника сюда
        root.right = delete(root.right, temp.data)  # Удаляем преемника справа
    return root

# Пример использования
root = None
# Вставка элементов
for v in [50, 30, 20, 40, 70, 60, 80]:  
    root = insert(root, v)

inorder(root)   # Вывод значений дерева в отсортированном порядке
print()

root = delete(root, 20)  # Удаляем узел со значением 20
inorder(root)
print()

root = insert(root, 25)  # Вставляем значение 25
inorder(root)
print()

# Поиск узла со значением 25 и вывод результата
print("Есть 25" if search(root, 25) else "Нет 25")
Duplicate Article
September 11, 07:02
0 views
1 reaction
0 replies
0 reposts