Реализация двоичного дерева поиска

Введение

В этом практическом занятии мы научимся реализовывать двоичное дерево поиска на Java. Двоичное дерево поиска - это двоичное дерево, в котором значение каждого узла больше или равно значениям в его левом поддереве и меньше или равно значениям в его правом поддереве.

Skills Graph

Создание класса BSTNode

Во - первых, создадим Java - класс, представляющий узел двоичного дерева поиска, и назовем его BSTNode. Узел в двоичном дереве поиска должен иметь значение и два дочерних узла - один слева и один справа.

class BSTNode {
    int value;
    BSTNode leftChild;
    BSTNode rightChild;

    BSTNode(int val) {
        this.value = val;
        this.leftChild = null;
        this.rightChild = null;
    }
}

Вставка элементов в двоичное дерево поиска

Для вставки элементов в двоичное дерево поиска мы следуем следующему алгоритму:

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

public static BSTNode insert(int value, BSTNode current) {
    if (current == null) {
        BSTNode newNode = new BSTNode(value);
        return newNode;
    } else {
        if (value < current.value)
            current.leftChild = insert(value, current.leftChild);
        else
            current.rightChild = insert(value, current.rightChild);
    }
    return current;
}

Для тестирования этого метода создадим двоичное дерево поиска и вставим несколько элементов:

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    // Print out the tree to verify the insertion
    System.out.println("Traversal after insertion: ");
    inorderTraversal(root);
}

// Function to traverse the tree inorder
public static void inorderTraversal(BSTNode current) {
    if (current == null)
        return;
    inorderTraversal(current.leftChild);
    System.out.print(current.value + " ");
    inorderTraversal(current.rightChild);
}

Результат:

Traversal after insertion:
5 7 9 12 20 21

Поиск элемента в двоичном дереве поиска

Для поиска элемента в двоичном дереве поиска мы следуем следующему алгоритму:

• Если значение текущего узла совпадает с искомым значением, то возвращаем true.
• Если значение текущего узла больше искомого значения, то рекурсивно вызываем метод для левого дочернего узла.
• Если значение текущего узла меньше искомого значения, то рекурсивно вызываем метод для правого дочернего узла.
• Если текущий узел равен null, то возвращаем false.

public static boolean search(int key, BSTNode current) {
    if (current == null)
        return false;
    if (current.value == key)
        return true;
    else {
        if (key < current.value)
            return search(key, current.leftChild);
        else
            return search(key, current.rightChild);
    }
}

Для тестирования этого метода ищем некоторые элементы:

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    // Search for elements
    System.out.println(search(7, root));
    System.out.println(search(9, root));
    System.out.println(search(17, root));
}

Результат:

true
true
false

Удаление элемента из двоичного дерева поиска

Удаление элемента из двоичного дерева поиска немного сложнее предыдущих шагов, так как нам нужно обрабатывать разные случаи в зависимости от типа узла:

• Если узел не имеет дочерних узлов (листовой узел), просто удалите его.
• Если узел имеет только одного дочернего узла, замените его единственным дочерним узлом.
• Если узел имеет два дочерних узла, замените его минимальным значением из правого поддерева или максимальным значением из левого поддерева.

public static BSTNode delete(int value, BSTNode current) {
    if (current == null)
        return current;
    if (value < current.value)
        current.leftChild = delete(value, current.leftChild);
    else if (value > current.value)
        current.rightChild = delete(value, current.rightChild);
    else if (value == current.value) {
        if (current.leftChild!= null && current.rightChild!= null) {
            int min = current.rightChild.value;
            BSTNode temp = current.rightChild;
            while (temp.leftChild!= null) {
                min = temp.leftChild.value;
                temp = temp.leftChild;
            }
            current.value = min;
            current.rightChild = delete(min, current.rightChild);
        } else if (current.leftChild == null)
            return current.rightChild;
        else if (current.rightChild == null)
            return current.leftChild;
    }
    return current;
}

Для тестирования этого метода удалите несколько узлов и распечатайте дерево:

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    // Delete some nodes
    root = delete(12, root);
    root = delete(20, root);
    root = delete(9, root);

    // Print the tree to verify the deletion
    System.out.println("Traversal after deletion: ");
    inorderTraversal(root);
}

Результат:

Traversal after deletion:
5 7 21

Обход двоичного дерева поиска

Мы можем обходить двоичное дерево поиска разными способами:

• Симметричный (Inorder) обход (Left-Root-Right)
• Префиксный (Preorder) обход (Root-Left-Right)
• Постфиксный (Postorder) обход (Left-Right-Root)
• Обход по уровням (Level-order Traversal, BFS)

public static void inorderTraversal(BSTNode current) {
    if (current == null)
        return;
    inorderTraversal(current.leftChild);
    System.out.print(current.value + " ");
    inorderTraversal(current.rightChild);
}

public static void preorderTraversal(BSTNode current) {
    if (current == null)
        return;
    System.out.print(current.value + " ");
    preorderTraversal(current.leftChild);
    preorderTraversal(current.rightChild);
}

public static void postorderTraversal(BSTNode current) {
    if (current == null)
        return;
    postorderTraversal(current.leftChild);
    postorderTraversal(current.rightChild);
    System.out.print(current.value + " ");
}

public static void levelOrderTraversal(BSTNode root) {
    Queue<BSTNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        BSTNode temp = queue.poll();
        System.out.print(temp.value + " ");
        if (temp.leftChild!= null)
            queue.add(temp.leftChild);
        if (temp.rightChild!= null)
            queue.add(temp.rightChild);
    }
}

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

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    System.out.print("Inorder Traversal: ");
    inorderTraversal(root);
    System.out.print("\nPreorder Traversal: ");
    preorderTraversal(root);
    System.out.print("\nPostorder Traversal: ");
    postorderTraversal(root);
    System.out.print("\nLevel-order Traversal: ");
    levelOrderTraversal(root);
}

Результат:

Inorder Traversal: 5 7 9 12 20 21
Preorder Traversal: 12 7 5 9 20 21
Postorder Traversal: 5 9 7 21 20 12
Level-order Traversal: 12 7 20 5 9 21

Резюме

В этом практическом занятии мы научились создавать, вставлять элементы, искать элемент, удалять элемент из двоичного дерева поиска и обходить его на Java.

Сначала мы создали класс BSTNode, представляющий узел в двоичном дереве поиска. Затем мы реализовали функциональность вставки, поиска и удаления с использованием алгоритмов, специфичных для двоичных деревьев поиска. Наконец, мы узнали, как обходить двоичное дерево поиска с использованием различных техник обхода, таких как симметричный (inorder), префиксный (preorder), постфиксный (postorder) и обход по уровням (level-order traversal).

С этими концепциями вы должны быть в состоянии реализовать двоичные деревья поиска в своих собственных Java-программах.