6. Двоичное дерево поиска (Binary search tree)

Прежде чем перейти к двоичному дереву поиска, вспомним что такое двоичный поиск по отсортированному массиву (он же метод деления пополам или дихотомия).

6.2 Двоичный поиск

Искать элементы в отсортированном массиве можно гораздо быстрее, чем в неотсортированном.

    ┌────┬────┬────┬────┬────┬────┬────┬────┬────┐
    |  0 |  1 |  3 | 10 | 11 | 23 | 30 | 71 | 99 |
    └────┴────┴────┴────┴────┴────┴────┴────┴────┘

Если нам нужно найти число 30 в отсортированном массиве, мы можем сделать такие итерации:

1. Начать итерирование с середины массива — число 11. Число 30 больше числа 11, значит мы можем отбросить в наших поисках все значения с начала массива по элемент со значением 11 включительно;
2. Затем мы снова поделим оставшийся массив пополам, взяв элемент 71. 30 меньше 71, значит мы можем отбросить все элементы правее 71 включительно;
3. Продолжим деление пополам, взяв элемент со значением 30. Это и есть искомый элемент — можно заканчивать итерирование

                           |
                           v
    ┌────┬────┬────┬────┬────┬────┬────┬────┬────┐
1.  |    |    |    |    |    | 23 | 30 | 71 | 99 |
    └────┴────┴────┴────┴────┴────┴────┴────┴────┘

                                          |
                                          v
    ┌────┬────┬────┬────┬────┬────┬────┬────┬────┐
2.  |    |    |    |    |    | 23 | 30 |    |    |
    └────┴────┴────┴────┴────┴────┴────┴────┴────┘

                                     |
                                     v
    ┌────┬────┬────┬────┬────┬────┬────┬────┬────┐
3.  |    |    |    |    |    |    | 30 |    |    |
    └────┴────┴────┴────┴────┴────┴────┴────┴────┘

Каждая итерация в двоичном поиске исключает из массива половину элементов. Это происходит из-за того, что массив отсортирован. Во время поиска мы можем точно определить, какую из половин массива нам следует исключить из дальнейших итераций, благодаря сравнению текущего элемента с искомым. Двоичный поиск работает за O(log n), в отличие от линейного поиска, который работает за O(n).

Отсортированный массив прекрасно подходит для поиска элементов, но плохо подходит для добавления и удаления элементов (оба работают за O(n) по времени). Двоичное дерево поиска может обеспечивать такую же сложность поиска, но быть гораздо эффективнее массива при добавлении и удалении элементов.

6.3 Структура двоичного дерева поиска

Главная идея, которая лежит в основе двоичного дерева поиска, — взять все элементы отсортированного массива и организовать их в виде двоичного дерева.

    ┌────┬────┬────┬────┬────┬────┬────┬────┬────┐
    |  0 |  1 |  3 | 10 | 11 | 23 | 30 | 71 | 99 |
    └────┴────┴────┴────┴────┴────┴────┴────┴────┘

                           |
                           v

                        ┌─────┐
                        |  11 |
                        └─────┘
                       /       \
                 ┌─────┐        ┌─────┐
                 |  3  |        |  30 |
                 └─────┘        └─────┘
                /      |        |      \
            ┌─────┐  ┌─────┐ ┌─────┐  ┌─────┐
            |  1  |  |  10 | |  23 |  |  71 |
            └─────┘  └─────┘ └─────┘  └─────┘
            /                               \
        ┌─────┐                            ┌─────┐
        |  0  |                            |  99 |
        └─────┘                            └─────┘

Двоичное дерево поиска должно обладать такими свойствами:

1. Каждый узел должен иметь не более двух поддеревьев (это должно быть двоичное дерево);
2. Каждый узел в дереве должен быть больше всех узлов в своем левом поддереве;
3. Каждый узел в дереве должен быть меньше всех узлов в своем правом поддереве.

6.4 Операции над двоичным деревом поиска

6.4.1 Поиск элемента (find)

Поиск значения в двоичном дереве поиска очень сильно напоминает поиск в отсортированном массиве.

find(key, tree = this._root) {
    // Если дерево пусто, то элемента со значением key
    // в нем нет -- возвращаем false
    if (!tree) {
        return false;
    }

    // Если значение текущего элемента равно искомому,
    // возвращаем true
    if (tree.key === key) {
        return true;
    }

    // Если искомое значение меньше значения в текущем узле,
    // ищем в левом поддереве. Иначе -- в правом.
    if (key < tree.key) {
        return this.find(key, tree.left);
    } else {
        return this.find(key, tree.right);
    }
}

6.4.2 Добавление элемента (insert)

В определении двоичного дерева поиска ничего не говорится о том, что дерево должно быть сбалансировано. Дерево может принять такую форму:

    ┌───┐
    | 1 |
    └───┘
         \
          ┌───┐
          | 2 |
          └───┘
                \
                 ┌───┐
                 | 3 |
                 └───┘

Это несбалансированное бинарное дерево поиска. В таком виде оно подобно связанному списку, поиск по которому работает за O(n) по времени.

Балансировка будет описана в следующих частях, текущая реализация не будет ее в себя включать.

insert(key, tree = this._root) {
    // Если дерево пусто, создаем корневой элемент
    if (!this._root) {
        this._root = new BinaryTreeNode(key);
        return;
    }

    if (key < tree.key) {
        // Если значение для вставки меньше значения текущего узла,
        // продолжаем итерации влево
        if (tree.left) {
            this.insert(key, tree.left);

        // Если левого поддерева нет, то создаем новый узел
        // и заканчиваем итерации
        } else {
            tree.setLeft(new BinaryTreeNode(key));
        }
    } else {
        // Если значение для вставки больше значения текущего узла,
        // продолжаем итерации вправо
        if (tree.right) {
            this.insert(key, tree.right);

        // Если правого поддерева нет, то создаем новый узел
        // и заканчиваем итерации
        } else {
            tree.setRight(new BinaryTreeNode(key));
        }
    }
}