Алгоритмы дерева двоичного поиска для начинающих JavaScript

1656020168 algoritmy dereva dvoichnogo poiska dlya nachinayushhih javascript

Недавно мне пришлось научить старшеклассников программировать. Существует не так много учебных пособий, удобных для начинающих, по алгоритмам, закодированным на JavaScript, на каком языке они изучали. Потому я решил сделать один.

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

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

Что такое двоичное дерево поиска (BST)?

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

По сравнению с обычным деревом, BST обладает следующими свойствами:

  • каждый левый дочерний имеет меньшее значение, чем его отец
  • каждый правильный ребенок имеет большую ценность, чем его отец
  • каждый узел может содержать от 0 до 2 детей.

Следующая диаграмма должна кое-что прояснить вещи.

Определение узла бинарного дерева

Без названия_Произведение-25
Двоичное дерево поиска

Обычно мы определяем узел двоичного дерева с такой функцией в Javascript:

 function TreeNode(val, left, right) {
     this.val = val
     this.left = left
     this.right = right
 }

Основные обходы бинарного дерева (Inorder, Postorder, Preorder)

Первое, что нужно знать, – это прокрутить каждый узел BST. Это позволяет выполнять функцию на всех узлах нашего BST. Например, если мы хотим найти значение x В нашем BST нам понадобятся узлы.

Есть три основных способа сделать это. К счастью, у них общие темы.

Порядковый обход

Рекурсивный алгоритм – это самый простой способ начать работу с обходом бинарного дерева в порядке. Идея такова:

  • Если узел нулевой, ничего не делайте – иначе рекурсивно вызывайте функцию из левого дочернего узла.
  • Затем выполните некоторые операции с узлом после обхода, хотя все дочерние левые элементы. Наш текущий узел гарантированно будет самым левым узлом.
  • Наконец вызовите функцию на node.right.

Алгоритм Inorder обходит узлы дерева слева, к середине, справа.

/**
* @param {TreeNode} root
*/
const inorder = (root) => {
    const nodes = []
    if (root) {
        inorder(root.left)
        nodes.push(root.val)
        inorder(root.right)
    }
    return nodes
}
// for our example tree, this returns [1,2,3,4,5,6]

Постордер обход

Рекурсивный алгоритм – это самый простой способ начать работу с постордерным обходом.

  • Если узел нулевой, ничего не делайте – иначе рекурсивно вызывайте функцию из левого дочернего узла.
  • Когда левых детей больше не будет, вызовите функцию node.right.
  • Наконец выполните некоторые операции с узлом.

Обход Postorder посещает узлы дерева слева, справа, внутрь.

/**
* @param {TreeNode} root
*/
const postorder = (root) => {
    const nodes = []
    if (root) {
        postorder(root.left)
        postorder(root.right)
        nodes.push(root.val)
    }
    return nodes
}
// for our example tree, this returns [1,3,2,6,5,4]

Обход предварительного заказа

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

  • Если узел нулевой, ничего не делайте – иначе выполните какую-нибудь операцию с узлом.
  • Перейдите к левому дочернему узлу и повторите.
  • Выделите правый дочерний узел и повторите.

Обход Postorder посещает узлы дерева изнутри, слева, справа.

/**
* @param {TreeNode} root
*/
const preorder = (root) => {
    const nodes = []
    if (root) {
        nodes.push(root.val)
        preorder(root.left)
        preorder(root.right)
    }
    return nodes
}
// for our example tree, this returns [4,2,1,3,5,6]

Что такое двоичное дерево поиска?

Действительное дерево двоичного поиска (BST) имеет ВСЕХ левых дочерних со значениями меньше родительского узла и ВСЕХ правых дочерних элементов со значениями больше родительского узла.

Чтобы проверить, является ли дерево действительным деревом двоичного поиска:

  • Определите минимальное и максимальное значение, которое может иметь текущий узел
  • Если значение узла выходит за пределы этих границ, верните значение false
  • Рекурсивно проверьте левые дочерние элементы узла, при этом максимальное ограничение установлено на значение узла
  • Рекурсивно проверьте верные дочерние элементы узла, при этом минимальная привязка устанавливается на значение узла
/**
* @param {TreeNode} root
*/
const isValidBST = (root) => {
    const helper = (node, min, max) => {
        if (!node) return true
        if (node.val <= min || node.val >= max) return false
        return helper(node.left, min, node.val) && helper(node.right, node.val, max)
    }
    return helper(root, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER)
}

Как найти максимальную глубину двоичного дерева

Здесь алгоритм пытается найти высоту/глубину нашего BST. Другими словами, мы смотрим, сколько «уровней» содержит BST.

  • Если нулевой узел, мы возвращаем 0, поскольку он не добавляет глубины
  • В противном случае мы добавляем +1 к нашей текущей глубине (мы прошли один уровень)
  • Рекурсивно вычислить глубину дочерних узлов и вернуть максимальную сумму между node.left и node.right
/**
* @param {TreeNode} root
*/
const maxDepth = function(root) {
    const calc = (node) => {
        if (!node) return 0
        return Math.max(1 + calc(node.left), 1 + calc(node.right))
    }
    return calc(root)
};

Как найти самого низкого общего предка между двумя узлами дерева

Давайте повысим сложность. Как найти общего предка между двумя узлами дерева в нашем бинарном дереве? Давайте рассмотрим несколько примеров.

Без названия_Произведение-25
Двоичное дерево поиска

В этом дереве самым низким общим предком 3 и 1 является 2. LCA 3 и 2 равно 2. LCA 6 и 1 и 6 равно 4.

Видите здесь шаблон? LCA между двумя узлами дерева является либо одним из самих узлов (случай 3 и 2), либо родительским узлом, где первый дочерний узел находится где-то в его левом поддеревье, а второй дочерний – где-то в его правом поддеревье.

Алгоритм поиска самого низкого общего предка (LCA) между двумя узлами дерева p и q выглядит следующим образом:

  • Проверьте, найдено ли p или q в левом или правом поддеревьях.
  • Затем проверьте, есть ли текущий узел p или q
  • Если одно из p или q найдено в левом или правом поддеревье, а одно из p или q является самим узлом, мы нашли LCA
  • Если в левом или правом поддеревье находятся оба p и q, мы обнаружили LCA
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
*/
const lowestCommonAncestor = function(root, p, q) {
    let lca = null
    const isCommonPath = (node) => {
        if (!node) return false
        var isLeft = isCommonPath(node.left)
        var isRight = isCommonPath(node.right)
        var isMid = node == p || node == q
        if (isMid && isLeft || isMid && isRight || isLeft && isRight) {
            lca = node
        }
        return isLeft || isRight || isMid
    }
    isCommonPath(root)
    return lca
};

Подведению

Подытоживая, мы научились обходить, проверять и вычислять глубину BST.

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

Добавить комментарий

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