Вставка узла в бинарное дерево поиска

Сначала определим бинарное дерево поиска, представленное в коде Java следующим образом:

public class BST<Key extends Comparable<Key>, Value> {

    // Узлы в дереве — приватный класс; внешнему миру не нужно знать конкретную реализацию узлов двоичного дерева поиска
    private class Node {
        private Key key;
        private Value value;
        private Node left, right;

        public Node(Key key, Value value) {
            this.key = key;
            this.value = value;
            left = right = null;
        }
    }
    // Корневой узел
    private Node root;
    // Количество узлов в дереве
    private int count;
    // Конструктор, по умолчанию создаёт пустое двоичное дерево поиска
    public BST() {
        root = null;
        count = 0;
    }
    // Вернуть количество узлов в бинарном дереве поиска
    public int size() {
        return count;
    }
    // Вернуть, является ли бинарное дерево поиска пустым
    public boolean isEmpty() {
        return count == 0;
    }
}

Node представляет узел, а count представляет количество узлов.

В следующем примере показаны шаги вставки элемента 61 в бинарное дерево поиска, приведённое ниже:

(1) Вставляемый элемент 61 больше 42; сравните с корневым узлом правого поддерева узла 42.

(2) 61 больше 59, поэтому 61 нужно переместить в соответствующую позицию в правом поддереве узла 59. Так как здесь пусто, вставьте его непосредственно как правый дочерний узел узла 59.

Операция вставки также является рекурсивным процессом и охватывает три случая: равно, больше и меньше.

Пример кода на Java

Загрузка пакета исходного кода:Скачать

код файла src/example/binary/BinarySearchTreeInsert.java:

package example.binary;

/**
* Вставить новый элемент в бинарное дерево поиска
 */

public class BinarySearchTreeInsert<Key extends Comparable<Key>, Value> {

    // Узлы в дереве — приватный класс; внешнему миру не нужно знать конкретную реализацию узлов двоичного дерева поиска
    private class Node {
        private Key key;
        private Value value;
        private Node left, right;

        public Node(Key key, Value value) {
            this.key = key;
            this.value = value;
            left = right = null;
        }
    }

    private Node root;  // Корневой узел
    private int count;  // Количество узлов в дереве

    // Конструктор, по умолчанию создаёт пустое двоичное дерево поиска
    public BinarySearchTreeInsert() {
        root = null;
        count = 0;
    }

    // Вернуть количество узлов в бинарном дереве поиска
    public int size() {
        return count;
    }

    // Вернуть, является ли бинарное дерево поиска пустым
    public boolean isEmpty() {
        return count == 0;
    }

    // Вставить новую пару данных (key, value) в бинарное дерево поиска
    public void insert(Key key, Value value) {
        root = insert(root, key, value);
    }

    // Основной код --- начало
    // Вставка узла (key, value) в бинарное дерево поиска с корнем в node с использованием рекурсивного алгоритма
    // Возвращает корень двоичного дерева поиска после вставки нового узла
    private Node insert(Node node, Key key, Value value) {
        if (node == null) {
            count++;
            return new Node(key, value);
        }
        if (key.compareTo(node.key) == 0)
            node.value = value;
        else if (key.compareTo(node.key) < 0)
            node.left = insert(node.left, key, value);
        else    // key > node->key
            node.right = insert(node.right, key, value);

        return node;
    }
    // Основной код --- конец
}
Другие расширения