Оригинальная статья: Christina – Understanding Binary Search Trees

В этой статье я хочу подробно рассмотреть древовидную структуру данных. Деревья представляют собой непоследовательную структуру данных, которая полезна для хранения информации, и быстрого поиска. Другими словами, они являются абстрактной моделью иерархической структуры (представьте себе семейное древо). Деревья состоят из узлов (Node) с родительско-дочерними отношениями.

Двоичное дерево и Двоичное дерево поиска

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

Как вы, вероятно, можете догадаться, двоичное дерево поиска (binary search tree – BST) – это тоже двоичное дерево. Основное отличие состоит в том, что BST позволяет хранить отсортированные узлы с меньшим значением слева и узлы с большим значением справа. Как показано на рисунке выше.

Создание узлов и BST классов

Я обычно настоятельно рекомендую писать код по мере чтения статьи в каком нибудь онлайн редакторе (например https://codesandbox.io/) и постоянно тестировать / играть с тем, что мы пишем. Для начала мы создадим наш класс Node, который будет представлять узлы в нашем BST:

class Node {
    constructor(data) {
        this.data = data; // node value
        this.left = null;   // left node child reference
        this.right = null; // right node child reference
    }
}

Далее мы объявим базовую структуру нашего класса BinarySearchTree:

class BinarySearchTree {
    constructor() {
        this.root = null; // корень bst
    }
}

Нашим следующим шагом будет реализация основных методов. Вот что мы рассмотрим:

• insert(data)
• inOrderTraverse()
• preOrderTraverse()
• postOrderTraverse()
• search(data)
• remove(data)

Вставка узлов в BST

Чтобы вставить новый узел в дерево, нужно выполнить два шага:

1. Проверить, является ли вставка особым случаем. Другими словами, нам нужно проверить, является ли узел, который мы пытаемся добавить, первым в дереве (то есть если какое либо значение у атрибута root). Если это так (то есть root == null), нам просто нужно указать первый (корневой) узел для этого нового узла, создав экземпляр класса Node и присвоив его корневому свойству root.
2. Если первое условие не выполняется тогда просто добавить узел в соответствующую позицию.

insert(data) {
    let newNode = new Node(data);

    if (this.root === null) {
        this.root = newNode;
    } else {
        this.insertNode(this.root, newNode); // helper method below
    }
}

insertNode(node, newNode) {
    if (newNode.data < node.data) {
        if (node.left === null) {
            node.left = newNode;
        } else {
            this.insertNode(node.left, newNode);
        }
    } else {
        if (node.right === null) {
            node.right = newNode;
        } else {
            this.insertNode(node.right, newNode);
        }
    }
}

В итоге, insert(data) создает новый узел Node со значением data и, если дерево пустое, устанавливает этот узел в качестве корня дерева, в противном случае вызывается insertNode(this.root, newNode). insertNode (node, newNode) – наш вспомогательный метод, который отвечает за сравнение данных нового узла с данными текущего узла и рекурсивное перемещение влево или вправо, соответственно, до тех пор, пока не найдет правильный узел с нулевым значением, в который можно добавить новый узел.

Проверим как это работает, и выполним следующий код …

const BST = new BinarySearchTree();
BST.insert(11); // establishes root node 
BST.insert(7);
BST.insert(9);
BST.insert(15);

BST.insert(6);

console.log(BST);

… мы можем проиллюстрировать последнюю вставку этой диаграммой:

Обход BST

Обход дерева (Traverse) – это процесс посещения всех узлов дерева и выполнения операции на каждом узле. Большой вопрос, как мы должны обходить дерево? Существует три общих подхода: прямой (in-order), симметричный или поперечный (pre-order) и в обратном порядке (post-order).

Прямой обход

При прямом обходе будут посещаться все узлы в порядке возрастания, начиная с указанного узла (хотя это и необязательно), и выполнять заданную функцию обратного вызова callback (также необязательно). Опять же, мы будем использовать рекурсию:

inOrderTraverse(node, callback) {
    if (node != null) {
        this.inOrderTraverse(node.left, callback);
        callback(node.data);
        this.inOrderTraverse(node.right, callback);
    }
}

Следующая диаграмма показывает путь, по которому идет наш inOrderTraverse:

Симметричный обход

При симметричном обходе посещаются каждый узел до его потомков. Обратите внимание на довольно тонкую разницу с прямым обходом в коде и на диаграмме:

preOrderTraverse(node, callback) {
    if (node != null) {
        callback(node.data);
        this.preOrderTraverse(node.left, callback);
        this.preOrderTraverse(node.right, callback);
    }
}

Обход в обратном порядке

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

postOrderTraverse(node, callback) {
    if (node != null) {
        this.postOrderTraverse(node.left, callback);
        this.postOrderTraverse(node.right, callback);
        callback(node.data);
    }
}

Поиск значений в BST

Рассмотрим вариант поиска значений в BST. В нашей реализации, node представляет текущий узел, а data представляют значение, которое мы ищем:

search(node, data) {
    if (node === null) {
        return null;
    } else if (data < node.data) {
        return this.search(node.left, data);
    } else if (data > node.data) {
        return this.search(node.right, data);
    } else {
        return node;
    }
}

Я рекомендую на данном этапе протестировать весь код, вы можете добавить в console.log, чтобы можно было бы увидеть, какие узлы посещаются. Если вы не пишете код, проследите по одной из диаграмм в этой статье и спрогнозируйте путь метода search при поиске определенного значения. Вы заметите, как легко найти максимальные и минимальные значения!

Использовать метод search можно так:

...
  search(node, data) {
   ....
    else {
      console.log(node)
      return node;
    }
  ...
  }


...

BST.search(BST.root, 9);

Удаление узла из BST

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

// находит минимальный узел в дереве
minNode(node) {
    // если слева от узла ноль тогда это должен быть минимальный узел
    if (node.left === null)
        return node;
    else
        return this.findMinNode(node.left);
}


remove(data) {
    this.root = this.removeNode(this.root, data); // helper method below
}

removeNode(node, data) {
    if (node === null) {
        return null;
    // если данные, которые нужно удалить, меньше, чем данные корня, переходим к левому поддереву
    } else if (data < node.data) {
        node.left = this.removeNode(node.left, data);
        return node;
    // если данные, которые нужно удалить, больше, чем данные корня, переходим к правому поддереву
    } else if (data > node.data) {
        node.right = this.removeNode(node.right, data);
        return node;
    // если данные такие как данные корня, удаляем узел
    } else {
        // удаляем узел без потомков (листовой узел (leaf) или крайний)
        if (node.left === null && node.right === null) {
            node = null;
            return node;
        }

        // удаляем узел с одним потомком
        if (node.left === null) {
            node = node.right;
            return node;
        } else if(node.right === null) {
            node = node.left;
            return node;
        }

        // удаляем узел с двумя потомками
        // minNode правого поддерева хранится в новом узле
        let newNode = this.minNode(node.right);
        node.data = newNode.data;
        node.right = this.removeNode(node.right, newNode.data);
        return node;
    }
}

В начале мы ищем соответствующий узел, который нужно удалить, а потом есть три сценария, которые мы рассмотрим более подробно ниже.

Удаление крайнего узла (leaf node)

Первый сценарий включает в себя крайний узел (leaf node), то есть у которого нет левого или правого дочернего элемента. В этом случае нам нужно будет удалить узел, присвоив ему значение null. Однако не забывайте, что мы также должны позаботиться о ссылках из родительского узла:

Удаление узла с одним потомком

Второй сценарий включает в себя узел, который имеет левый или правый дочерний узел. Как вы можете видеть на диаграмме ниже, нам нужно пропустить соответствующий узел и назначить родительский указатель на дочерний узел:

Удаление узла с двумя потомками

Третий и последний сценарий включает в себя узел с двумя дочерними элементами. Чтобы удалить такой узел, нужно выполнить следующие действия:

1. Как только вы найдете узел, который нужно удалить, найдите минимальный узел из его правого края поддерева (см. заштрихованную область на диаграмме ниже).
2. Далее вы можете обновить значение узла ключом минимального узла из его правого поддерева. Этим действием вы заменяете ключ узла, что означает, что он будет удален.
3. Теперь у вас есть два узла в дереве с одним и тем же ключом, что не правильно. Таким образом, нужно удалить минимальный узел из правого поддерева, поскольку вы переместили его на место удаленного узла.
4. Наконец, нужно вернуть обновленную ссылку на узел его родителю.

Заключение

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

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