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

Отзывать,

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

Итак, бинарное дерево поиска — это именно это, плюс следующие правила.

  • Все, что находится справа от узла, будет иметь большой номер (ключ).
  • Все, что находится слева от узла, будет иметь меньший номер.

Давайте посмотрим на это на примере.

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

План игры по кодированию.

  1. Определить концепцию (бинарного) узла
  2. Дайте определение понятию дерева.
  3. Определяем, как добавлять узлы в дерево // BST.insert(number)
  4. Определяем, как удалять узлы из дерева // BST.remove(number)

Давайте начнем!

1. Как вы определяете бинарный узел?

Каждый узел будет иметь левую и правую стороны (они могут быть пустыми). Каждый узел также имеет номер (ключ).

class BinaryNode {
    constructor(number) {
        this.number = number;
        this.left = null;
        this.right = null;
    }
}

2. Как вы определяете бинарное дерево поиска?

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

class BinarySearchTree {
    constructor(number) {
        this.root = new BinaryNode(number);
    }
}

3. Как вы добавляете узлы в BST?

Это легко, если бы в нашем дереве был только один узел — мы бы проверили левую и правую стороны, чтобы выяснить, куда добавить новый узел.

Используя пример выше, что, если бы мы пытались добавить узел 17? Откуда нам знать, не добавлять ли его ниже узла 13?

Рассмотрим несколько сценариев при добавлении нового узла (newNode) к некоторому существующему узлу (existingNode). Помните, меньшие числа слева, большие числа справа.

(A) Если новыйУзел › существующийУзел // попытаться добавить к существующемуУзелу справа

  • Учитывая это, если правая часть существующего узла свободна // ура! добавлять.
  • Что, если правая сторона существующего узла занята? // проверяем этот узел

(B) Если новыйУзел ‹ существующийУзел // попытаться добавить к левой стороне существующегоУзела

  • Учитывая это, если левая сторона существующего узла свободна // ура! добавить.
  • Что, если левая сторона существующего узла занята? // проверить этот узел

Давайте реализуем.

// Add to BinarySearchTree class as a method
insertNode(existingNode, newNode) {
    if (newNode.number <= existingNode.number) {
        if (!existingNode.left) {
            existingNode.left = newNode;
        } else {
            this.insertNode(existingNode.left, newNode);
        }
    else {
        if (!existingNode.right) {
            existingNode.right = newNode;
        } else {
            this.insertNode(existingNode.right, newNode);
        }
    }
}

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

Но мы еще не закончили! Эта функция предполагает, что newNode — это BinaryNode, а что такое existsNode?

Поскольку наш план состоял в том, чтобы иметь функцию вставки, которая принимает число в качестве параметра, нам нужно каким-то образом соединиться с нашей функцией вставкиNode:

  1. преобразование числа в BinaryNode и
  2. предоставление insertNode отправной точки для запуска
// Add to BinarySearchTree class as a method
insert(number) {
    const newNode = new BinaryNode(number);
    this.insertNode(this.root, newNode);
}

4. Как удалить узлы из BST?

Вообще говоря, мы бы:

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

Это подводит нас к нескольким сценариям. Назовем узел, который мы пытаемся удалить, target. Давайте также представим, что мы сканируем наше дерево, пытаясь найти цель, которую нужно удалить.

(A) Что, если после всех поисков цель не существует в дереве? // Отлично! Больше нечего делать.

(B) Что, если целью является меньшее число, чем сканируемый нами узел? // Мы идем влево, чтобы найти меньшие числа и продолжить поиск и удаление

(C) Что, если цель больше, чем сканируемый узел? // Мы идем вправо, чтобы найти большее число и продолжить нашу деятельность по поиску и удалению

(D) Мы нашли цель! Что теперь?

  • Если у нашей цели нет потомков // Отлично! удалить этот узел.
  • Если у нашей цели есть один (левый или правый) дочерний // Удалите цель, повторно присоедините дочерний элемент к узлу выше по течению от цели.
  • Если у нашей цели есть и левый, и правый дочерние элементы // Необходим мозговой штурм!

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

// Add to BinarySearchTree class as a method
removeNode(node, target) { //node is the current node being scanned
    if (!node) { 
        return null;
    }
    
    if (target < node.number) {
        node.left = this.removeNode(node.left, target);
    } else if (target > node.number) {
        node.right = this.removeNode(node.right, target);
    } else {
        if (!node.left && !node.right) {
            node = null; 
        } else if (!node.left || !node.right) {
            node = node.right ? node.right : node.left;
        } else {
            // Some brainstorming needed!
        }
    }
    return node;
}

Здесь следует отметить три ключевых момента:

  1. Это наше условие остановки. Когда мы достигаем конца «ветки дерева» и не находим нашу цель, мы хотим закончить свою деятельность.
if (!node) {
    return null;
}

2. Удаление узла равносильно установке его значения на ноль.

node = null;

3. Хотим вернуть обновленное дерево

return node;

Вернемся к мозговому штурму.

Используя приведенную выше BTS, попробуем удалить узел 14.

Обратите внимание, что узел 14 имеет двух дочерних элементов, 12 и 19. Помните, правило бинарного дерева состоит в том, что узел может иметь максимум один левый дочерний элемент и один правый дочерний элемент. Это означает, что мы не можем просто снова присоединить 12 и 19 к 28 и закончить на этом.

Что происходит, когда мы пытаемся присоединить 12? Если мы удалим 14 и присоединим 12 к 28, 13 все равно будет справа от 12. Но что нам делать с 19, который также нужно поместить справа от 12?

Что происходит, когда мы пытаемся присоединить 19? Если мы удалим 14 и присоединим 19 к 28, 17 останется слева от 19. Но что нам делать с 12, который также нужно поместить слева от 19?

Нам действительно нужно найти наиболее подходящего кандидата для замены 14, и он может быть только один.

Вот план: что, если мы заменим 14 на 17? Будет ли это работать?

Мы видим, что это так. Все, что справа от 17, больше, все, что слева, меньше. Но была ли это удачная догадка?

Самый левый дочерний элемент правого поддерева.

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

Если бы мы выбрали любое другое число справа от 14 (т. е. 19), мы бы нарушили ограничение двоичного дерева.

Давайте создадим функцию для поиска этой идеальной замены.

// Add to BinarySearchTree class as a method
findIdealReplacement(startingNode) {
    if (!startingNode.left)
        return startingNode;
    else
        return this.findIdealReplacement(startingNode.left)
}

Здесь снова рекурсия. Это примерно переводится как: Начать с узла. Если слева ничего нет, верните этот узел. В противном случае продолжайте идти налево.

Вернемся к основной функции removeNode.

Нам нужно сделать несколько вещей, прежде чем мы закончим:

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

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

// Replace previous version of removeNode function
remove(number) {
    this.root = this.removeNode(this.root, number)
}
removeNode(node, target) { //node is the current node being scanned
    if (!node) { 
        return null;
    }
    
    if (target < node.number) {
        node.left = this.removeNode(node.left, target);
    } else if (target > node.number) {
        node.right = this.removeNode(node.right, target);
    } else {
        if (!node.left && !node.right) {
            node = null; 
        } else if (!node.left || !node.right) {
            node = node.right ? node.right : node.left;
        } else {
            const candidate = this.findIdealReplacement(node.right);
            node.number = candidate.number;
            node.right=this.removeNode(node.right,candidate.number);
        }
    }
    return node;
}

И это все!

Полный код здесь.