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

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

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

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

Как программно представить двоичное дерево поиска в JavaScript? На самом деле это довольно просто. На самом деле намного проще, чем представить график. Объект JavaScript - это идеальная структура данных для представления каждого узла в дереве, поскольку он позволяет нам хранить реляционные данные о каждом правом и левом дочернем узле.

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

let numbers = [9, 4, 12, 15, 72, 21, 36, 2, 10, 14, 8, 19]

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

let rootNode = {element: 9, rightChild: null, leftChild: null}

Переходя к следующему числу в списке, 4, мы видим, что 4 меньше 9 и, следовательно, будет его левым дочерним элементом. Мы представляем 4 с помощью JS-объекта и обновляем rootNode:

let nodeA = {element: 4, rightChild: null, leftChild: null}

let rootNode = {element: 9, rightChild: null, leftChild: nodeA}

Затем мы переходим к третьему элементу в массиве, который равен 12. 12 больше 9, поэтому будет добавлен как правый дочерний элемент корневого узла:

let nodeB = {element: 12, rightChild: null, leftChild: null}
let nodeA = {element: 4, rightChild: null, leftChild: null}

let rootNode = {element: 9, rightChild: nodeB, leftChild: nodeA}

Это продолжается через каждый из элементов в начальном наборе чисел, пока мы не дойдем до последнего. После 12 мы представляем 15. Мы знаем, что оно больше 9, поэтому двигайтесь вправо. Мы знаем, что оно больше 12, поэтому двигайтесь вправо. Затем мы видим, что правильного ребенка еще нет, поэтому 15 становится правильным ребенком и так далее, и тому подобное. Теперь у нас есть полное двоичное дерево поиска, и мы можем эффективно его обходить, зная, что с каждым посещенным узлом мы избавляемся от необходимости посещать его родственный элемент или любого из его потомков.

let nodeK = {element: 19, rightChild: null, leftChild: null}
let nodeJ = {element: 8, rightChild: null, leftChild: null}
let nodeI = {element: 14, rightChild: null, leftChild: null}
let nodeH = {element: 10, rightChild: null, leftChild: null}
let nodeG = {element: 2, rightChild: null, leftChild: null}
let nodeF = {element: 36, rightChild: null, leftChild: null}
let nodeE = {element: 21, rightChild: nodeF, leftChild: nodeK}
let nodeD = {element: 72, rightChild: null, leftChild: nodeE}
let nodeC = {element: 15, rightChild: nodeD, leftChild: nodeI}
let nodeB = {element: 12, rightChild: nodeC, leftChild: nodeH}
let nodeA = {element: 4, rightChild: nodeJ, leftChild: nodeG}
let rootNode = {element: 9, rightChild: nodeB, leftChild: nodeA}

Приведенный выше код эквивалентен приведенному ниже дереву:

                                 9
                              /      \
                            4          12
                          /   \       /   \
                        2       8   10     15
                                          /   \
                                        14     72
                                              /
                                            21
                                           /  \
                                         19    36

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

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